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:
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:
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:
Wir haben auch noch ein paar Randbedingungen die wir (trivialerweise) einhalten müssen:
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:
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:
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:
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:
Uns interessieren allerdings die ungültigen Werte für a. Somit müssen wir von der Gesamtanzahl einer Zeile unsere gültigen Subtrahieren:
Nun die Klammern auflösen und zusammenfassen:
Somit erhalten wir die Anzahl von ungültigen Werten in einer Matrixzeile. Nun müssen wir das ganze nur noch über alle Matrixzeilen aufzummieren:
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:
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:
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:
Mit der folgenden Formel, die man in einem durchschnittlichen Formelwerk der Mathematik findet, können die Summen aufgelöst werden:
Somit ergibt sich dann für die Anzahl der ungültigen Wertkombinationen die Formel:
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:
Nun können wir für min und max unsere Definitionen von oben einsetzen. Somit erhalten wir nach ein wenig Rechnerei folgendes Ergebnis:
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:
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.
