Thou Shalt Not Multiply

Entia non sunt multiplicanda sine necessitate. —- Wilhelm von Ockham (1288 – 1348) zugeschrieben

„Wie multipliziert ein Computer?“ fragte mein Sohn neulich. „Warum multipliziert er nicht indem er so-und-so-oft addiert?“ Eine sehr gute Frage. Wer weiß die Antwort? Informatiker/innen wissen die Antwort – oder sollten sie wissen.

Das Handwerk des Addierens, Multiplizierens, Sortierens, etc. gehört zur Algorithmik, einem Teilgebiet der Informatik, auch wenn Schulen das so genannte Rechnen fälschlicherweise der Mathematik zuordnen. Die Algorithmik beruht darauf, dass Menschen und Maschinen einfache Arbeitsschritte verbinden können und manchmal – je nach Zwischenergebnis – das eine oder andere tun.
wüste
dacarlo / photocase.com

Gegeben zwei Zahlen a und b. Wenn a ungerade ist, ziehe eins ab und addiere b zu c. (Zu Beginn sei c Null.) Dann halbiere a und verdopple b. Sobald a Null ist bist Du fertig; c ist dann Dein Ergebnis.

Das Vertrackte an Computern ist, dass sie solche Sachen schnell machen und dass sie sich sehr, sehr viele solche Anweisungen merken können. Und dann wird es sehr schwer, zu verstehen, was ein Computer da eigentlich macht. Wenn man aber ganz genau hinsehen würde, wären es immer nur solche einfachen Arbeitsschritte.

Jeder dieser Arbeitsschritte kostet Zeit und Energie. Und genauso, wie viele winzige Sandkörner sich zu großen Dünen anhäufen können, können sich viele kleine Arbeitsschritte zu langen Wartezeiten und hohen Stromrechnungen summieren. Es macht also Sinn, zu bedenken, welche Arbeitsschritte die verschiedenen Algorithmen einem Computer aufbürden.

Quidquid agis, prudenter agas et respice finem. — Lateinischer Kalenderspruch

Addieren, Verdoppeln, Halbieren sind einfach – zumindest für Computer – multiplizieren nicht (und Dividieren schon gar nicht). In der Praxis spielt diese Einsicht keine Rolle. Wer programmiert heute noch so nahe an der Maschine, dass er ihr einzelne Rechenschritte vorschreibt? Die einfachen Tricks, die seit Jahren im Internet kolportiert werden, beherrscht heutzutage sowieso der Compiler [1], falls es überhaupt einen gibt [2].

Das Beispiel zeigt aber das grundlegende Prinzip: Bei allem was Du einen Rechner tun lässt, sei vorsichtig und bedenke das Ende. Quidquid agis, prudenter agas et respice finem. Und oft heißt das, dass ein gedankenlos dahin g’schlamperter Code zigtausendfach durchlaufen wird und der Computer dabei viele Dinge tun muss, die sich nach ein bisschen Nachdenken als unnötig herausstellen.

Neben dem angesprochenen Multiplizieren durch Addieren ist die klassische Frage nach Bubble Sort versus Quicksort ein weiteres Lehrbuchbeispiel für die Notwendigkeit guter Algorithmen. In der Praxis zeigt sich das Problem allerdings eher durch falsch gewählte Datenstrukturen, die dann über die entsprechenden Bibliotheksfunktionen auf die Algorithmik durchschlagen:

Finde das größte X, das auch ein U ist! (Hier sei U ein Prädikat auf einer Kollektion der X.) Wer bei dieser Aufgabenstellung sortiert, hat nicht lange genug überlegt.

function foo(X) {
  while ( !X.sort().first().isU() ) {
    X := X.sort().butFirst();
  }
  return X.sort().first();
}

