使我的Clojure地圖功能實現更快

Question

我最近一直在嘗試Clojure。我嘗試編寫我自己的地圖功能（實際上是兩個），並對照內置函數對它們進行計時。然而，我的地圖功能比內置功能要慢得多。我想知道如何讓我的實現更快。它應該給我一些我編寫的性能調優Clojure算法的見解。第一個函數（my-map）用遞歸進行遞歸。第二個版本（my-map-loop）使用循環/遞歸，這比簡單地使用遞歸要快得多。

(defn my-map 
    ([func lst] (my-map func lst [])) 
    ([func lst acc] 
     (if (empty? lst) 
      acc 
      (recur func (rest lst) (conj acc (func (first lst))))))) 

(defn my-map-loop 
    ([func lst] 
     (loop [acc [] 
        inner-lst lst] 
      (if (empty? inner-lst) 
       acc 
       (recur (conj acc (func (first inner-lst))) (rest inner-lst)) 
       )))) 

(let [rng (range 1 10000)] 
    (time (map #(* % %) rng)) 
    (time (my-map #(* % %) rng)) 
    (time (my-map-loop #(* % %) rng))) 

這是我得到的結果 -

"Elapsed time: 0.084496 msecs" 
"Elapsed time: 14.132217 msecs" 
"Elapsed time: 7.324682 mess" 

更新

resueman指出，我是不正確的時間的事情後，我改變了功能：

(let [rng (range 1 10000)] 
    (time (doall (map #(* % %) rng))) 
    (time (doall (my-map #(* % %) rng))) 
    (time (doall (my-map-loop #(* % %) rng))) 
    nil) 

這些是新的結果：

"Elapsed time: 9.563343 msecs" 
"Elapsed time: 12.320779 msecs" 
"Elapsed time: 5.608647 mess" 

"Elapsed time: 11.103316 msecs" 
"Elapsed time: 18.307635 msecs" 
"Elapsed time: 5.86644 mess" 

"Elapsed time: 10.276658 msecs" 
"Elapsed time: 10.288517 msecs" 
"Elapsed time: 6.19183 mess" 

"Elapsed time: 9.277224 msecs" 
"Elapsed time: 13.070076 msecs" 
"Elapsed time: 6.830464 mess" 

看起來像我的第二個實現是最快的一堆。無論如何，我仍然想知道是否有辦法進一步優化它。

Answer 1

有很多事情可以利用有一個更快的地圖：瞬變（爲您的累加器），分塊seqs（源只有當你想要一個懶惰的輸出時有意義），reducible集合（再次來源）和更熟悉核心功能（這是一個mapv）。

如果只是檢查您的JVM優化是否有上限（這是lein的默認值），那麼您還應該考慮使用Criterium而不是time。

=> (let [rng (range 1 10000)] 
     (quick-bench (my-map-loop #(* % %) rng)) 
     (quick-bench (into [] (map #(* % %)) rng)) ; leveraging reducible collections and transients 
     (quick-bench (mapv #(* % %) rng))) ; existing core fn 

(output elided to keep only the means) 
      Execution time mean : 776,364755 µs 
      Execution time mean : 409,737852 µs 
      Execution time mean : 456,071295 µs 

這是有趣的是，mapv是不會高於(into [] (map #(* % %)) rng)是優化這類計算的一個通用的方法。

Answer 2

你的實現和內置的clojure實現之間有一個主要的根本區別：內置版本是懶惰的。實際上，你只是比較時間來簡單地在集合中放置一個包裝器，以便將每個項目轉換爲新的集合。基本上，無論代碼的速度如何，您都沒有機會贏得比賽。

如果您改變與此相比：

(let [rng (range 1 10000)] 
    (time (doall (map #(* % %) rng))) 
    (time (doall (my-map #(* % %) rng))) 
    (time (doall (my-map-loop #(* % %) rng))) 
    nil) 

的時間非常接近。在我使用它的運行中，您的第二次實現的執行時間從大約兩倍，再到一半。你可以做很多優化來改善這一點，但主要問題是你的測試，而不是你的功能。

如果你在對抗雖然Clojure的/核心競爭很感興趣，看最好的地方是在the source

(defn map 
    ([f coll] 
    (lazy-seq 
     (when-let [s (seq coll)] 
     (if (chunked-seq? s) 
      (let [c (chunk-first s) 
       size (int (count c)) 
       b (chunk-buffer size)] 
      (dotimes [i size] 
       (chunk-append b (f (.nth c i)))) 
      (chunk-cons (chunk b) (map f (chunk-rest s)))) 
      (cons (f (first s)) (map f (rest s)))))))) 

^修改，以去除除了代碼你比較一切反對。