Ich habe eine Quelle von Elementen und möchte Läufe von ihnen mit dem gleichen Wert einer Schlüsselfunktion getrennt verarbeiten. In Python würde das wie
aussehen %Vor% Diese Lösung ist völlig faul, d. h. wenn process nicht versucht, den gesamten Inhalt von part zu speichern, würde der Code in O(1) memory ausgeführt werden.
Clojure Lösung
%Vor% ist weniger faul: es realisiert jeden Teil vollständig. Das Problem ist, dass src sehr lange Läufe von Elementen mit demselben key-fn -Wert haben könnte und dass die Realisierung zu OOM führen könnte.
Ich habe diese Diskussion gefunden, in der behauptet wird, dass die folgende Funktion (geringfügig geändert für die Benennung Konsistenz innerhalb Post) ist faul genug
%Vor% Allerdings verstehe ich nicht, warum es nicht unter OOM leidet: beide Teile der Cons-Zelle enthalten einen Verweis auf s , also während process konsumiert part , s wird aber realisiert nicht Müll gesammelt. Es würde nur dann für GC infrage kommen, wenn drop-while part durchläuft.
Meine Fragen sind also:
lazy-partition-by nicht faul genug ist? partition-by mit garantierten Speicheranforderungen, vorausgesetzt, dass ich keine Referenzen auf die vorherige part halte, bis ich anfange, die nächste zu realisieren? BEARBEITEN: Hier ist eine faule genug Implementierung in Haskell:
%Vor% Wie aus span implementation , part und rest teilen sich den Status implizit. Ich frage mich, ob diese Methode in Clojure übersetzt werden könnte.
Obwohl diese Frage eine sehr interessante Betrachtung des Sprachdesigns hervorruft, ist das praktische Problem, dass Sie Partitionen in konstantem Speicher verarbeiten möchten. Und das praktische Problem ist mit etwas Inversion lösbar.
Übergeben Sie die Verarbeitungsfunktion nicht an das Ergebnis einer Funktion, die eine Folge von Partitionen zurückgibt, sondern an die Funktion, die die Partitionen erzeugt. Dann können Sie den Status in einer geschlossenen Weise steuern.
Zuerst werden wir einen Weg finden, den Verbrauch der Sequenz mit dem Zustand des Schwanzes zu verschmelzen.
%Vor% Dann eine modifizierte Version von partition-by
Hinweis: Für O (1) Speicherverbrauch processfn muss ein eifriger Konsument sein! Also während (process-partition-by identity key-fn coll) dasselbe ist wie (partition-by key-fn coll) , weil identity die Partition nicht belegt , der Speicherverbrauch ist nicht konstant.
Tests
%Vor%Die Faustregel, die ich in diesen Szenarien verwende (dh die, in denen eine einzelne Eingabesequenz mehrere Ausgabesequenzen erzeugen soll), besteht darin, dass Sie von den folgenden drei wünschenswerten Eigenschaften im Allgemeinen nur zwei haben können:
Die Version in clojure.core wählt (1,3), gibt aber auf (2) auf, indem sie eine ganze Partition auf einmal erzeugt. Python und Haskell wählen beide (1,2), obwohl es nicht sofort offensichtlich ist: Hat Haskell überhaupt keinen veränderlichen Zustand? Nun, seine faule Bewertung von allem (nicht nur Sequenzen) bedeutet, dass alle Ausdrücke Thunks sind, die als leere Schiefertafeln beginnen und nur dann geschrieben werden, wenn ihr Wert benötigt wird; Die Implementierung von span , wie Sie sagen, teilt den gleichen Thunk von span p xs' in seinen beiden Ausgabesequenzen, so dass das, was immer es benötigt, es zuerst an das Ergebnis der anderen Sequenz "sendet" und die Aktion bei a ausführt Entfernung, die notwendig ist, um die anderen schönen Eigenschaften zu erhalten.
Die alternative Clojure-Implementierung, mit der Sie verbunden sind, wählt (2,3), wie Sie festgestellt haben.
Das Problem ist, dass für partition-by das Ablehnen von entweder (1) oder (2) bedeutet, dass Sie den Kopf einer Sequenz halten: entweder die Eingabe oder eine der Ausgaben. Wenn Sie also eine Lösung wünschen, bei der beliebig große Partitionen einer beliebig großen Eingabe bearbeitet werden können, müssen Sie (1,2) wählen. Es gibt ein paar Möglichkeiten, wie Sie dies in Clojure tun können:
delay , und verlangen Sie, dass der Client so oft wie nötig force aufruft, um Daten abzurufen. Das wird in Clojure sehr viel hässlicher sein und die Stack-Tiefe stark erhöhen (dies wird bei einer nicht-trivialen Eingabe wahrscheinlich den Stack sprengen), aber es ist theoretisch möglich. Ich bin mir ziemlich sicher, dass jeder dieser drei Ansätze möglich ist, aber um ehrlich zu sein, sind sie alle ziemlich hart und überhaupt nicht natürlich. Die Sequenzabstraktion von Clojure macht es einfach nicht einfach, eine Datenstruktur zu erzeugen, die Sie möchten. Mein Rat ist, wenn Sie so etwas brauchen und die Partitionen zu groß sind, um bequem zu passen, akzeptieren Sie einfach ein etwas anderes Format und machen ein wenig mehr Buchhaltung selbst: weichen Sie dem (1,2,3) -Dilemma aus, indem Sie nicht mehrere erzeugen Ausgabesequenzen überhaupt!
Anstatt ((2 4 6 8) (1 3 5) (10 12) (7)) als Ausgabeformat für etwas wie (partition-by even? [2 4 6 8 1 3 5 10 12 7]) zu verwenden, könnten Sie ein etwas häßlicheres Format akzeptieren: ([::key true] 2 4 6 8 [::key false] 1 3 5 [::key true] 10 12 [::key false] 7) . Dies ist weder schwer zu produzieren noch schwer zu konsumieren, obwohl es ein bisschen langwierig und mühsam ist, zu schreiben.
Hier ist eine sinnvolle Implementierung der produzierenden Funktion:
%Vor% Und hier ist, wie Sie es konsumieren: Zuerst definieren Sie ein generisches reduce-grouped , das die Details des Gruppierungsformats verbirgt, und dann eine Beispielfunktion count-partition-sizes , um den Schlüssel und die Größe jeder Partition auszugeben, ohne irgendwelche Sequenzen im Speicher zu behalten:
Bearbeiten : Wenn ich es noch einmal betrachte, bin ich nicht wirklich davon überzeugt, dass mein reduce-grouped viel nützlicher ist als (reduce f init (map g xs)) , da es keinen wirklichen Hinweis darauf gibt, wann Schlüsseländerungen. Wenn Sie also wissen möchten, wann sich eine Gruppe ändert, benötigen Sie eine intelligentere Abstraktion, oder Sie verwenden meine ursprüngliche lazy-partition-by mit nichts "cleverem" Umbruch.
Habe ich Recht, wenn ich auf "lazy-partition" trete - indem ich nicht faul genug bin?
Nun, es gibt einen Unterschied zwischen Faulheit und Gedächtnisnutzung. Eine Sequenz kann träge sein und dennoch viel Speicher benötigen - siehe zum Beispiel die Implementierung von clojure.core/distinct , die eine Menge verwendet, um sich an alle zuvor beobachteten Werte in der Sequenz zu erinnern. Aber ja, Ihre Analyse der Speicheranforderungen von lazy-partition-by ist korrekt - der Funktionsaufruf zur Berechnung des Kopfes der zweiten Partition behält den Kopf der ersten Partition, was bedeutet, dass die Realisierung der ersten Partition dazu führt, dass sie beibehalten wird. Erinnerung. Dies kann mit dem folgenden Code überprüft werden:
Da weder doseq noch dorun den Kopf behalten, würde dies einfach für immer laufen, wenn lazy-partition-by O (1) im Speicher wäre.
Gibt es eine Implementierung von partition-by mit garantierten Speicheranforderungen, vorausgesetzt, ich halte keine Referenzen auf den vorherigen Teil, bis ich anfange, den nächsten zu realisieren?
Es wäre sehr schwierig, wenn nicht unmöglich, eine solche Implementierung rein funktional zu schreiben, was für den allgemeinen Fall funktionieren würde. Beachten Sie, dass eine allgemeine lazy-partition-by - Implementierung keine Annahmen darüber machen kann, wann (oder falls) eine Partition realisiert wird. Die einzige garantiert korrekte Art, den Anfang der zweiten Partition zu finden, besteht darin, sich nicht zu merken, wie viel von der ersten Partition realisiert wurde, um sich daran zu erinnern, wo die erste Partition begann, und vorwärts zu scannen, wenn sie angefordert wird.
Für den speziellen Fall, in dem Sie Datensätze nacheinander für Nebenwirkungen bearbeiten und sie nach Schlüssel gruppiert haben möchten (wie es bei Ihrer Verwendung von doseq oben impliziert ist), könnten Sie etwas in der Art eines Prozentsatzes berücksichtigen. co_de% / loop , das einen Zustand beibehält und bei Änderung des Schlüssels wieder setzt.
Tags und Links clojure lazy-evaluation lazy-sequences