2016-03-28 19 views
3

In Clojure Ich möchte das Ergebnis der mehrfachen Reduktion finden, während nur die Sequenz einmal konsumieren. In Java würde ich etwas tun, wie folgt aus:Führen Sie mehrere Reduzierungen in einem einzigen Durchgang in Clojure

double min = Double.MIN_VALUE; 
double max = Double.MAX_VALUE; 
for (Item item : items) { 
    double price = item.getPrice(); 
    if (price > min) { 
     min = price; 
    } 

    if (price < max) { 
     max = price; 
    } 
} 

in Clojure I unter Verwendung Schleife viel das gleiche tun könnte und wieder auftreten, aber es ist nicht sehr zusammensetzbare - ich möchte etwas tun, die Sie hinzufügen in können andere Aggregationsfunktionen nach Bedarf

Ich habe die folgende Funktion geschrieben, dies zu tun:

(defn reduce-multi 
    "Given a sequence of fns and a coll, returns a vector of the result of each fn 
    when reduced over the coll." 
    [fns coll] 
    (let [n (count fns) 
     r (rest coll) 
     initial-v (transient (into [] (repeat n (first coll)))) 
     fns (into [] fns) 
     reduction-fn 
     (fn [v x] 
      (loop [v-current v, i 0] 
      (let [y (nth v-current i) 
        f (nth fns i) 
        v-new (assoc! v-current i (f y x))] 
       (if (= i (- n 1)) 
       v-new 
       (recur v-new (inc i))))))] 
    (persistent! (reduce reduction-fn initial-v r)))) 

Dies kann auf folgende Weise verwendet werden:

(reduce-multi [max min] [4 3 6 7 0 1 8 2 5 9]) 
=> [9 0] 

Ich schätze, dass es in den meisten idiomatische Weise nicht implementiert ist, aber das Hauptproblem ist, dass es etwa 10x so langsam ist wie die Reduktionen gleichzeitig. Dies kann nützlich sein für viele, die eine Menge Reduktionen durchführen, wo die Seq schwere IO ausführt, aber das könnte sicherlich besser sein.

Gibt es etwas in einer vorhandenen Clojure-Bibliothek, die das macht, was ich will? Wenn nicht, wo liege ich in meiner Funktion falsch?

+2

Haben Sie in Transducers gelesen? Wenn ja, sind sie verwirrend? Wenn nicht, würde es vorgeschlagen werden. –

+5

Siehe 'juxt' unter https://github.com/cgrand/xforms –

+0

@AWebb' juxt' scheint perfekt ... aber nicht erforderlich, oder? Mein Verständnis ist, dass Transducer eine Reihe von separaten "reduce" -Rufen ermöglichen, ohne dass Zwischensequenzen erzeugt werden, was ich zum Ziel nehme, hier zu sein. – Mars

Antwort

-1

Hier ist, wie ich es tun würde:

(ns clj.core 
    (:require [clojure.string :as str]) 
    (:use tupelo.core)) 

(def data (flatten [ (range 5 10) (range 5) ])) 
(spyx data) 

(def result (reduce (fn [cum-result curr-val]       ; reducing (accumulator) fn 
         (it-> cum-result 
           (update it :min-val min curr-val) 
           (update it :max-val max curr-val))) 
         { :min-val (first data) :max-val (first data) } ; inital value 
         data))           ; seq to reduce 
(spyx result) 
(defn -main []) 

;=> data => (5 6 7 8 9 0 1 2 3 4) 
;=> result => {:min-val 0, :max-val 9} 

So die Reduktionsfunktion (fn ...) führt entlang einer Karte wie {:min-val xxx :max-val yyy} durch jedes Element der Sequenz, die max Werte min & Aktualisierung nach Bedarf bei jedem Schritt.

Während dies nur einen Durchlauf durch die Daten macht, macht es eine Menge zusätzlicher Arbeit und ruft zweimal pro Element update auf. Es sei denn, Ihre Sequenz sehr ungewöhnlich ist, ist es wahrscheinlich effizienter zu machen zwei (sehr effizient) durch die Daten wie:

(def min-val (apply min data)) 
(def max-val (apply max data)) 
(spyx min-val) 
(spyx max-val) 
;=> min-val => 0 
;=> max-val => 9 
3