Das schreibt sich vielleicht elegant, ist aber trotzdem blöde, weil offenbar X immer wieder sortiert wird. Mehr noch, verändert die unterstellte Sort-Methode das ihr übergebene X oder liefert sie eine neue, sortierte Liste? Der Rückgabewert, den beispielsweise JavaScript liefert, suggeriert Letzteres, aber selbst in Common Lisp, wo man es am wenigsten erwarten würde [3, 4], wird die ursprüngliche Liste verändert. Der Rückgabewert ist nur eine zusätzliche Referenz auf X. Poisoned syntactic suggar sozusagen.

Statt also gedankenlos Bibliotheksfunktionen zusammen zu stecken und unnötige Bremsklötze oder gar Fehler einzubauen, sollte man sich eher fragen, ob diese Aufgabe häufiger gestellt wird und vielleicht nur wenige X tatsächlich ein U sind; — und man sollte die oben angeführte Referenz [4] nachlesen …

Seit einiger Zeit grassiert überdies die Idee, Daten als Zeichenketten (engl. Strings) zu speichern: mydata[„foo“]=“bar“. Aber was in PHP oder JavaScript so unschuldig daher kommt, braucht zur Laufzeit String-Vergleiche und öffnet Tippfehlern Tür und Tor. Beim altbackenen C/C++ meckert der Compiler, wenn er mydata.foo = bar nicht kennt, weil das entsprechende Struct und Enum fehlt.

Fasse Dich kurz! — Leitspruch des Bundespost-Marketings

In der Wissenschaft sollte Ockham’s Rasiermesser dafür sorgen, unnötigen Unsinn zu verhindern: Entia non sunt multiplicanda sine necessitate. Vervielfältige nicht grundlos die Zahl der Dinge mit denen Du hantierst. Also lieber eine Kepler-Ellipse statt Dutzende Epizykeln.

Selbiges sollte aber auch in den Niederungen des angewandten Programmierens gelten: Lieber ein Durchlauf durch alle X als Dutzende. Lieber eine Liste (die man nicht verändern muss) als viele kopierte Listen. Lieber ein Integer als Dutzende von Zeichen in einem String — von deren Beliebigkeit ganz zu schweigen.

Verkümmern die Adern zwischen reiner und angewandter Mathematik, so entartet die reine zu einer abgewandten
und die angewandte zu einer unreinen Mathematik. — Robert Sauer, Lehrbuch der Ingenieur-Mathematik, Springer, 1959

Leider ist Praxis aber nicht so rein. Vor allem stammt die Informatik u.a. von der angewandten und nicht der reinen Mathematik ab. In der Praxis zählt Kosteneffizienz — und da haben einfach zu handhabende aber Laufzeit-suboptimale Lösung ihre Berechtigung. Man sollte es halt, wie immer im Leben, nicht übertreiben.


Zum Schluss sei allerdings schmunzelnd darauf hingewiesen, dass meine Argumentation im Rahmen der Green IT deutlich besser dasteht, denn obwohl ein Systemarchitekt monatlich hundertmal mehr als ein Server kostet, verbraucht er nur ca. 100 Watt. Ein Server inklusive seiner Betriebsumgebung aber verbraucht ca. 480 Watt. Ein Stück Software, das drei Jahre lang auf einem Server betrieben wird (ca. 1000 Tage), 10% effizienter zu machen darf – aus monetärer Sicht – den Architekten also maximal ca. einen Tag kosten. Aufgrund der CO2-Bilanz hätten es hingegen ca. 16 Personenmonate sein dürfen. Vielleicht sollte die IT Industrie hier mal Zuschüsse beantragen?

[fblike style=“button_count“ showfaces=“false“ width=“90″ verb=“like“ font=“arial“ float=“left“] [fbshare type=“button“ float=“left“] [google_plusone size=“medium“ float=“left“] [twitter style=“horizontal“ float=“left“ lang=“de“] [linkedin_share style=“right“ float=“left“]

Verwandte Beiträge

Leave a comment

Pj28

Bitte geben Sie den Text vor: