Data.Map: Wie kann ich feststellen, ob ich "Value-strict maps" brauche?

8

Wenn Sie zwischen Data.Map.Lazy und Data.Map.Strict wählen, sagen uns die Dokumente zum ersten:

  

API dieses Moduls ist streng in den Schlüsseln, aber faul in den Werten. Wenn Sie wertstrotzende Maps benötigen, verwenden Sie stattdessen Data.Map.Strict .

und für letzteres ebenfalls:

  

Die API dieses Moduls ist sowohl in den Schlüsseln als auch in den Werten streng. Wenn Sie -Wartungs-Maps benötigen, verwenden Sie stattdessen Data.Map.Lazy .

Wie tendieren mehr erfahrene Haskeller als ich dazu, dieses "Bedürfnis" zu erkennen? Anwendungsfall in einem run-and-done-Befehlszeilentool (dh nicht daemon-like / long-running): readFile ing eine einfache lines -basierte benutzerdefinierte Konfigurationsdatei, in der viele (nicht alle) Zeilen definieren Schlüssel: Wertpaare, die in einem Map gesammelt werden sollen. Sobald dies erledigt ist, schreiben wir viele Werte neu, abhängig von anderen Werten, die später gelesen wurden (dank der Unveränderlichkeit, in diesem Prozess erstellen wir ein neues Map und verwerfen die ursprüngliche Inkarnation).

(Obwohl in der Praxis diese Datei wahrscheinlich nicht einmal 1000 Zeilen erreichen wird, nehmen wir einfach an, dass dies für einige Benutzer sehr schnell vonstatten gehen wird.)

Irgendein bestimmter Lauf des Werkzeugs wird vielleicht 20-100% des (beim Laden neu geschriebenen, obwohl ich mich bei lazy-eval nie ganz sicher bin), wenn wirklich ") key: value Paare, irgendwo zwischen einmal und Dutzenden von Zeiten.

Wie beziehe ich mich auf die Unterschiede zwischen "Wert-strikt" und "Wert-faul" Data.Map s hier? Was passiert "unter der Haube", in Bezug auf Mainstream-Computing, wenn Sie so wollen?

Im Grunde geht es bei solchen Hash-Maps natürlich um "einmal speichern, viele Male nachschlagen" - aber was ist dann nicht "grundlegend"? Und außerdem scheint das ganze Konzept von Lazy-Evals Thunks auf dieses Prinzip zu reduzieren, also warum nicht immer value-faul bleiben?

    
metaleap 23.12.2016, 10:30
quelle

2 Antworten

8
  

Wie kann ich die Unterschiede zwischen "value-strict" und "value-faulen" Data.Maps hier begründen?

Wert faul ist das normale in Haskell. Dies bedeutet, dass nicht nur Werte, sondern Thunks (d. H. Rezepte zur Berechnung des Werts) gespeichert werden. Nehmen wir zum Beispiel an, Sie extrahieren den Wert aus einer Zeile wie folgt:

%Vor%

Dann würde eine Wert-strikte Karte den Wert beim Einfügen tatsächlich extrahieren, während ein Fauler sich einfach daran erinnern würde, wie man es bekommt. Dies ist dann auch, was Sie auf einem lookup

bekommen würden

Hier sind einige Vor- und Nachteile:

  • Lazy-Werte benötigen möglicherweise mehr Speicher, nicht nur für den Thunk selbst, sondern auch für die Daten, auf die dort verwiesen wird (hier line ).
  • strenge Werte benötigen möglicherweise mehr Speicher. In unserem Fall könnte dies der Fall sein, wenn der String so interpretiert wird, dass er einige speicherhungrige Strukturen wie Listen, JSON oder XML liefert.
  • Wenn Sie lazy-Werte verwenden, benötigen Sie möglicherweise weniger CPU, wenn Ihr Code nicht jeden Wert benötigt.
  • zu tiefe Verschachtelung von Thunks kann Stapelüberläufe verursachen, wenn der Wert endgültig benötigt wird.
  • Es gibt auch einen semantischen Unterschied: Im Lazy-Modus könnten Sie wegkommen, wenn der Code zum Extrahieren des Werts fehlschlagen würde (wie der obige, der fehlschlägt, wenn in der Zeile kein ':' steht), wenn Sie es nur brauchen schau, ob der Schlüssel vorhanden ist. Im strikten Modus stürzt Ihr Programm beim Einfügen ab.

Wie immer gibt es keine festen Maße wie: "Wenn Ihr ausgewerteter Wert weniger als 20 Bytes benötigt und weniger als 30 μs zur Berechnung benötigt, verwenden Sie strict, sonst verwenden Sie faul."

Normalerweise gehen Sie nur mit einem und wenn Sie extreme Laufzeiten / Speicherverbrauch bemerken, versuchen Sie den anderen.

    
Ingo 23.12.2016, 12:03
quelle
3

Hier ist ein kleines Experiment, das einen Unterschied zwischen Data.Map.Lazy und Data.Map.Strict zeigt. Dieser Code erschöpft den Heap:

%Vor%

(Besser mit einem kleinen maximalen Heap kompilieren, wie ghc Main.hs -with-rtsopts="-M20m" .)

Das foldl' behält die Map in WHNF bei der Iteration über die unendliche Liste von Nullen bei. Thunks akkumulieren jedoch in dem geänderten Wert, bis der Heap erschöpft ist.

Derselbe Code mit Data.Map.Strict läuft einfach für immer. In der strikten Variante sind die Werte in WHNF, wenn die Karte in WHNF ist.

    
danidiaz 23.12.2016 12:06
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie ändere ich die Variable von innen Fn Schließung in Rust?