Prepend und vs. Perf in Mathematica anhängen
In Lisp-ähnlichen Systemen ist CONS der normale Weg, ein Element einer Liste VORZUNEHMEN. Funktionen, die an eine Liste angehängt werden, sind wesentlich teurer, da sie die Liste bis zum Ende durchlaufen und dann den endgültigen Nullwert durch einen Verweis auf das angehängte Element ersetzen. IOW (PseudoLisp)
%Vor%Die Frage ist, ob die Situation in Mathematica ähnlich ist? In den meisten Fällen scheinen die Listen von Mathematica wie Lisp-Listen einzeln verknüpft zu sein, und wenn dem so ist, können wir annehmen, dass Append [Liste, Element] viel teurer ist als Prepend [Liste, Element]. Ich konnte jedoch in der Mathematica-Dokumentation nichts finden, um diese Frage zu beantworten. Wenn Mathematicas Listen doppelt verknüpft oder cleverer implementiert sind, z. B. in einem Heap, oder wenn nur ein Zeiger zum letzten beibehalten wird, dann kann das Einfügen ein völlig anderes Leistungsprofil haben.
Jeder Rat oder jede Erfahrung wäre willkommen.
4 Antworten
Mathematicas Listen sind nicht wie bei Common Lisp einfach verlinkte Listen. Es ist besser, an Mathematica-Listen als array- oder vektorartige Strukturen zu denken. Die Geschwindigkeit der Insertion ist O (n), aber die Geschwindigkeit des Abrufs ist konstant.
Sehen Sie sich diese Seite von Datenstrukturen und effiziente Algorithmen in Mathematica , die mathematische Listen ausführlicher behandeln.
Lesen Sie außerdem diese Stack Overflow-Frage zu den verknüpften Listen und deren Leistung in Mathematiker.
Da Mathematica-Listen, wie bereits erwähnt, als Arrays implementiert sind, führen Operationen wie Append und Prepend dazu, dass die Liste jedes Mal kopiert wird, wenn ein Element hinzugefügt wird. Eine effizientere Methode besteht darin, eine Liste vorzubelegen und sie zu füllen, jedoch zeigte mein unten beschriebenes Experiment keinen so großen Unterschied, wie ich erwartet hatte. Besser noch, anscheinend, ist die Linked-List-Methode, die ich untersuchen muss.
%Vor%Zeitdiagramm vergleicht AppendTo mit der Vorbelegung. (Laufzeit: 82 Sekunden)
Bearbeiten
Unter Verwendung der vorgeschlagenen Modifikation von nixeagle wurde der Zeitpunkt der Vorbelegung erheblich verbessert, d. h. mit preallocatedlist = Join[startlist, ConstantArray[0, {Length[datalist]}]];
Zweiter Schritt
Eine verkettete Liste der Form {{{startlist}, data1}, data2} funktioniert noch besser und hat den großen Vorteil, dass die Größe nicht im Voraus bekannt sein muss, ebenso wie die Vorbelegung.
p> %Vor%Timing-Vergleich von Linked-List vs Pre-Allocation. (Laufzeit: 6 Sekunden)
Als kleines Addon ist hier eine effiziente Alternative zu "AppendTo" in M -
%Vor%Wenn Sie wissen, wie viele Elemente Ihr Ergebnis haben wird und wenn Sie Ihre Elemente berechnen können, ist das Ganze Append, AppendTo, Linked-List usw. nicht notwendig. Im Geschwindigkeitstest von Chris funktioniert die Vorbelegung nur, weil er die Anzahl der Elemente im Voraus kennt. Die Zugriffsoperation auf datelist steht für die virtuelle Berechnung des aktuellen Elements.
Wenn die Situation so ist, würde ich niemals einen solchen Ansatz verwenden. Ein einfacher Tisch kombiniert mit einem Join ist die Hölle schneller. Lassen Sie mich den Code von Chris wiederverwenden: Ich füge die Vorbelegung der Zeitmessung hinzu, weil bei Verwendung von Anhängen oder der verknüpften Liste die Speicherzuordnung ebenfalls gemessen wird. Außerdem verwende ich die resultierenden Listen und überprüfe, ob sie gleich sind, denn ein cleverer Interpreter könnte vielleicht einfache, nutzlose Befehle erkennen und diese optimieren.
%Vor% 
Meiner Meinung nach sind die interessanten Situationen, wenn Sie die Anzahl der Elemente nicht im Voraus kennen und Sie sich ad hoc entscheiden müssen, ob Sie etwas anhängen müssen. In diesen Fällen lohnt sich ein Blick auf Reap [] und Sow []. Im Allgemeinen würde ich sagen, AppendTo ist böse und bevor Sie es verwenden, werfen Sie einen Blick auf die Alternativen:
%Vor%Gibt {5.151575, 0.250336, 0.128624, 0.148084}. Das Konstrukt
%Vor%ist zum Glück wirklich lesbar und schnell.
Bemerkung
Seien Sie vorsichtig, wenn Sie dieses letzte Beispiel zu Hause ausprobieren. Hier, auf meinem Ubuntu 64bit und Mma 8.0.4 benötigt das AppendTo mit n = 10 ^ 5 10GB Speicher. n = 10 ^ 6 nimmt all meinen RAM, der 32 GB beträgt, um ein Array mit 15 MB Daten zu erstellen. Lustig.
Tags und Links wolfram-mathematica list lisp