Welches Rechenmodell ist „das Beste“?

1937 beschrieb Turing eine Turingmaschine. Seitdem wurden viele Berechnungsmodelle beschrieben, um ein Modell zu finden, das einem echten Computer ähnelt, aber dennoch einfach genug ist, um Algorithmen zu entwerfen und zu analysieren.

Als Ergebnis haben wir Dutzende von Algorithmen für z. B. das SORT-Problem für verschiedene Rechenmodelle. Leider können wir nicht einmal sicher sein, dass eine Implementierung eines Algorithmus mit der Laufzeit O (n) in einem Wort-RAM mit zulässigen Bitvektoroperationen schneller abläuft als eine Implementierung eines Algorithmus mit der Laufzeit O (n⋅logn) in ein Wort RAM (ich spreche natürlich nur von "guten" Implementierungen).

Ich möchte also verstehen, welches der vorhandenen Modelle "das Beste" für die Entwicklung von Algorithmen ist, und ich suche nach einer aktuellen und detaillierten Übersicht über Rechenmodelle, die Vor- und Nachteile von Modellen und deren Realitätsnähe aufzeigt.

Ich habe das Standard-Word-RAM-Modell immer als "das Beste" in Ihrem Sinne angesehen. Jeder, der gelernt hat, in einer Sprache wie C zu programmieren (oder lose Entsprechungen wie Java usw.), denkt genau an dieses Modell, wenn er an einen Computer denkt.

Natürlich benötigen Sie manchmal Verallgemeinerungen, abhängig von den Regimen, in denen Sie arbeiten. Das externe Speichermodell ist ein wichtiger Aspekt, den Sie berücksichtigen sollten. Dies gilt nicht nur für die Arbeit mit Datenträgern, sondern auch für das Verständnis des Cache (das Sie dazu zwingt, sich um ihn zu kümmern). Eine zu ernsthafte Behandlung kann natürlich auch zu unsinnigen Ergebnissen führen, da das reine externe Speichermodell keine Berechnung berücksichtigt. Eine andere Verallgemeinerung des Wort-RAM ist die Parallelität, aber da sind wir im Moment alle ein bisschen verwirrt :)

Ein Algorithmus mit einer Laufzeit von wird sicherlich schneller ausgeführt als einer mit einer Laufzeit von . Es ist eine mathematische Tatsache, dass die erstere für große schneller ist :) Ihre Problemgröße ist möglicherweise einfach nicht groß genug, damit dies eine Rolle spielt. Da Sie die Sortierung ansprechen, kann ich Ihnen versichern, dass es sehr schwierig sein wird, die Radix-Sortierung mit einem vergleichsbasierten Algorithmus für vernünftiges zu übertreffen .O ( n lg n ) n $O(n)$$O(n \lg n)$$n$$n$

Eine abschließende Bemerkung zu Algorithmen und "Realität": Denken Sie immer daran, was Sie erreichen wollen. Wenn wir mit Algorithmen arbeiten, versuchen wir, die schwierigsten Probleme zu lösen (z. B. SAT mit 50 Variablen oder Sortieren von Milliarden Zahlen). Wenn Sie versuchen, 200 Zahlen zu sortieren oder SAT nach 20 Variablen zu lösen, benötigen Sie keinen ausgefallenen Algorithmus. Deshalb sind die meisten Algorithmen in der Realität trivial. Das sagt nichts Schlechtes über algorithmische Forschung aus - wir interessieren uns zufällig für dieses ungewöhnliche 1/1000 der wirklichen Probleme, die zufällig schwierig sind ...

Es gibt kein völlig zufriedenstellendes Rechenmodell, mit dem sich Algorithmen traurigerweise analysieren lassen, selbst wenn man es für eine traditionelle Umgebung hält. Dies setzt voraus, dass alle Daten leicht zugänglich sind und der Arbeitsraum praktisch unbegrenzt ist.

