Algorithmen bewerten und vergleichen in Java

Worum geht´s?

Wenn wir davon ausgehen, dass bei verschiedenen Problemstellungen verschiedene Algorithmen zu einer Lösung führen – woher wissen wir dann, welcher Algorithmus der bessere ist? Ist das subjektiv? Egal? Hauptsache, er funktioniert?

Mitnichten.

Ein Werkzeug zur Bewertung eines Algorithmus kann das „magische Dreieck“ sein.

1. Das „magische Dreieck“ eines Algorithmus

Ein jeder Algorithmus sollte 3 Ziele möglichst gut erreichen:

• Gute Performance (Schnelligkeit)
• Wenig Speicherverbrauch
• Klarheit (Wie verständlich ist der Code?)

1.1 Die Vorstufe: überall verbessern soweit wie möglich

Bis zu einem gewissen Grad lassen sich an allen drei Ecken des Dreiecks Verbesserungen erzielen, ohne dass die anderen Ecken darunter leiden – etwa indem Code Conventions beachtet werden, oder auf Clean Code geachtet wird.

Aber es gibt den Punkt, an dem eine jede weitere Verbesserung in der Performance entweder zu mehr Speicherverbrauch führt (etwa, indem mehr Zwischenergebnisse gespeichert werden) oder zu weniger Klarheit (z.B. indem abgefahrene mathematische Konzepte genutzt werden, die kein Normalsterblicher mehr versteht).

Umgekehrt führt eine Speicherverbrauchs-Optimierung oft zu Nachteilen an den anderen drei Punkten.

Mehr Klarheit im Code macht ihn zwar einfacher zum warten und erweitern, aber oft auch langsamer, weil mehr Methoden-Aufrufe z.B. auch immer Auswirkung auf Performance und Speicherverbrauch haben.

Wo sollte also im Zweifelsfall „gespart“ werden?

1.2 Wo noch weiter sparen, wenn jedes Sparen an anderer Stelle wehtut?

Das kommt darauf an, um welche Anwendung es geht, und unter welchen Voraussetzungen das Programm eingesetzt werden wird.

Haben wir nur sehr begrenzten Speicherplatz, eine Unzahl an Datensätzen (z.B. Nutzer-Daten von Facebook mit >2 Mrd Nutzern oder z.B. schlechte/teure Internet-Verbindungen, wo jede zusätzliche Daten-Übertragung ein Problem ist? Dann wird vermutlich der Speicherverbrauch ein Thema sein.

Haben wir ein selbst-fahrendes Auto, das anhand von Live-Kamera-Bildern innerhalb von Millisekunden entscheiden muss, ob der Fleck im Bild ein Staubkorn oder ein Kleinkind ist, dann macht eine 0,1 Sekunden spätere Bremsung all den Unterschied den es gibt. Hier heißt es maximale Performance, auch auf Kosten der anderen beiden Seiten des Dreiecks.

Arbeiten viele Mitarbeiter gemeinsam am selben Code, und ist es absehbar, dass dieser oft verändert und erweitert werden muss, womöglich auch im Abstand mehrerer Monate oder Jahre, so dass es wichtig ist, sich möglichst rasch wieder im Code zurecht zu finden? Das spricht für eine Betonung der Klarheit.

2. Wie du die Performance von Algorithmen im Vorfeld vergleichen kannst

Neben dem „magischen Dreieck“ gibt es noch eine einfache, aber sehr nützliche Methode, Algorithmen zu vergleichen.

Die meisten Algorithmen haben in irgendeiner Form Schleifen eingebaut, und die Performance dieser Algorithmen basiert zu einem guten Teil darauf, wie oft eine solche Schleife durchlaufen werden muss.

Weil das bei verschiedenen Durchläufen auch unterschiedlich oft sein kann, macht es Sinn, sich die drei Extremfälle durchzuüberlegen:

• Im besten Fall
• Im schlechtesten Fall
• Im Durchschnitt

2.1 Brute Force-Algorithmus

Nehmen wir an, wir haben ein Programm, dass ein Passwort aus Zahlen mit insgesamt 4 Stellen erraten soll. Insgesamt gibt es daher 10^4 Möglichkeiten, wie so ein Passwort beschaffen sein kann, nämlich alles von 0000 bis 9999.

Ein klassischer Algorithmus zum Knacken eines solchen Passworts ist der Brute Force Algorithmus. Dieser würde in unserem Fall einfach alle Möglichkeiten von 0000 über 0001, 0002, 0003 usw. bis hin zu 9999 durchprobieren, bis er die richtige Kombination erwischt hat.

Bei einem zufälligen Passwort zwischen 0 und 9999 dauert es mit diesem Algorithmus

• Im besten Fall: 1 Versuch (wenn das Passwort 0000 ist)
• im schlechtesten Fall: 10000 Versuche (wenn das Passwort 9999 ist)
• Im Durchschnitt: 5000 Versuche (wenn das Passwort irgendwo dazwischen ist)

2.2 Zufalls-Algorithmus

Vergleichen wir das Ganze mal mit einem Algorithmus, der einfach aus den Möglichkeiten ein zufälliges Passwort generiert und nachschaut, ob er zufällig genau das Passwort erraten hat. Wenn nicht, erzeugt er erneut ein zufälliges und schaut erneut nach, ob es das ist. Das macht er so lange, bis er es erraten hat.

Was passiert hier in unseren Fällen:

• Im besten Fall: 1 Versuch (wenn er es zufällig genau errät)
• Im schlechtesten Fall: Unendlich lange (wenn er zufällig nie das richtige erwischt)
• Im Durchschnitt: Vom Zufall abhängig, aber auf Dauer weit über 5000 Versuche

Das Haupt-Problem am Zufalls-Algorithmus ist, dass er mehrfach dasselbe Passwort versuchen kann.

Würden wir uns in einer Liste speichern, welche wir schon geraten haben, hätten wir zwar dieses Problem „gelöst“, aber hätten a) mehr Speicherverbrauch und b) müssten wir ständig überprüfen ob das zufällig neu erstellte Passwort schon geraten wurde oder nicht.

Vermutlich bräuchte der Algorithmus weniger oder gleich viele Durchläufe der Haupt-Schleife als unser Brute-Force-Algorithmus, aber aufgrund der Listen-Überprüfungen bräuchte er wahrscheinlich trotzdem erheblich länger als der andere.

In diesem Fall „gewinnt“ der Brute Force-Algorithmus.

Man kann sich diese Szenarien (bester Fall, schlechtester Fall, Durchschnitt) für die meisten Fälle auch ganz konkret mathematisch durchrechnen (und Mathematiker machen das tatsächlich gerne, es gibt sogar Preise dafür).

Für dich relevant ist aber vor allem ein grobes Gefühl dafür, wo die Problemfelder bei deinem Algorithmus sein könnten. Gibt es einen schlechtesten Fall, bei dem der Algorithmus unendlich lange läuft? Dann solltest du in den meisten Fällen noch etwas an ihm ändern 😉

Diskussion zum Tutorial