, das ist, was ich tun würde: einfach delegieren diese Aufgabe an einen Kern reduce Funktion, wie diese :

(defn multi-reduce 
    ([fs accs xs] (reduce (fn [accs x] (doall (map #(%1 %2 x) fs accs))) 
         accs xs)) 
    ([fs xs] (when (seq xs) 
      (multi-reduce fs (repeat (count fs) (first xs)) 
          (rest xs))))) 

in repl:

user> (multi-reduce [+ * min max] (range 1 10)) 
(45 362880 1 9) 

user> (multi-reduce [+ * min max] [10]) 
(10 10 10 10) 

user> (multi-reduce [+ * min max] []) 
nil 

user> (multi-reduce [+ * min max] [1 1 1000 0] []) 
[1 1 1000 0] 

user> (multi-reduce [+ * min max] [1 1 1000 0] [1]) 
(2 1 1 1) 

user> (multi-reduce [+ * min max] [1 1 1000 0] (range 1 10)) 
(46 362880 1 9) 

user> (multi-reduce [max min] (range 1000000)) 
(999999 0) 
+0

Dies erhält einen Stapelüberlauffehler für Sequenzen, die groß genug sind, z. (Multi-reduzieren [max min] (Bereich 10000)) StackOverflowError clojure.lang.LazySeq.sval (LazySeq.java:40) Allerdings ist dies definitiv auf dem richtigen Weg - es ist die Version der Karte, die mehrere Sammlungen akzeptiert das hilft sehr. Das hatte ich völlig vergessen, was einen großen Teil der Komplexität in meiner eigenen Lösung verursacht. –

+0

oh, dieser Stackowerflow ist einfach zu lösen. Mein Fehler. Das ist, weil die 'Karte' vollständig realisiert werden sollte. – leetwinski

+0

meine Antwort aktualisiert: eingewickelt 'map' in' doall' – leetwinski

1

Der Code für reduce schnell ist für reduzierbar Sammlungen. Es lohnt sich also, multi-reduce auf Core reduce zu basieren. Dazu müssen wir reduzierende Funktionen der richtigen Form konstruieren können. Eine Zusatzfunktion so zu tun ...

(defn juxt-reducer [f g] 
    (fn [[fa ga] x] [(f fa x) (g ga x)])) 

Jetzt können wir die gewünschte Funktion definieren, die als juxt mit reduce verbindet ...

(defn juxt-reduce 
    ([[f g] coll] 
    (if-let [[x & xs] (seq coll)] 
    (juxt-reduce (list f g) [x x] xs) 
    [(f) (g)])) 
    ([[f g] init coll] 
    (reduce (juxt-reducer f g) init coll))) 

Zum Beispiel

(juxt-reduce [max min] [4 3 6 7 0 1 8 2 5 9]) ;=> [9 0] 

Das obige folgt der Form des Kerns reduce. Es kann deutlich erweitert werden, um mehr als zwei Funktionen zu bewältigen. Und ich würde erwarten, dass es für reduzible Sammlungen schneller ist als Ihres.

+0

Was ist eine reduzierbare Sammlung? Oder vielleicht wäre es besser zu fragen, wie eine * nicht reduzierbare * Sammlung aussieht? –

+0

Eine * reduzierbare * Sammlung ist eine, die sich selbst reduzieren kann - eine Instanz von 'clojure.lang.IReduce', wie in [dem Quellcode von' reduce'] zu sehen ist (https://github.com/clojure/clojure /blob/010864f8ed828f8d261807b7345f1a539c5b20df/src/clj/clojure/core.clj#L6527). Ich denke, darauf bezieht sich @AWebb in seinem Kommentar zu [@ Leetwinskis Antwort] (http://stackoverflow.com/a/36278314/1562315). Der Repl sagt mir, dass Vektoren und Bereiche reduzierbar sind, aber Listen, Mengen und Karten nicht. – Thumbnail

+0

Großartig, danke. Wo kommt der Leistungsverlust her? In dem Beispiel, mit dem ich arbeite, benutze ich einen Bereich, der schnell sein sollte. Es scheint mir, dass das Problem ist, dass die reduzierenden Funktionen, die ich und @ Leetwinski verwendet haben, irgendwie langsam sind. –

Verwandte Themen