Haskell sinnlose Leistung - effizient mehrere Funktionen auf die gleichen Daten zuordnen

Question

Ich muss oft mehrere Funktionen auf die gleichen Daten zuordnen. Ich habe dpMap umgesetzt, dies zu tun für mich

dpMap fns = (`map` fns) . flip ($) 

dpMap ist eine Funktion, bedeutet das ich die Daten gelesen dt nur einmal (wie eine nur mit dem gleichen Eingang gespeist Schaltung Einem sinnloses System erinnert an einer Schaltung. nur die Rohrleitungen keine Daten)?

Betrachten Sie als Beispiel die Berechnung des Minimums und Maximums einer Liste dt.

minimax dt = (dpMap [minimum, maximum]) dt 

(I des dt befreien, sondern muß -XNoMonomorphismRestriction verwenden bekommen kann)

Gibt es wie dies einen Leistungsvorteil gegenüber der Umsetzung in einer Punkt-Voll Form die gleiche Funktion ?:

minimax2 dt = [minimum dt, maximum dt] 

EDIT: Gibt es eine allgemeine Implementierung von dpMap, die mit konstantem Speicher arbeitet?

Ich fand einen anderen netten Blogpost: http://www.haskellforall.com/2013/08/composable-streaming-folds.html; hoffe, dass dies hilft.

EDIT2: Nach etwas mehr Kontext, hier eine Lösung ist, auch wenn ich nicht über eine genaue Umsetzung der dpMap, ist das Muster einfach genug, dass es keine separate Funktion übernimmt keine Garantie:

minimax = (,) <$> minimum <*> maximum 

Verbrauch:

> minimax [1..100] 
(1,100) 

Wenn Sie wollen auch die Summe und die Länge berechnen

func = (,,,) <$> minimum <*> maximum <*> sum <*> length 

Verwendung

:

> func [1..100] 
(1,100,5050,100) 

Answer 1

Ich werde in dieser Antwort eine ziemlich breite Sicht auf die Frage nehmen, hauptsächlich wegen der Kommentare unter WillNess 'Antwort.

In einem blog post, führte Max Rabkin einige Arbeiten an Faltkombinatoren ein. Conal Elliott griff diese Idee auf und veröffentlichte einige weitere Blogposts sowie die ZipFold package über Hacker. Ich würde sehr empfehlen, dieses Material zu lesen, es ist kurz und ziemlich zugänglich. Das ZipFold-Paket ist wahrscheinlich sehr nützlich, obwohl es für einige Zeit nicht aktualisiert wurde.

Edward Kmett jüngsten Tour-de-Force, lens, enthält auch einige folding combinators. Ich bin mir nicht sicher, ob ich es nur dafür benutzen möchte, aber wenn du sowieso ein Objektiv verwendest, ist es wahrscheinlich wert, dass du es dir ansiehst.

Ein alternativer Ansatz ist die Verwendung von Parallelität. Wenn Sie

import Control.Parallel 

minimax2 dt = let a = minimum dt 
        b = maximum dt 
       in a `par` b `pseq` [a,b] 

und Link mit Threaded schreiben, dann ist es möglich, minimax2 in etwas in der Nähe konstanten Raum zu laufen, in Abhängigkeit von den Launen des Schedulers, Mondphasen, usw. (meist den Scheduler und Zuordnung Muster der Funktionen IIRC). Natürlich bietet dies keine zuverlässigen Garantien, aber es kann in der Praxis gut funktionieren. Verallgemeinern dieses Ansatzes zu dpMap sollte einfach sein, Sie würden wahrscheinlich Control.Parallel.Strategies oder ähnliches verwenden, anstatt die untere Ebene par direkt zu verwenden.

Schließlich sind die meisten iteratee-abgeleiteten Bibliotheken ziemlich gut im Umgang mit dieser Art von Aufgabe. Im Allgemeinen bieten sie eine explizite Kontrolle darüber, wann Eingangsströme erzeugt und verbraucht werden.In iteratee ich sequence_, die fast das gleiche wie dpMap, wird sequence hinzufügen, die genau das gleiche tun wird, wie dpMap, und eine Reihe von Reißverschlüssen, die alle in konstantem Raum laufen (vorausgesetzt, die konsumierenden Funktionen sind selbst konstant-) Raum). Ich wäre nicht überrascht, wenn die meisten anderen Pakete ähnliche Operationen hätten.

Answer 2

TL; DR: Es gibt keine Garantien über die Leistung in der Sprache selbst. Überhaupt keine. Es ist ein Compiler Sache.

Als Faustregel gilt, dass eine genannte Einheit resident ist. Wenn träge von nur einem Verbraucher zugegriffen wird, ist es vernünftig zu erwarten, dass es so optimiert wird, dass das kompilierte Programm in konstantem Arbeitsspeicher ausgeführt wird.

Die Erstellung und der Verbrauch von Speicherzellen werden verschachtelt, und jede Zelle wird nach der Verarbeitung GC-ediert.

---

In minimax2 dt = [minimum dt, maximum dt] der Ausdruck [minimum dt, maximum dt] ist innerhalb des Schutzbereichs, wo die benannte Einheit dt definiert ist. Höchstwahrscheinlich (d. H. Fast sicher) wird GHC es als eine Speichereinheit, d. H. Einmal, zuweisen, und sowohl dt innerhalb des Ausdrucks beziehen sich auf dieselbe Entität (zeigen Sie darauf, als ob Zeiger vorhanden wären).

Aber wie Cat Plus Plus in den Kommentaren darauf hinweist, ist natürlich der Zugriff auf Entität eine ganz andere Sache. Und die zwei Unterausdrücke werden jeweils separat darauf zugreifen, d. H. Sie werden vollständig im Speicher behalten. Das ist nicht gut.

Wir können es besser machen, und finden unsere Antwort, indem wir nur einmal darauf zugreifen, mit einer Falte, und sammeln die zwei Daten, während wir weitermachen. In einer solchen Situation ist es nahezu sicher, dass GHC eine Optimierung durchführen wird, bei der diese Liste als Ganzes im Speicher behalten wird.

Dies ist, was normalerweise als die Liste konsumiert wird träge. Wenn dies der Fall ist, wird seine Erzeugung mit diesem einen Zugriff verschachtelt, und jede erzeugte Speicherzelle wird sofort durch GC (Garbage Collection) verbraucht und freigegeben, so dass eine konstante Speicheroperation erreicht wird.

Aber das ausgesagt auf unsere Fähigkeit, durch die Liste zu scannen nur einmal:

{-# OPTIONS_GHC -O2 -XBangPatterns #-} 

import Data.List (foldl') 

minmax :: (Ord b) => [b] -> (b, b) 
minmax (x:xs) = foldl' (\(!a,!b) x -> (min a x,max b x)) (x,x) xs 

Bang Muster verhindern Aufbau thunk, wodurch Bewertung der Argumente eifriger. Prüfung:

Prelude> minmax [1..6] 
(1,6) 
Prelude> minmax [] 
*** Exception: <interactive>:1:4-65: Non-exhaustive patterns in function minmax 

Eine leere Liste der Kurs hat kein Minimum noch Maximum definiert.

Damit die Optimierungen wirksam werden, muss beim Kompilieren mit GHC das Flag -O2 verwendet werden.