Archiv für Juni 2009

Zahlenvergleich

Freitag, 26. Juni 2009

Heutzutage wird es einem sehr leicht gemacht große Datenbestände zu sortieren. Es gibt vorgefertigte, hoch performante Methoden die lediglich die zu sortierenden Daten und einen Zeiger/Referenz auf eine Vergleichsmethode erwarten. Diese Methode ist im Normalfall ganz einfach gestrickt. Sie bekommt einfach zwei Parameter vom Typ der zu sortierenden Daten. Die Methode hat nichts weiter zu tun als diese Daten auszuwerten. Wenn der erste Parameter als “größer” zu bewerten ist, gibt die Methode einen positiven Wert, bei “kleiner” einen Negativen und bei Gleichheit eine 0 zurück.

Betrachten wir hier einmal den Spezialfall eines Integervergleichs. Eine Methode dafür sieht wie folgt aus:

Image

Nun gibt es aber eine Reihe von Menschen, die an einem aktuten Nanosekundenverschwendungssyndrom leiden. Bedingt durch meine technische Ausbildung, muss ich mich selbst hier dazu zählen.
Um Laufzeit zu sparen, könnte man nun auf die Folgende, doch sehr naheliegende Version dieser Methode kommen:

Image

Wenn a größer als b ist, so gibt diese Methode einen Wert größer 0, bei a < b einen negativen Wert und bei a = b eine 0 zurück.

Aber stimmt das Wirklich? Immer?

Wahrscheinlich ist die Frage nur mit Nein zu beantworten, denn sonst hätte ich mir sicherlich nicht die Mühe gemacht diesen Artikel zu schreiben. Aber woran krankt es denn nun bei dieser Lösung?

Das Problem welches wir in diesem Fall haben, ist die Beschränkung des Wertebereiches für einen Ganzahlwert. Rein mathematisch betrachtet ist die Formulierung korrekt. Geben wir den Kindern einmal Namen: Sei min der kleinste Wert und max der größte Wert den unsere Ganzzahl annehmen kann. Was passiert nun intern, wenn wir zu max noch eine 1 hinzuaddieren? Es kommt zu einem Überlauf und die Variable kippt auf den Wert min. Dies wird uns bei dieser Lösung zum Verhängnis. Betrachten wir einmal folgenden Aufruf:

Compare( max, min );

Wir erwarten hier, das die Methode einen Wert größer 0 zurück gibt. Wir erhalten jedoch -1. Dies lässt sich auch leicht nachvollziehen. Gehen wir mal von einer 32 Bit breiten Variablen aus. Diese hat einen Wertebereich von -2147483648 bis 2147483647. Wenn wir jetzt min von max abziehen, erhalten wir 2147483647 – (-2147483648) was nach Adam Riese nun 4294967295 ergibt. Das ist in Hex: 0xFFFFFFFF. Was bedeutet alle Bits sind gesetzt. Dies entspricht aber gerade (in der 2er Komplementdarstellung) die -1.

Jetzt könnte uns ja interessieren in wievielen Fällen dies passiert, um eine Abschätzung des Fehler zu geben. Dazu müssen wir uns der (sowas braucht man nur in der Schule-)Mathematik zuwenden. Zuerst müssen wir die Bedingung für gültige Vergleiche aufstellen. Das ist ziemlich einfach. Es dürfen am unteren und oberen Rand keine Überläufe stattfinden, da sonst das Vorzeichen wechselt. Daraus ergibt sich folgende Bedingung:

Image

Wir haben auch noch ein paar Randbedingungen die wir (trivialerweise) einhalten müssen:

Image

Ich möchte hier den allgemeinen Fall für eine n-Bit Breite im 2er Komplement dargestellte Zahl betrachten. Somit ergeben sich die Grenzen für min und max wie folgt:

Image

Nun können wir loslegen. Da a und b zwei unabhängige Variablen sind, kann für jeden Wert b, a Werte zwischen min und max annehmen. Wir haben also eine Matrix über a und b. Betrachten wir erst einmal die gültigen a Werte für ein gegebenes b. Dafür formen wir einfach die ursprüngliche Ungleichung nach a um und erhalten:

Image

Da aber a wegen der oben genannten Randbedingungen auch im Bereich [ min, max ] liegen muss, müssen wir die Grenzen ebenfalls auf diese Grenzen beschränken. Somit erhalten wir folgende Ungleichung:

Image

Da es sich um diskrete Werte handelt können wir nun alle möglichen gültigen Werte für a für ein gegebenes b berechnen:

Image