Die Multi-Tape-Turing-Maschine ist sicherlich theoretisch gut spezifiziert und viele Algorithmen wurden im Laufe der Jahre in diesem Modell entworfen und analysiert. Für manche ist es jedoch nicht eng genug, wie echte Computer funktionieren, um ein wirklich gutes Modell für das 21. Jahrhundert zu sein. Andererseits ist das Wort-RAM-Modell populär geworden und scheint die Arbeitsweise moderner Computer genauer zu erfassen (Operationen an Wörtern, nicht Bits, ständiger zeitlicher Zugriff auf Speicherstellen). Es gibt jedoch Aspekte, die nicht ideal sind. Zum Beispiel gibt es kein Ein-Wort-RAM-Modell. Zunächst muss festgelegt werden, welche Operationen an Wörtern in konstanter Zeit zulässig sein sollen. Hierfür gibt es viele Möglichkeiten, ohne dass eine einzige Antwort akzeptiert wird. Zweite, Die Wortgröße w wird normalerweise so eingestellt, dass sie mit der Eingabegröße wächst (dh mindestens so schnell wie log (n)), damit jedes Element im Speicher mit einer konstanten Anzahl von Wörtern adressiert werden kann. Dies bedeutet, dass man sich eine unendliche Klasse von Maschinen vorstellen muss, auf denen Ihr Algorithmus ausgeführt wird, oder noch schlimmer, dass sich die Maschine ändert, wenn Sie mehr Daten einspeisen. Dies ist zumindest für meine Schüler ein beunruhigender Gedanke. Schließlich erhalten Sie mit dem Wort-RAM-Modell etwas überraschende Komplexitätsergebnisse, die möglicherweise nicht mit denen übereinstimmen, die man als Student lernt. Beispielsweise ist die Multiplikation von zwei n-Bit-Zahlen in diesem Modell O (n) -Zeit, und das einfache Einlesen einer n-Bit-Zeichenfolge ist plötzlich eine sublineare Zeitoperation. Dies bedeutet, dass man sich eine unendliche Klasse von Maschinen vorstellen muss, auf denen Ihr Algorithmus ausgeführt wird, oder noch schlimmer, dass sich die Maschine ändert, wenn Sie mehr Daten einspeisen. Dies ist zumindest für meine Schüler ein beunruhigender Gedanke. Schließlich erhalten Sie mit dem Wort-RAM-Modell etwas überraschende Komplexitätsergebnisse, die möglicherweise nicht mit denen übereinstimmen, die man als Student lernt. Beispielsweise ist die Multiplikation von zwei n-Bit-Zahlen in diesem Modell O (n) -Zeit, und das einfache Einlesen einer n-Bit-Zeichenfolge ist plötzlich eine sublineare Zeitoperation. Dies bedeutet, dass man sich eine unendliche Klasse von Maschinen vorstellen muss, auf denen Ihr Algorithmus ausgeführt wird, oder noch schlimmer, dass sich die Maschine ändert, wenn Sie mehr Daten einspeisen. Dies ist zumindest für meine Schüler ein beunruhigender Gedanke. Schließlich erhalten Sie mit dem Wort-RAM-Modell etwas überraschende Komplexitätsergebnisse, die möglicherweise nicht mit denen übereinstimmen, die Sie als Schüler lernen. Beispielsweise ist die Multiplikation von zwei n-Bit-Zahlen in diesem Modell O (n) -Zeit, und das einfache Einlesen einer n-Bit-Zeichenfolge ist plötzlich eine sublineare Zeitoperation.

Abgesehen davon, wenn Sie nur wissen möchten, ob Ihr Algorithmus wahrscheinlich schnell abläuft, ist dies höchstwahrscheinlich der Fall :-)

Models sind nur Models. Ich würde es nicht zu weit treiben; Sie erzählen etwas über einige Aspekte Ihrer Algorithmen, aber nicht die ganze Wahrheit.

Ich würde vorschlagen, dass Sie einfach das Standardwort-RAM-Modell für Ihre Analyse verwenden und den Algorithmus implementieren und sehen, wie gut er in der Praxis funktioniert.

(Eigentlich sagt Ihnen nur die Implementierung Ihres Algorithmus, ohne ihn jemals auszuführen, viel darüber aus ... Zum einen ist er dann nachweislich implementierbar.)

Wenn es bei Ihrer Rechenaufgabe mehr um das Verschieben von Daten als um das Durchführen von (arithmetischen) Operationen geht (die Datenmengen sind riesig, sodass sie nicht einmal in den Hauptspeicher passen), dann das I / O-Modell (1988 von Aggarwal und Vitter eingeführt ). kann sehr genau sein. Für Aufgaben wie das Permutieren einer großen Anzahl von Elementen im Hauptspeicher kann es hilfreich sein, die Algorithmen zu verwenden, die I / O-optimal sind (in einer sorgfältigen Implementierung).

Für moderne Mehrkerncomputer kann die von Arge, Goodrich, Nelson und Sitchinava im Jahr 2008 eingeführte parallele Variante ein genaues Modell sein.

Wenn Sie "das beste" Rechenmodell meinen, um Ihr Leben komplizierter zu machen, können Sie Wolframs Universal-Turing-Maschine mit 2 Zuständen und 3 Symbolen verwenden.

PROS : keine außer dem Gefühl, die feine Linie zwischen Vernunft und Verrücktheit zu gehen;

Nachteile : Tonnen ...

:-D (nur ein Witz, ich stimme im Grunde mit den vorherigen Antworten überein ...)

Eine theoretischere Anmerkung: Der Artikel Ultimative theoretische Modelle von Nanocomputern argumentiert, dass das reversible 3D-Netzmodell das optimale physikalische Rechenmodell ist, in dem Sinne, dass kein anderes physikalisches Modell asymptotisch schneller sein könnte. Physikalische Überlegungen wie die Lichtgeschwindigkeit, das Landauer-Prinzip und die Bekenstein-Grenze werden diskutiert.

Um aus dem Abstract zu zitieren:

Wir stellen fest, dass eine reversible Maschine, die nur einige hundert Schichten von Schaltkreisen enthält, mit der aktuellen Technologie eine bessere Leistung erzielen kann als jede andere Maschine, und dass ein auf Nanotechnologie basierender reversibler Computer nur wenige Mikrometer groß sein muss, um eine mögliche irreversible Technologie zu übertreffen.

Wir argumentieren, dass eine Siliziumimplementierung des reversiblen 3D-Netzes heute wertvoll sein könnte, um bestimmte wissenschaftliche und technische Berechnungen zu beschleunigen, und schlagen vor, dass das Modell ein Schwerpunkt zukünftiger Studien in der Theorie paralleler Algorithmen für eine Vielzahl von Problemen werden sollte.