Programmiererpraxis
Die Computerwissenschaft
.jpg "Ted Neward")
Seit Jahren höre ich, wie Kollegen von sich als „Computerwissenschaftler“ sprechen. Ich hörte auch, dass „ein Gebiet, in dessen Bezeichnung 'Wissenschaft' nicht vorkommt, nicht wirklich eine Wissenschaft ist“. Natürlich hat eine ziemlich große Anzahl von Leuten auf meinem Gebiet keine formale Ausbildung in Computerwissenschaft, und eine ebenfalls ziemlich große Anzahl sieht die Arbeiten, die von den Universitäten und aus den Büros von Hochschulprofessoren kommen, mit Geringschätzung an – und das mit einem gewissen Recht. Wann hat Ihnen das letzte Mal eine Menge griechischer Symbole, die vorgaben, ein Typsystem zu beschreiben, geholfen, eine Branchenanwendung einsatzbereit zu machen?
Ich kenne eine Reihe unglaublich intelligenter Leute, und einer davon ist Joe Hummel, jemand, der zu Recht den Titel Computerwissenschaftler beanspruchen kann, aufgrund seines Doktortitels und überhaupt. Ich bat ihn, mit mir zusammen diesen Artikel zu schreiben, um die Computerwissenschaft zu untersuchen. Ich dachte, es könnte interessant sein, mit einigen einfacheren Teilgebieten der Computerwissenschaft zu beginnen und sich dazu vorzuarbeiten, wie eine Kenntnis der Theorie hinter einigen dieser Teilgebiete Ihnen das Leben als praktischer Programmierer durchaus etwas erleichtern kann.
In dieser Ausgabe behandeln wir die klassische „Groß O“-Lösung, die uns eine konsistente Möglichkeit zur Beschreibung eines einfachen Konzepts gibt: Wie viele Ressourcen (Zeit, Speicherplatz, Strom usw.) benötigt der Computer, um ein gegebenes Programm auszuführen? Diese Berechnung wird Algorithmusanalyse genannt, und hat zum Ziel, den von Ihnen gewählten Algorithmus in eine bestimmte mathematische Kategorie zu platzieren. Warum ist das so? Damit Sie den besten für eine Situation auswählen können. Es gibt viele Kategorien, wobei jede folgende Kategorieeinen Sprung beim Ressourcenverbrauch darstellt. Wir werden den Schwerpunkt auf die Ausführungszeit legen, und nur auf die ersten drei Kategorien: O(1), O(lgN) und O(N). Wie üblich bezeichnet N die Anzahl der von dem Algorithmus verarbeiteten Datenelemente. Eine zusammenfassenden Darstellung, worauf dies hinausläuft, finden Sie in Abbildung 1, in der die Ausführungszeit hervorgehoben wird, die Sie für jede Kategorie erwarten können, wenn N zunimmt.
.png)
Abbildung 1: Ausführungszeiten, wenn die Anzahl der verarbeiteten Elemente (N) zunimmt
Ein Algorithmus der Ordnung N wird O(N) geschrieben, ausgesprochen „Groß O von N“ und auch bekannt als „linear“. Wenn N Datenelemente geben sind, nimmt ein O(N)-Algorithmus die Ordnung von N Zeitschritten an. Ein Algorithmus der Ordnung log N wird O(lgN) geschrieben, ausgesprochen „Groß O von log N“ und als „logarithmisch“ bezeichnet. Wenn N Datenelemente gegeben sind, nimmt ein O(lgN)-Algorithmus die Ordnung von log2(N) Zeitschritten an (viel weniger). Ein Algorithmus der Ordnung 1 wird O(l1) geschrieben, ausgesprochen „Groß O von 1“ und als „konstant“ bezeichnet. Für N Datenelemente, nimmt ein O(1)-Algorithmus eine konstante Anzahl von Zeitschritten an (noch weniger). Sehen Sie sich noch einmal Abbildung1 an. Was könnte diese Grafik sonst noch aussagen? Beachten Sie, dass, wenn N z. B. verdoppelt wird, ein linearer Algorithmus doppelt soviel Zeit braucht.
Sehen wir uns ein Beispiel an, wie sich dies im wirklichen Leben auswirkt, und wie die Kenntnis von etwas Algorithmusanalyse eine große Auswirkung haben kann. Angenommen, Sie erhalten eine Protokolldatei, die auf Entsprechungen zu einer Liste verdächtiger IP-Adressen durchsucht werden soll. Einfach genug:
List<string> suspicious = BuildList(); /* step 0 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.Contains(ipaddr)) /* step 2 */
matches++; /* step 3 */
}
Wie kategorisieren wir die Zeitkomplexität dieses Verfahrens? Nehmen wir an, die Protokolldatei enthält M Zeilen und N verdächtige IP-Adressen. Das Aufbauen einer unsortierten Liste von N Elementen (Schritt 0) führt zu einmaligen Kosten von O(N). Die Schleife führt N Iterationen durch, daher sind die Kosten der Schleife O(M * Kosten einer Iteration). Jede Iteration führt drei grundlegende Schritte aus:
- die Zeile analysieren
- die Liste durchsuchen
- die Entsprechungen erhöhen, wenn eine Entsprechung gefunden wird
Analytisch herangehen
Der intellektuelle Aspekt der Algorithmusanalyse liegt darin, zu lernen, was gezählt werden soll und was nicht gezählt werden soll. Während es zum Beispiel aufwändig sein kann, eine Zeile zu analysieren – vielleicht durch Anwendung eines regulären Ausdrucks – beansprucht es einen relativ zu den Daten konstanten Zeitbetrag. Anders gesagt, die zum Analysieren einer Zeile benötigte Zeit bleibt völlig unverändert, ob nun M oder 2 M Zeilen in der Datei vorhanden sind. Es ändert sich auch nicht, wenn N oder 2 N verdächtige IP-Adressen vorhanden sind. Daher sagen wir, dass Schritt 1 und 3 eine c (konstante) Zeit benötigen. Schritt 2 jedoch, die Durchsuchung der Liste, ändert sich im Verhältnis zur Anzahl der verdächtigen IP-Adressen:
if (suspicious.Contains(ipaddr))
Die Contains-Method führt eine lineare Suche durch, beginnend mit dem ersten Element und solange, bis entweder eine Entsprechung gefunden oder das Ende der Liste erreicht wird. (Wie können wir das wissen? Auf eine von drei Arten: wir haben es getestet, wir haben uns den Quellcode angesehen oder die MSDN-Bibliotheksdokumentation teilt es uns mit.)
Bei zufälligen Daten durchsuchen wir die halbe Liste, wofür wir N/2 Schritte benötigen. Dieses würde für die meisten Fälle gelten, in diesem besonderen Fall besteht ein stärkeres Argument darin, dass die meisten Adressen in der Protokolldatei vertrauenswürdig sind, da unser Webserver weder eine Bank noch die Webseite eines Präsidentschaftskandidaten ist. Das heißt, dass es nicht gleichmäßig wahrscheinlich ist, dass ein gegebener Client nicht vertrauenswürdig ist, und dass die große Mehrheit der Suchen die Liste durchläuft, ohne eine Entsprechung zu finden und N Schritte benötigt.
Da die Konstanten wegfallen, wenn die Ordnung berechnet wird, ist die Suche in jedem Fall O(N) und ergibt eine Komplexität von O(M * N) für die Schleife. Dies wiederum ergibt eine algorithmische Gesamtkomplexität von:
= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)
Daher erfordert Version 1 unserer Lösung eine Zeit von O(MN).
'Daten, Daten, Daten! Ohne Ton kann ich keine Ziegel machen!'
Die erste Frage, die Sie sich stellen sollten, ist: „Brauchen wir einen besseren Algorithmus?“ M ist normalerweise groß, in der Größenordnung von Millionen (möglicherweise Milliarden) von Zeilen. Daran können Sie nicht viel ändern, denn Sie müssen jede Zeile anfassen, um sie zu durchsuchen. Wenn N, die Anzahl der verdächtigen IP-Adressen, klein ist (etwa N < 100), ist Ihre Arbeit getan. Bei den heutigen schnellen Computern ist kaum ein messbarer Unterschied zwischen m Schritten und 100 M Schritten. Wenn N jedoch größer wird (zum Beispiel N >> 100 oder deutlich mehr als 100), lohnt es sich, andere Suchalgorithmen in Betracht zu ziehen.
Außer natürlich, wenn Sie über ein sehr großes Hardwarebudget verfügen. (Manchmal sogar dann.)
Ein effizienterer Algorithmus ist die binäre Suche, die in die Mitte springt und dann links oder rechts sucht, je nachdem, ob das zu suchende Element kleiner oder größere als das Mittelelement ist. Durch das jedesmalige Teilen des Suchbereichs in Hälften zeigt der Algorithmus ein O(lgN)-Verhalten. Was bedeutet dies in der Praxis? Wenn N = 1.000 Elemente gegeben sind, hätte die binäre Suche schlechtestenfalls die Größenordnung von 10 Zeitschritten (210 ≈ 1.000), während eine lineare Suche 1.000 erfordern würde. Für N = 1 Million ist der Unterschied noch dramatischer – in der Ordnung von 20 Zeitschritten gegenüber 1 Million. Die wichtigste Abwägung besteht darin, dass für die binäre Suche die Daten in sortierter Ordnung vorliegen müssen. Hier ist das Protokolldatei-Suchprogramm, zur Verwendung mit der binären Suche umgeschrieben:
List<string> suspicious = BuildList(); /* step 0 */
suspicious.Sort(); /* step 0.5 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.BinarySearch(ipaddr) >= 0) /* step 2 */
matches++; /* step 3 */
}
Das Sortieren der verdächtigen Liste (Schritt 0,5) repräsentiert einmalige Kosten O(NlgN), während die Kosten pro Iteration durch die effizientere binäre Suche von O(N) auf O(lgN) reduziert werden (Schritt 2). Dies ergibt eine algorithmische Gesamtkomplexität von:
= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)
In unserem Szenario, in dem M >> N ist, fungiert N mehr wie eine kleine Konstante, wenn sie zu M addiert wird, und daher erfordert Version 2 unserer Lösung ungefähr eine Zeit von O(MlgN). Also? Für N = 1.000 verdächtige IP-Adresse haben wir soeben die Ausführungszeit von einer Größenordnung von 1.000 M Zeitschritten auf 10 M reduziert, was 100x schneller ist. Die zusätzliche Sortierzeit von ungefähr 10.000 Zeitschritten (O(NlgN)) wird durch die wiederholten Einsparungen bei der Suchzeit mehr als ausgeglichen.
Gehen wir Hashen!
Wenn Sie etwas über die Daten wissen, die Sie suchen, können (und sollten) Sie eine Hashtabelle einrichten. Das Hashing reduziert die durchschnittliche Suchzeit auf O(1) – und etwas besseres können Sie gar nicht tun. Dies geschieht durch Zuordnung eines einzelnen Wertes zu den Elementen, die in der Tabelle gespeichert sind, wobei dieser Wert durch eine Hashfunktion erstellt wird. Die Hauptbedingung für das Hashing ist das Vorhandensein einer guten Hashfunktion, die die Suchdaten über einen Bereich von ganzen Zahlen zuordnet, mit wenigen Kollisionen (doppelten Zuordnungen). Unser überarbeitetes Protokolldateiprogramm (Version 3) nutzt die im Microsoft-.NET Framework integrierte Unterstützung für effektives Stringhashing:
Dictionary<string, int> suspicious = BuildHashTable(); /* step 0 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.ContainsKey(ipaddr)) /* step 2 */
matches++; /* step 3 */
}
Das Aufbauen der Hashtabelle (Schritt 0) führt zu einmaligen Anfangskosten von O(N). Dies ergibt eine algorithmische Gesamtkomplexität von:
= O(build + loop)
= O(N + M * 1)
= O(N + M)
Im Fall unseres Szenarios mit M >> N ist Version 3 unsere schnellste Lösung, mit einer Zeit von ungefähr O(M). Für N = 1.000 verdächtige IP-Adresse haben wir soeben die Ausführungszeit nochmals um den Faktor 10 reduziert, d. h. 1000x schneller als unsere ursprüngliche Version. Und das bemerkenswerte an diesem Verfahren besteht darin, dass bei noch größeren Werten für N, etwa 10.000 oder sogar 100.000, die Ausführungszeit gleich bleibt, in der Größenordnung von M Zeitschritten.
Wo ist also der Haken? Bei Version 2 und der binären Suche ist es einfach: Die Liste der IP-Adressen muss zuerst sortiert werden. In dieser Version mit Hashing sind drei Probleme zu berücksichtigen: das Erstellen einer effektiven Hashversion, die anfänglichen Erstellungskosten und der größere Speicherbedarf. Das Entscheidende ist die Hashversion. Ein effektive Hashversion verteilt die Daten mit einem Minimum an Kollisionen über die Tabelle und beseitigt die Notwendigkeit einer zusätzlichen Suche nach der anfänglichen Verteilung in der Tabelle. Eine derartige Konstruktion bietet anfängliche Konstruktionskosten von O(1) pro Datum oder O(N), dasselbe wie lineare Suche. Diese Effektivität bringt aber normalerweise in der Nachbarschaft einen Auslastungsfaktor von 10 Prozent mit sich, das bedeutet, die Daten nehmen nur 10 Prozent der Tabelle ein. Das Hashing erfordert also einen 10x größeren Speicherplatz als die lineare oder die binäre Suche, obwohl sie formal immer noch O(N) ist, wie die anderen.
Nochmals, weshalb tun wir das alles?
Nach dieser ganzen Pseudomathematik könnte es einem nicht in Computerwissenschaft Promovierten vorkommen, als hätten wir viele theoretische Manipulationen durchgeführt und wären zwar der Meinung, eine effiziente Lösung gefunden zu haben, hätten dabei aber viele Konstanten beseitigt. Dies führt uns zu der Eine-Million-Dollar-Frage: „Zahlt sich unsere theoretische Lösung in der Praxis wirklich aus?“ Eine faire Frage, besonders wenn man das eigentliche Ziel dieses Artikels berücksichtigt, nämlich, Sie zur Verwendung von Algorithmusanalyse zu ermutigen, um konkurrierende Verfahren zu evaluieren, bevor Sie einen Code schreiben (wenn Sie dies nicht bereits tun).
Ich habe schon oft gesehen, wie Engineers stundenlang, manchmal sogar tagelang herumsaßen und diskutierten, ob Verfahren A besser als Verfahren B sei. Aber die Leute führen nur selten eine schnelle Algorithmusanalyse durch.
Nachdem wir also jetzt die Analyse durchgeführt haben, wollen wir einige Tests durchführen und sehen, was praktisch geschieht. Um dies zu tun, haben wir zufällige Protokolldateien mit M Einträgen erstellt und diese Dateien dann anhand einer zufällig erstellten IP-Adressenliste durchsucht. (Die vollständigen Quell- und Eingabedateien sind verfügbar unter bit.ly/srchlogfiles.)
Zur Wiederholung, angenommen, dass M >> N, haben wir die algorithmischen Komplexitäten abgeleitet, die in Abbildung 2 dargestellt sind.
Abbildung 2: Algorithmische Komplexitäten unter der AnnahmeM >> N
| Zeit (t) | |
| Version 1: Verwendung linearer Suche | O(M * N) |
| Version 2: Verwendung binärer Suche | O(M * lgN) |
| Version 3: Verwendung von Hashing | O(M) |
Für unsere Tests haben wir M auf 1 Million festgesetzt und N für jeden Test verdoppelt: 128, 256, 512 usw. Die Verdoppelung von N hebt die Leistungscharakteristika der Suchalgorithmen hervor. Wenn unsere Analyse korrekt ist, sollte sich jedesmal, wenn N verdoppelt wird, die Ausführungszeit ändern, wie in Abbildung 3 gezeigt.
Abbildung 3: Vorausgesagte Änderung der Ausführungszeit, wennNverdoppelt wird
| Zeit für 2N: | |
| Version 1 | O(M * 2 * N) => 2 * O(M * N) => 2t |
| Version 2 | O(M * lg(2N)) => O(M * (lg2 + lgN)) => O(M * (1 + lgN) => O(M + M * lgN) => M + O(M * lgN) => M + t |
| Version 3 | O(M) => t |
In anderen Worten, Version 1 sollte sich zeitlich verdoppeln (2t), Version 2 sollte weitere M Zeitschritte benötigen (t + M), und Version 3 sollte keine zusätzliche Zeit benötigen (t). Abbildung 4 zeigt die tatsächlich aufgezeichneten Zeiten (in Sekunden).
Abbildung 4: Tatsächlich aufgezeichneten Zeiten (Sekunden)
| M | N | Version 1 | Version 2 | Version 3 |
| 1,000,000 | 128 | 3.81 | 2.88 | 2.15 |
| 256 | 5.65 | 2.98 | 2.15 | |
| 512 | 9.39 | 3.11 | 2.17 | |
| 1,024 | 16.78 | 3.23 | 2.19 | |
| 2,048 | 31.52 | 3.36 | 2.19 | |
| 4,096 | 61.18 | 3.49 | 2.28 | |
| 8,192 | 120.63 | 3.68 | 2.39 | |
| 16,384 | 238.86 | 3.95 | 2.54 | |
| 32,768 | 473.91 | 4.34 | 2.89 |
Wie Sie in Abbildung 4 sehen, verdoppelt sich Version 1 – die auf der linearen Suche basiert – wirklich in der Zeit, wenn sich N verdoppelt. Dies ist in den meisten Situationen wahrscheinlich ein Nachteil.
Version 2 – die auf der binären Suche basiert – ist um Größenordnungen schneller als Version 1 und wächst wesentlich langsamer an. Die Wachstumsrate ist schwieriger zu quantifizieren, da sie von der Zeit TM für die Ausführung von M Operationen abhängt, die im Bereich von 0,1 bis 0,3 Sekunden liegen kann. Nach unserer Analyse sollte Version 2 mit einer konstanten TM-Rate anwachsen, wenn sich N verdoppelt, dies scheint jedoch nicht der Fall zu sein; dies könnte am erhöhten Cachedruck (und daher Cacheverlusten) liegen, wenn N anwächst.
Schließlich bestätigt Abbildung 4, dass Version 3 tatsächlich der schnellste Algorithmus ist, mit ungefähr derselben Ausführungszeit, unabhängig von N (obwohl wiederum nicht ganz konstant).
Die Balance finden
Aus der Sicht eines Pragmatikers ist es nicht klar, dass die Verbesserung von Version 2 zu Version 3 mehr als eine bescheidene Anstrengung lohnt, trotz der Einsparung von mehr als einer Sekunde. Die potenziellen Einsparungen machen wirklich keinen großen Unterschied aus, außer wenn wir es mit wirklich großen M- oder N-Werten zu tun haben (wobei zu bedenken ist, dass Hashing 10x mehr Speicherplatz braucht, um die IP-Adressen zu speichern). Und dies führt zum letzten Punkt: wissen, wann man mit der Suche nach Optimierung aufhören sollte. Es könne eine interessante Herausforderung für einen Programmierer sein, den absolut schnellsten Algorithmus zur Ausführung einer bestimmten Operation zu finden, aber außer wenn diese Operation für den Benutzer absolut zentral und vorrangig ist, kann die Zeit, die zur Optimierung der letzten Sekunden aufgewendet wird, wesentlich besser für andere Aufgaben verwendet werden. Der Sprung von Version 1 zu Version 2 ist sicherlich die Zeit wert (es handelt sich um Einsparungen von 10.000 Prozent), aber wie in allen Dingen, muss der Programmierer eine Balance finden. Manchmal muss die Theorie der Praxis nachgeben, in anderen Fällen jedoch hilft die Theorie, zu bestimmen, wo wir unsere Anstrengungen in die Praxis umsetzen sollten.
Viel Spaß beim Programmieren!
Ted Neward ist Berater für Softwarearchitektur bei Neudesic LLC. Er hat mehr als 100 Artikel geschrieben und hat mehrere Bücher allein und in Zusammenarbeit mit anderen geschrieben, darunter „Professional F# 2.0“ (Wrox 2010). Er ist ein C#-MVP und spricht auf Konferenzen in der ganzen Welt. Er berät und hilft regelmäßig – Sie können ihn unter ted@tedneward.com oder Ted.Neward@neudesic.com erreichen, wenn Sie daran interessiert sind, das er mit Ihrem Team zusammenarbeitet, oder Sie können seinen Blog unter blogs.tedneward.com lesen.
Joe Hummel ist privater Berater, Mitglied des technischen Personals bei Pluralsight LLC, Trainer für MVP-Training.net und Gastwissenschaftler im Institut für Computerwissenschaft an der University of California, Irvine. Er hat einen Ph.D. der UC Irvine auf dem gebiet des Hochleistungscomputings und ist an Allem interessiert, was damit zu tun hat. Er wohnt in der Umgebung von Chicago, und wenn er nicht segelt, ist er zu erreichen unter joe@joehummel.net.