Uns interessieren allerdings die ungültigen Werte für a. Somit müssen wir von der Gesamtanzahl einer Zeile unsere gültigen Subtrahieren:

Image

Nun die Klammern auflösen und zusammenfassen:

Image

Somit erhalten wir die Anzahl von ungültigen Werten in einer Matrixzeile. Nun müssen wir das ganze nur noch über alle Matrixzeilen aufzummieren:

Image

Diese Formel gibt uns somit an, für wieviele Werte die Vergleichsmethode fehlschlägt. Aber wie kommen wir denn hier nun weiter? Wir haben Maxwertbildungen in einer Summe. Uffz… Nun hallen mir zum ersten mal wieder – nach sehr langer Zeit – die Worte meines Mathematikprofessors in den Ohren…

Sie dürfen keine Skrupel haben Beträge und Maximalwertbildungen in Fallunterscheidungen zu betrachten!

Ok Herr Engels. Dann mal los: Da es sich hier um einfache Maximalwertbildungen handelt, können wir das soger mit ein wenig Überlegung auch ganz einfach durchführen. Dazu ziehen wir die Summe einfach erstmal in drei Teile auseinander:

Image

Betrachten wir mal exemplarisch die 2. Summe. Wir können die Maximalwertbildung ganz einfach auflösen indem wir uns überlegen, für welche b einmal min bzw. b + min verwendet wird. Wann ist also min > b + min? Ganz einfach dann, wenn b < 0 ist. Somit müssen wir die Summe nur in zwei Teile aufteilen. Einen Teil für die negativen b und einen für b >= 0. Das sieht in diesem Fall dann wie folgt aus:

Image

Hier können wir wieder die 2. Summe auseinanderziehen. Auf diese Weise zerlegen wir auch die Zweite Maximalwertsumme. Wenn dann alles in der Ursprungsgleichung eingesetzt wird, kürzt sich eine Menge raus. Folgend also die einzelnen Schritte:

Image

Mit der folgenden Formel, die man in einem durchschnittlichen Formelwerk der Mathematik findet, können die Summen aufgelöst werden:

Image

Somit ergibt sich dann für die Anzahl der ungültigen Wertkombinationen die Formel:

Image

Uns interessiert aber wieviele Kombinationen bezogen auf alle möglichen Kombinationen fehlschlagen. Dazu müssen wir diesen Wert lediglich durch die Anzahl aller möglichen Kombinationen teilen:

Image

Nun können wir für min und max unsere Definitionen von oben einsetzen. Somit erhalten wir nach ein wenig Rechnerei folgendes Ergebnis:

Image

Hier können wir bereits den Wert n für die Bitbreite einsetzen. Aber wir sollten doch lieber einmal versuchen alles zu Vereinfachen. Macht man sich die Mühe und multipliziert das alles schön aus und fast zusammen, so kommt ein doch unerwartetes Ergebnis heraus:

Image

Das bedeutet, das diese Methode unabhängig vom darstellbaren Wertebereich stets in 25% aller Fälle falsch ist… Ups…

Dies ist – wie ich finde – ein sehr schönes Beispiel dafür, wie man sich schnell selbst ganz einfach eine Grube graben kann, nur weil man denkt es ganz geschickt und im “vorbeigehen” besser zu machen. Ausserdem zeigt es, wieviel Spass man mit einer Methode haben kann, die kaum kürzer sein könnte.

Schon in der Bibel steht geschrieben…

Dienstag, 23. Juni 2009

Mein Arbeitskollege hat mich gerade darauf aufmerksam gemacht, das bereits in der Bibel von der Softwareentwicklung die Rede ist. Dort steht bei Johannes 1,1-2: “Am Anfang war das Wort”. Also hat schon Johannes erkannt, das es keinen Sinn macht eine Software zu entwickeln ohne eine Spezifikation bzw. Leistungsbeschreibung in den Händen zu halten.

Image

Somit ist Johannes eher ein idealisierter Softwareentwickler akademischer Nuancierung. Der erste dokumentierte Fall eines mitten im Beruf stehenden Programmieres ist somit die Fantasiefigur des Dr. Faust aus Goethes gleichnamigen Werk. Nachdem Dr. Faust von seinem Softwaremanager ein Projekt zur Umsetzung erhalten hat, ist der folgende Monolog zu lesen:

Im Anfang war das Wort!
Hier stock ich schon! Wer hilft mir weiter fort?

Erfahrungsgrätsche

Dienstag, 23. Juni 2009

