Dies ist eine überraschend komplexe Frage, weil zwei Merkmale von Haskell und GHC:
- Verzögerte Auswertung
- Liste Fusion
Liste Fusion bedeutet, dass in einigen Situationen GHC kann den Listenverarbeitungscode in eine Schleife schreiben, die keine Listenzellen zuweist. Je nach dem Kontext, in dem es verwendet wird, kann derselbe Code keine zusätzlichen Kosten verursachen.
Faule Bewertung bedeutet, dass wenn das Ergebnis einer Operation nicht verbraucht wird, Sie die Kosten für die Berechnung nicht übernehmen. So zum Beispiel, ist dies günstig, weil Sie nur die ersten zehn Elemente der Liste zu konstruieren haben:
example = take 10 ([1..1000000] ++ [1000001])
In der Tat, in diesem Code die take 10 mit der Liste Anfügen verschmelzen kann, so ist es das gleiche wie einfach [1..10].
Aber nehmen wir einfach an, dass wir alle Elemente von allen Listen verbrauchen, die wir machen, und dass der Compiler unsere Listenoperationen nicht verschmilzt. Jetzt zu Ihren Fragen:
Wenn ich ein Element zu einer Liste in Haskell hinzufüge, gibt Haskell eine (vollständig?) Neue Liste zurück und manipuliert die ursprüngliche nicht. Nun sagen wir, ich habe eine Liste von Millionen Elementen und füge ein Element am Ende an. Kopiert Haskell die gesamte Liste (1 Million Elemente) und fügt das Element zu dieser Kopie hinzu? Oder gibt es einen netten "Trick" hinter den Kulissen, um das Kopieren der ganzen Liste zu vermeiden?
Es gibt Tricks, das Kopieren der gesamten Liste zu vermeiden, aber von seinem Ende anhängt Sie sie besiegen. Die Sache zu verstehen ist, dass funktionale Datenstrukturen normalerweise so entworfen sind, dass Operationen, die sie "modifizieren", Struktur-Teilen ausnutzen, um so viel von der alten Struktur wie möglich wiederzuverwenden. So kann beispielsweise zwei Listen anhängen wie folgt definiert werden:
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys
bei dieser Definition suchen, können Sie sagen, dass die Liste ys wird im Ergebnis wiederverwendet werden. Also, wenn wir xs = [1..3] haben, ys = [4..5] und xs ++ ys, die alle komplett ausgewertet und im Speicher auf einmal beibehalten, wird es so etwas wie dieses Gedächtnis weise aussehen:
+---+---+ +---+---+ +---+---+
xs = | 1 | -----> | 2 | -----> | 3 | -----> []
+---+---+ +---+---+ +---+---+
+---+---+ +---+---+
ys = | 4 | -----> | 5 | -----> []
+---+---+ +---+---+
^
|
+------------------------------------+
|
+---+---+ +---+---+ +---+---+ |
xs ++ ys = | 1 | -----> | 2 | -----> | 3 | -------+
+---+---+ +---+---+ +---+---+
, dass der lange Weg, dies zu sagen: wenn Sie das tun xs ++ ys , und es fusioniert nicht, und Sie verbrauchen die ganze Liste, dann wird das eine Kopie von xs erstellen, aber den Speicher für ys wiederverwenden.
Aber jetzt schauen wir uns wieder in diesem Bit Ihrer Frage:
die wir nun sagen, ich habe eine Liste von einer Million Elementen und ich anfügen ein Element am Ende. Kopiert Haskell die gesamte Liste (1 Million Elemente) und fügt das Element zu dieser Kopie hinzu?
Das wäre so etwas wie [1..1000000] ++ [1000001], und ja, es würde die ganze Million Elemente kopieren. Auf der anderen Seite würde [0] ++ [1..1000000] nur die [0] kopieren. Die Faustregel lautet wie folgt:
- Hinzufügen von Elementen am Anfang einer Liste ist am effizientesten.
- Das Hinzufügen von Elementen am Ende einer Liste ist oft ineffizient, besonders wenn Sie es immer und immer wieder tun.
Die allgemeinen Lösungen für diese Art von Problem sind:
- Ihren Algorithmus ändern, so dass Sie eine Liste in einem Zugriffsmuster sie effizient unterstützen verwenden.
- Verwenden Sie keine Listen; Verwenden Sie eine andere Sequenzdatenstruktur, die das für das jeweilige Problem erforderliche Zugriffsmuster effizient unterstützt. Eine andere Antwort erwähnt Differenzlisten, aber andere erwähnenswert sind:
Ich bin damit einverstanden, was Sie sagen, aber die Ihre Big O-Notation ist nicht korrekt. O (500000500000) == O (1) == konstante Zeit (siehe http://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant). Sicher, Sie können argumentieren, dass, wenn Sie versuchen, "eine Million Elemente anzuhängen", es immer in O (1) läuft, da keine Variable übrig ist und die Operation "eine Million Mal anhängen" tatsächlich in konstanter Zeit läuft. Aber ich glaube nicht, dass du das sagen willst. –
@ JohannesWeiß Besser? – bheklilr
Ja, @bheklilr, danke :) –