Angenommen, ich habe eine Funktion f , die einige Eingaben akzeptiert und eine Zahl erzeugt. Innerhalb der Funktion f wird eine Liste gemäß der Eingabe erstellt, die dann reduziert wird (z. B. unter Verwendung von foldl' g ), um die endgültige Ausgabenummer zu erzeugen. Da die Zwischenliste schließlich reduziert werden soll, ist es möglich, die Reduzierungsfunktion g anzuwenden, ohne die Zwischenliste auszudrücken . Das Ziel besteht darin, den Speicher zu begrenzen, der zum Speichern (oder Ausdrücken, falls ein weniger genaues Wort gespeichert wird) zum Speichern der Liste verwendet wird.
Um das zu verdeutlichen, benötigt diese Funktion foldPairProduct O(N1 * N2) Leerzeichen für die Zwischenliste (der Platzbedarf ist vielleicht komplizierter aufgrund von Ausdruck und Lazy Evaluation, aber ich nehme an, dass es proportional oder schlechter ist). Hier ist N1, N2 die Größe der beiden Eingabelisten.
Eine alternative Implementierung der Logik ist foldPairProduct ', die O(2 * 2) Leerzeichen benötigt.
Die Situation wird für foldCrossProduct noch verschlimmert, deren Implementierung ähnlich wie foldPairProduct ist, außer dass sie mehrere Listen als Eingabe akzeptiert. Seine Raumkomplexität (noch im Sinne der imperativen Sprachen) für die Zwischenliste ist O(N1 * N2 * ...* Nk) , wobei k die Länge von [[a]] ist.
Wenn wir der Implementierungsidee von foldPairProduct' gefolgt wären, wäre die Raumkomplexität k^2 , was sehr viel platzsparender ist. Meine Fragen sind:
Ich habe foldPairProduct' für ein Listenpaar implementiert. Es scheint jedoch, als wäre die Implementierung für eine beliebige Anzahl von Listen nicht einfach.
Ich will Haskell nicht mit imperativer Sprache vergleichen, aber gibt es eine Implementierung, die konstanten Raum verwendet (oder in einem anderen Wort, ohne die Zwischenliste der genannten Länge auszudrücken)? Vielleicht würde Monad helfen, aber ich bin sehr neu dazu.
Macht der Compiler tatsächlich seine Magie? Das heißt, es ist zu beachten, dass die Liste intermediär ist und reduziert wird, und in der Tat einen Weg findet, um sie platzeffizient zu bewerten. Schließlich dachte ich, dass die faule Evaluierung und Compiler-Optimierung dafür gedacht ist.
Jeder Kommentar ist willkommen. Vielen Dank.
Update 1
Ein Leistungstest bestätigte die Analyse der "Raumkomplexität" von foldPairProduct und foldCrossProduct , basierend auf der Variation der Eingabegröße N1, N2, N3 und der Beobachtung der Bytes, die von GC kopiert wurden.
Der Leistungstest zeigt die Analyse auf foldPairProduct' , die überraschenderweise N1 * N2 oder sogar noch schlechteren Speicherplatzverbrauch zeigte. Dies ist wahrscheinlich darauf zurückzuführen, dass der rekursive Aufruf ineffizient ausgewertet wird. Die Ergebnisse sind unten angehängt (mit ghc-Einstellungen wie bei Yuras).
Update 2
Ich habe ein paar weitere Experimente aktualisiert, wie ich aus den Kommentaren und Antworten lerne. Für foldPairProduct stimmt der Gesamtspeicher in Verwendung mit der von Daniel Fischer erläuterten Komplexität des Platzes überein.
Für Nach Daniels Ratschlag haben Sie die foldCrossProduct , obwohl Daniels Komplexitätsanalyse für mich sinnvoll ist, zeigen die Ergebnisse keine lineare Speichernutzung. x <- xs und y <- crossproduct ys getauscht und es wird tatsächlich eine lineare Raumkomplexität erreicht.
Für foldCrossProduct (max) [[1..100],[1..n], [1..1000]] , mit n = 100, 1000, 10000, 100000 ist der verwendete Speicher 2, 2, 3, 14 MB.
foldPairProduct [1..n] [1..10000]
%Vor%foldPairProduct [1..10000] [1..n]
%Vor%foldPairProduct [1..n] [1..n]
%Vor%foldCrossProduct (max) [[1..n], [1..100], [1..1000]]
%Vor%foldCrossProduct (max) [[1..100], [1..n], [1..1000]]
%Vor%foldPairProduct '[1..n] [1..n]
%Vor% kann ein guter Bürger sein. Das zweite Argument, ys , wird wiederholt verwendet, so dass es während der Berechnung vollständig im Speicher bleiben muss, aber die Zwischenliste wird langsam erzeugt, da sie konsumiert wird, so dass nur eine konstante Menge an Speicher zur Verfügung gestellt wird. co_de% Raumkomplexität. Natürlich muss O(length ys) list cells produziert und konsumiert werden, also sind die Allokationen length xs * length ys [unter der Annahme, dass jeder O(length xs * length ys) Wert begrenzten Raum verwendet]. Die Anzahl der beim GC kopierten Bytes (und damit die für GC benötigte Zeit) kann durch Bereitstellung eines größeren Zuordnungsbereichs drastisch reduziert werden, mit a fällt die Anzahl ab
für die Standardeinstellung auf
%Vor% und die Zeit von +RTS -A1M bis GC time 4.88s für GC time 0.07s und xs == ys = [1 .. 10000] :: [Int] .
Aber das hängt davon ab, ob der Striktheitsanalysator seine Aufgabe erfüllt - was gut ist, wenn der Typ, mit dem er verwendet wird, z.B. f = (+) und während der Kompilierung bekannt, und die Kombinationsfunktion ist bekanntermaßen streng. Wenn der Code nicht spezialisiert ist oder wenn bekannt ist, dass die Kombinationsfunktion nicht streng ist, erzeugt die Faltung einen Thunk von Int size. Dieses Problem kann durch die Verwendung der strengeren O(length xs * length ys) behoben werden.
führt direkt zum Problem der unzureichenden Strenge, der Wert, der von einem foldl1' -Konstruktor umschlossen wird, kann hier vom Compiler nicht strikt gemacht werden, da er für das Gesamtergebnis nicht benötigt wird, so dass der Fold oft erzeugt wird ein Just size Thunk unter dem O(length xs * length ys) - natürlich, für einige Just , wie f , wird es sich so verhalten, wie es ist. Damit das ein guter Speicherbürger ist, wenn alle Werte verwendet werden, müssen Sie eine ausreichend strenge Kombinationsfunktion const verwenden, die auch den Wert unter f im Ergebnis erzwingt (wenn es ein Just ist); mit Just hilft auch. Damit kann es foldl1' space complexity haben (die Listen O(length ys + length xs) und xs werden mehr als einmal verwendet, werden also wiederverwendet).
Obwohl GHC wenig CSE (allgemeine Teilausdruck-Eliminierung) ausführt, wird die Liste ys (wahrscheinlich) hier zwischen den verschiedenen crossProduct xss s geteilt, so dass x Raumkomplexität erzeugt. Wenn die Reihenfolge der Elemente in der Liste keine Rolle spielt, ordnen Sie sie nach
hilft. Dann muss O(N2*...*Nk) nicht auf einmal im Speicher sein, also kann inkrementell produziert und konsumiert werden, nur crossProduct xss muss gespeichert werden, da es mehrmals verwendet wird. Bei den rekursiven Aufrufen muss die erste der verbleibenden Listen gemeinsam genutzt werden, so dass eine Gesamtkomplexität von xs entsteht.
Es gibt eine spezifische Optimierung für die Erstellung / Änderung / Verbrauch von Listen, die loop fusion genannt werden . Weil Haskell rein und nicht-streng ist, gibt es eine Anzahl von Gesetzen wie map f . mag g == map (f . g) .
Wenn der Compiler den Code aus irgendeinem Grund nicht erkennt und suboptimalen Code erzeugt (nachdem ich -O flag übergeben habe), würde ich die Stream-Fusion im Detail untersuchen, um zu sehen, was sie verhindert.
(Ok, ich habe mich geirrt, es wird nicht im konstanten Raum funktionieren, weil eine der Listen mehrfach verwendet wird, so dass es am wahrscheinlichsten eine lineare Raumkomplexität hat)
Haben Sie versucht, ein Testprogramm mit aktivierten Optimierungen zu kompilieren? Dein foldPairProduct sieht gut für mich aus, und ich erwarte, dass es im konstanten Raum funktioniert.
HINZUFÜGEN: Ja, es funktioniert in konstantem Speicherplatz (3 MB Gesamtspeicher belegt):
%Vor%Tags und Links haskell list on-the-fly reduction