In meinen (fast) täglichen Diskussionen höre ich immer wieder die Aussage “Über Programmierstil lässt sich nicht streiten”. Dem möchte ich hier gänzlich widersprechen. Man kann darüber vortrefflich streiten. Außerdem behaupte ich auch noch dreist, dass diese Aussagen von Programmierern getroffen werden, die entweder zu faul, zu überfordert oder extrem eingebildet sind. Ich habe auch noch nie erlebt, dass ein wirklich guter Programmierer einen solchen Satz von sich gegeben hat. Denn ein solcher Satz ist Zeichen von mangelnder Selbstreflexion.

Beim Programmieren reihen wir nicht nach Schema-F irgendwelche Zeichen aneinander. Vielmehr ist es eine Kunst. Ein schöpferischer Akt. Es gilt etwas aus dem Nichts zu erschaffen. Öffnen wir eine neue Datei, so sitzen wir wie ein Maler vor einer weißen Leinwand und sind dann nur unserer eigenen Kreativität und Disziplin unterworfen. Aber welche Kunst kommt ohne Selbstreflexion aus?

Nun zum eigentlichen Thema dieses Beitrags mit dem Schönen und von google beängstigenderweise noch nicht indizierten (!) Titel: Erfahrungsgrätsche:

Wenn wir in einem größeren Projekt arbeiten, so ist es von Natur aus gegeben das junge und unerfahrene Programmierer mit den “alten Hasen” zusammenarbeiten. Oder Kollegen verlassen das Projekt und neue Kollegen kommen hinzu. Was immer einen Erfahrungsverlust bedeutet aber auch einen frischen Wind ins Team bringt. Allen ist (hoffentlich) gemein, dass sie das Projekt erfolgreich beenden möchten. Das schwächste Glied in der Kette ist der Neueinsteiger. Der entweder noch keine Berufserfahrung hat oder sich neu in einem Projekt einarbeitet. Kann man diese “Erfahrungsgrätsche” überbrücken? Ja – ich denke die Einstiegshürde kann man erheblich niedriger gestalten. Dies können aber nur die erfahrenen Programmierer tun. Diese sind hier in die Pflicht zu nehmen. Wie kann das geschehen? Zum einen einmal über die Dokumentation. Darüber brauche ich wohl kein Wort zu verlieren. Zum Anderen aber auch über strukturierten und vor allen Dingen einfachen Quellcode. Der – nur nochmal beiläufig erwähnt – kommentiert sein muss. Die aktuellste Dokumentation ist und bleibt nun einmal der Quellcode selbst.

Was bedeutet denn nun “einfacher Quellcode”. Ist es die Anzahl der Operationen pro Zeile? Die Anzahl der Bedingungen innerhalb einer Abfrage? Ist es einfache Eleganz oder gar die geschickte Ausnutzung der gegebenen Möglichkeiten? Nein – und doch Ja. Hier kommt es auf die Definitionen der einzelnen Begriffe an. Ich für meinen Teil definiere “einfachen Quellcode” als Gehirn gerecht und einfach klassifizierbar. Was auch bedeutet, das der Quellcode nicht den Erfahrungen aus unserem alltäglichen Leben widerspricht.

Was meine ich mit dem ersten Punkt: “Gehirn gerecht klassifizierbar”. Nehmen wir einmal die folgende C/C++ Methode:

Image

Sie ist sehr elegant und nutzt auch einige spezielle Spracheigenschaften aus. Aber ist diese Methode einfach zu verstehen? Wie lange braucht man um zu verstehen was sie tut? Viel wichtiger ist jedoch die Frage: Würde sich ein Anfänger die Zeit nehmen diese im Projektalltag zu verstehen? Wenn ja, wie hoch ist die Wahrscheinlichkeit das ein Anfänger diese Methode auch richtig interpretiert? Mal Hand aufs Herz wie lange brauchtest Du um zu verstehen was die Methode macht? Oder hast Du auch einfach weiter gelesen und es erst gar nicht versucht, weil diese auf den ersten Blick zu komplex erscheint? Genau darin liegt das Problem.

Was macht diese Methode nicht einfach für das Gehirn klassifizierbar? Zum Beispiel die Tatsache das in der äußeren Klammer zwei Größenvergleiche voneinander subtrahiert werden. Dies hat das Gehirn nicht gelernt. Im Alltag gibt es keine Entsprechung dafür. Wie zum Beispiel: ‘Wenn das Auto schneller ist als 100KMh’ subtrahieren wir davon ‘Wenn die Anzahl der Fahrspuren kleiner Drei ist’. In diesem Beispiel knarzt es gehörig im Gebälk unserer Synapsen. Das Gehirn meldet bereitwillig: Das ist totaler Unfug!
Nun ist es aber so, das ein solcher Unfug einfach in jeder Programmiersprache umgesetzt werden kann. Das ist ein schönes Beispiel dafür, das völlig dem Prinzip des “Gehirn gerechten Klassifizierens” widerspricht.

