Wie modelliert man die Ausführungszeit von Algorithmen?

Question

Welche Modelle der Laufzeit des Algorithmus existieren?

Wir erwarten alle Mergesort schneller als bublesort, und beachten Sie, dass mergesort macht O (n Log n) Vergleiche vs O (n) für bubblesort.

Für andere Algorithmen, zählen andere Operationen (als vergleicht und Swaps), wie Pointer-Dereference, Array-Lookup, Arithmetik auf fester Größe ganzer Zahlen usw.

Welche anderen Möglichkeiten, die Ausführungszeit zu modellieren sind ?

Einer, den ich kenne, zählt die Anzahl der gelesenen und auf die Platte geschriebenen Blöcke; Eine ausführliche Beschreibung finden Sie in meiner Antwort auf When does Big-O notation fail?.

Ein anderer zählt die Anzahl der Cache-Misses. Dies erweitert das E/A-Modell, indem alle Ebenen der Speicherhierarchie betrachtet werden.

Ein drittes, für verteilte Algorithmen (z. B. in sichere Multiparty-Berechnung) ist die Menge der über das Netzwerk übertragenen Daten (häufig gemessen in Runden oder Anzahl der Nachrichten) zu zählen.

Welche anderen interessanten Dinge gibt es zu zählen (und nicht zählen!), Um die Leistung eines Algorithmus vorherzusagen?

Auch, Wie gut sind diese Modelle? Soweit ich gehört habe, sind Cache-Oblivious-Algorithmen konkurrenzfähig mit I/O-effizienten Algorithmen für Daten auf der Festplatte, aber nicht für In-Memory-Algorithmen.

Insbesondere: In welchen spezifischen Fällen verfälschen diese Modelle die relative Leistung? Nach meinen eigenen Experimenten beschleunigen Fibonacci-Heaps den kürzesten Pfad von Dijstra nicht (im Gegensatz zu binären Heaps), wenn die Daten klein genug sind, um in den Speicher zu passen.

Answer 1

Sie müssen ein Berechnungsmodell definieren, eine Schätzung der Kosten für jede Operation geben und dann Ihren Algorithmus im Hinblick auf diese Kosten analysieren; Natürlich hängen die Kosten von der jeweiligen Umgebung und den Eigenschaften der zugrunde liegenden Maschine ab, auf der Sie Ihren Algorithmus implementieren möchten. Die Frage ist also wirklich zu allgemein gehalten.

In einem Algorithmus-Kurs, wir einfach davon ausgehen, dass jede Operation kostet 1, so dass wir nur zählen, wie oft wir Schleife; In Algorithmen, die mit dem Hauptspeicher arbeiten, gehen wir davon aus, dass jede Operation, abgesehen von Lesen/Schreiben von E/A, 0 (und Lesen/Schreiben 1) kostet, und so weiter.

Sind diese Modelle eng mit der Realität? Es hängt von der Realität ab: Ihrer Umgebung und Ihrer Maschine.

Ihre Berechnung mit Cache-Misses könnte auf einem Core-Duo korrekt sein, aber falsch mit einem Cell-Prozessor, wo Sie zum Beispiel manuell den Inhalt des SPE-Speichers übertragen müssen.

Answer 2

Ich denke, dass, was auch immer Ihre Basis für die Modellierung der Ausführungszeit/Raum mit O (n ...) Notationen, Sie eine normalisierte Umgebung annehmen. Ich würde denken, dass egal welches Modell Sie angeben, und egal wie viele Variablen Sie messen, um es zu bestimmen ... es gilt nur in einer normalisierten Umgebung. Wenn die Festplatten-I/O im Wettbewerb niedrig ist, ist O (n ...) möglicherweise nicht erforderlich, um diese Gemeinkosten zu berücksichtigen ... wenn Sie meinen Punkt sehen.

So O (n) Modelle typische Leistung in einer normalisierten Umgebung auf dem Eingang n.

Mit der Erweiterung können Sie sagen, dass Plattenlesevorgänge in der Reihenfolge O (n) sind oder dass Speicherzuordnungen die Reihenfolge O (n) usw. sind. Externe Ereignisse, die Druck erzeugen (wie zum Beispiel die Planung), sollten keine Rolle im Modell der typischen Zeit/Raum/Vorkommen von irgendetwas spielen.

Oder vielleicht vermisse ich Ihren Punkt (was ich vermute ich könnte).

Answer 3

Für die Echtzeitplattformen, an denen ich arbeite, finde ich in letzter Zeit, dass das Kopieren großer Datenmengen (zB im KB-Bereich, nicht im MB-Bereich) tatsächlich viel schneller ist, als ich es erwartet habe. Wahrscheinlich hat das mit den großen Caches zu tun, die heute im Einsatz sind, oder vielleicht nur mit der rasend schnellen Prozessorgeschwindigkeit. Aber der Effekt ist, dass man sich nicht mehr darum bemühen sollte, seinen Code zu sehr zu pervertieren, nur um Datenkopien zu vermeiden.

Die Dinge, auf die ich wirklich achten muss, sind Gerätezugriffe und Kontextwechsel. Je weniger davon, desto besser.

Die Zeiten, in denen die "Zero Buffer" -Gerätetreiber mit der Geschwindigkeit übereinstimmten, sind vorbei.