Warum ist diese Schleifenfunktion im Vergleich zur Karte so langsam?

Question

Ich schaute auf Quellcode der Karten, der grundsätzlich lazy Sequenzen erstellt. Ich würde denken, dass das Iterieren über eine Sammlung und Hinzufügen zu einem transienten Vektor schneller wäre, aber das ist es eindeutig nicht. Was verstehe ich nicht über Clojures Leistungsverhalten?

;=> (time (do-with/(range 1 1000) (range 1 1000))) 
;"Elapsed time: 23.1808 msecs" 
; 
; vs 
;=> (time (doall (map #(/ %1 %2) (range 1 1000) (range 1 1000)))) 
;"Elapsed time: 2.604174 msecs" 
(defn do-with 
    [fn coll1 coll2] 
    (let [end (count coll1)] 
    (loop [i 0 
      res (transient [])] 
     (if 
      (= i end) 
      (persistent! res) 
      (let [x (nth coll1 i) 
        y (nth coll2 i) 
        r (fn x y)] 
       (recur (inc i) (conj! res r))) 
       )))) 

Answer 1

Um der vermuteten Auswirkungen auf die relativen Ergebnisse:

1. Ihre do-with Funktion verwendet nth die einzelnen Positionen in den Eingangs Sammlungen zuzugreifen. nth arbeitet in linearer Zeit auf Bereichen, wodurch do-with quadratisch. Unnötig zu sagen, dass dies die Performance bei großen Sammlungen zunichtemacht.

2. range produziert Chunked Seqs und map behandelt diese äußerst effizient. (Im wesentlichen Chunks von bis zu 32 Elementen erzeugt sie - hier wird es in der Tat genau 32 - durch eine enge Schleife über die interne Anordnung jeden Eingang chunk wiederum ausgeführt wird, führt zu einer internen Anordnungen von Ausgang chunks platzieren.)

3. Das Benchmarking mit time gibt Ihnen keine konstante Leistung. (Weshalb man wirklich eine richtige Benchmarking-Bibliothek verwendet werden soll, im Fall von Clojure, Criterium ist die Standardlösung.)

übrigens (map #(/ %1 %2) xs ys) kann einfach als (map/xs ys) geschrieben werden.

Update:

ich die map Version gebenchmarkt haben, die ursprüngliche do-with und eine neue do-with Version mit Criterium, (wie in der Fragetext) jeweils (range 1 1000), da beide Eingänge verwenden, den Erhalt der folgenden bedeuten Ausführungszeiten:

;;; (range 1 1000) 
new do-with   170.383334 µs 
(doall (map ...))  230.756753 µs 
original do-with  15.624444 ms 

Zusätzlich habe ich die Benchmark wiederholt, um einen Vektor in einem Var als Eingabe gespeichert ist, anstatt Bereiche (dh mit (def r (vec (range 1 1000))) am Anfang eines d unter Verwendung von r als beide Sammelargumente in jedem Benchmark). Wenig überraschend kam die ursprünglichen do-with in erster - nth ist sehr schnell auf Vektoren (plus mit nth mit einem Vektor vermeidet alle Zwischenzuweisungen in Seq Traversal beteiligt).

;;; (vec (range 1 1000)) 
original do-with  73.975419 µs 
new do-with   87.399952 µs 
(doall (map ...))  153.493128 µs 

Hier ist der neue do-with mit linearer Zeitkomplexität:

(defn do-with [f xs ys] 
    (loop [xs (seq xs) 
     ys (seq ys) 
     ret (transient [])] 
    (if (and xs ys) 
     (recur (next xs) 
      (next ys) 
      (conj! ret (f (first xs) (first ys)))) 
     (persistent! ret))))