Nun zum Punkt Zwei: “Quellcode soll den Erfahrungen des alltäglichen Lebens nicht widersprechen”.

Im ersten Punkt hat sich bereits ein Beispiel gefunden, was den Erfahrungen des alltäglichen Lebens widerspricht. Die Subtraktion zweier Vergleiche. Dieses schon ziemlich komplexe Beispiel lässt sich aber noch viel weiter runter brechen. Hat z.B. irgendjemand in der Fahrschule einen Satz gehört wie: “Wenn 80KMh kleiner ist als Ihre aktuelle Geschwindigkeit, dann müssen sie den Sicherheitsabstand erhöhen”. Oder hat auf Deinem Giro-Konto Antrag etwa folgendes gestanden: “Wenn 0 größer ist als Ihr aktueller Kontostand, berechnen wir Zinsen”. Ganz sicher nicht! Das widerspricht einfach unserem Alltag und unserer Lernerfahrung. In jeder Programmiersprache kann man aber genau so etwas problemlos formulieren:

Image

Dies hat zur Folge, dass beim überfliegen des Quellcodes entweder Teile einfach falsch wahr genommen und somit falsch Klassifiziert werden oder viel wahrscheinlicher, dass dem Leser diese merkwürdige ungewohnte Struktur ins Auge fällt. Er muss sie dreimal lesen, bevor er sie verinnerlicht hat. Die Augen müssen mehrfach hin und her springen. Dies unterbricht den Lesefluss erheblich. Wobei die andere Formulierung von Oben nach Unten flüssig und ohne Unterbrechung gelesen werden kann:

Image

Deshalb plädiere ich dafür, das Konstrukte beim Abbilden in einer Programmiersprache so weit wie möglich unserer alltäglichen Erfahrung und auch unserem Sprachdenken entsprechen. Die vorausgegangenen Beispiele lassen sich einfach in ein sprachliches Konstrukt Umformen: “Wenn die Geschwindigkeit größer als 80KHm ist, dann wird der Sicherheitsabstand erhöht” oder “Wenn Ihr Kontostand negativ ist, werden Zinsen berechnet”. Somit kann man große Teile Quellcode fast lesen wie seine Muttersprache. Aber versucht dies einmal mit einem meiner Quälkot-Lieblinge. Eure Versuche sind als Kommentare herzlich Willkommen:

Image

Nun am Fuße dieses doch etwas länger geratenen Artikels möchte ich nochmal die erste Methode aufgreifen. Ich vermute das viele immer noch nicht wissen was diese tut, weil sie sich nicht die Zeit genommen haben sie zu verstehen. Ich habe diese Methode umgeschrieben um einmal zu demonstrieren, wie eine Umsetzung aussehen könnte, die diesem Artikel Rechnung trägt:

Image

Wie groß die Zeitersparnis ist, könnt Ihr daran selbst beurteilen. Hier wurde auch lediglich eine Methode betrachtet die ursprünglich nur eine Zeile umfasste. Wie sieht es aus, wenn die Ursprungsmethode 30 Zeilen gleicher Komplexität kapselt?

Als Schlussbemerkung möchte ich noch einmal auf das Gleichnis vom Künstler und dem Programmierer zurückkommen. Nachdem wir unsere eigene kleine weiße Leinwand mit unserem “Kunstwerk” kreiert haben, liegt es im Auge des Betrachters ob er dieses Kunstwerk auch versteht. Experten dieser Kunst können vielleicht die Schönheit und Eleganz in ihrer komplexen Vielfalt erkennen. So in der ersten aber auch in der zweiten Methode. Aber gelingt es auch dem Laien dieser Kunst? Einem Anfänger?
Betrachten wir einmal die Bilder von einem der berühmtesten Maler: Pablo Picasso. Vermag ein Laie die Einzigartigkeit dieser Kunst zu verstehen? Warum ist die Welt von diesen Werken so begeistert, wo doch die Nachbarin von nebenan – in unseren Augen – gleichwertiges malt? Betrachten wir aber Bilder von Michelangelo oder die Mona Lisa von Leonardo da Vinci, da wird selbst einem Kunstbanausen klar, dass es sich um ein echtes und einmaliges Kunstwerk von erster Güte, Ausdruck und Qualität handelt.

Die Frage ist nun: Möchte ich ein Pablo Picasso oder eher ein Michelangelo sein?

