perché questa funzione di looping è così lenta rispetto alla mappa?

Question

Ho guardato il codice sorgente mappe che mantiene sostanzialmente la creazione di sequenze pigri. Penserei che iterare su una collezione e aggiungere a un vettore transitorio sarebbe più veloce, ma chiaramente non lo è. Cosa non capisco del comportamento delle prestazioni degli clojures?

;=> (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

Al fine di impatto ipotizzata sui risultati relativi:

1. La funzione do-with usa nth per accedere alle singole voci nelle collezioni di ingresso. nth opera in tempo lineare su intervalli, rendendo do-with quadratica. Inutile dire che questo ucciderà le prestazioni su grandi collezioni.

2. range produce seguenti del regolamento provvisorio divisi in blocchi e map gestisce quelli estremamente efficiente. (Essenzialmente produce pezzi fino a 32 elementi - qui sarà infatti esattamente 32 - eseguendo un ciclo stretto sopra la matrice interna di ciascun blocco di ingresso, a sua volta, mettendo risultati in matrici interne dei blocchi di uscita.)

3. Benchmarking con time non ti dà prestazioni steady state. (Che è il motivo per cui si dovrebbe davvero utilizzare una libreria di benchmarking corretta, nel caso di Clojure, Criterium è la soluzione standard.)

Per inciso, (map #(/ %1 %2) xs ys) può semplicemente essere scritto come (map/xs ys).

Aggiornamento:

ho benchmark la versione map, l'originale do-with e una nuova versione do-with con Criterium, utilizzando (range 1 1000) come entrambi gli ingressi in ogni caso (come nel testo della domanda), ottenendo il seguente significare tempi di esecuzione:

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

Inoltre, ho ripetuto il benchmark utilizzando un vettore memorizzato in un Var come input anziché intervalli (cioè con (def r (vec (range 1 1000))) al avviare d utilizzando come r entrambi gli argomenti di raccolta in ogni benchmark). Non sorprende che l'originale do-with è venuto in primo - nth è molto veloce su vettori (più utilizzando nth con un vettore evita tutte le allocazioni intermedi coinvolti nella ss attraversamento).

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

Ecco il nuovo do-with con la complessità tempo lineare:

(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))))