Dreimal hinschauen…

Montag, 22. Juni 2009

Quellcode wird einmal geschrieben aber 1000mal gelesen. Bei Fehlersuche/Fehlerbehebung, Erweiterungen oder Wartungsarbeiten allgemein. Deshalb erachte ich die Quellcodequalität persönlich als einen großen und wichtigen Faktor in der Softwareentwicklung. Bei allen Softwaremetriken und Technologien die zum Einsatz kommen, fehlen in meinen Augen stehts zwei Wichtige Elemente: Zum Einen der gesunde Menschenverstand und zum Anderen die richtige Gewichtung der Quellcodequalität. Um Zweitere soll es in dieser neuen Kategorie gehen. Quellcode ist das zentrale Element, womit wir unser Geld verdienen bzw. womit wir uns unsere Nerven ruinieren können. Wir lesen jeden Tag viel Quellcode der uns nicht bekannt ist und versuchen uns dort durchzuwühlen. Kurz gesagt, wir verbringen einen erheblichen Teil der Arbeitszeit damit Quellcode zu lesen. Wäre es nicht schön, wenn wir durch ein wenig Nachdenken und etwas Disziplin diese Arbeitszeit effektiver nutzen könnten? Schönen Quellcode zu schreiben kann uns hier und da eine Minute mehr Zeit kosten. Aber dieser Quellcode wird von vielen Entwicklern zig male gelesen, womit die Summe der Zeitersparnis um ein vielfaches höher ist. Deshalb sollte es zum guten Ton gehören, sich diese Zeit zu nehmen. Andersrum nimmst Du Dir einmal die Zeit, dafür nehmen sich viele Entwickler die Zeit für Dich. Es ist eine Investition die sich lohnt.

Aber nun zum eigentlichen Kern der Sache. Warum ist es notwendig Quellcodestrukturen zu vereinheitlichen und vorallendingen zu vereinfachen? Ganz einfach: Das Gehirn denkt und lernt in Strukturen. Ganz ähnlich wie die Leistungen von Großmeistern im Schach davon abhängen, sich Strukturen einzuprägen und abrufen zu können. Ohne diese Fähigkeit wäre es nicht möglich, das ein Schachmeister 15 von 16 Partien im Simultanschach in rasender Zeit gewinnt.
Nachdem die ersten Lichstrahlen die Retina “befeuern”, so fängt das Gehirn bereits an die gesehenen Dinge zu klassifizieren. Sonst wären wir nicht Lebensfähig: Freund oder Feind, Groß oder Klein, Langsam oder Schnell, Gefährlich oder Harmlos… Alles geschieht in Bruchteilen von Sekunden. Es bedarf danach häufig Mühe das Gehirn vom Gegenteil zu überzeugen. Als Beispiel soll einmal folgender Quellcodeausschnitt dienen:

Image

Man schaut sich den Quellcode an und der erste Eindruck sagt einem: Hey – Alles Okay. Doch irgendwann merkt man, da funktioniert etwas nicht. Aber warum? Es dauert einen kleinen Moment bis man dahinter kommt. Wertvolle Sekunden die sich durch solche Fehlstrukturen schnell aufsummieren. Dieses Beispiel ist so gesehen auch doppelt ärgerlich: Erstens wäre dieser Fehler mit einer passenden Quellcodestruktur erst garnicht entstanden und Zweitens ist der Aufwand zu hoch den Fehler dann noch zu erkennen. Ganz zu schweigen von dem Testaufwand, der Fehlerverwaltung, Fehlernachstellung, Fehlerbehebung, Fehlerbehebung nachtesten etc. Da können sich die 6 Sekunden Zeitersparnis (ich gehe jetzt mal großzügig davon aus, das es nicht länger als 1 Sekunde dauert eine Klammer zu setzen) schnell in größere zweistellige Minutenzahlen verschwenderter Zeit verwandeln.

Die Zeit und die Nerven die man bei einem mehrere 1000 Mann-Jahre großen Projekt einspart, kann sich jeder selbst ausrechnen. Deshalb bin ich ein eiserner Verfechter für sauberen Quellcode, einfachere Strukturen und Augen bzw. Gehrinfreundliches Layout. Dafür setze ich mich täglich ein und werde auch der Diskussionen nicht müde. Auch überdenke ich ständig meine Arbeitsweise und versuche Verbesserungen zu erhaschen und diese zu diskutieren. Das wünsche ich mir von allen Entwicklern. Es gibt keinen goldenen oder DEN richtigen Weg. Doch sollte jeder vermeiden den Holzweg zu gehen!