7

基本的に遅延シーケンスを作成し続けるマップのソースコードを見ました。コレクションを反復処理して一時的なベクトルに追加する方が高速だと思いますが、明らかにそうではありません。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))) 
                  ))))
4

1 に答える 1

14

相対的な結果への影響の推測順:

  1. 関数は、入力コレクション内の個々のアイテムにアクセスするためにdo-with使用します。範囲で線形時間で動作し、二次になります。言うまでもなく、これにより大規模なコレクションのパフォーマンスが低下します。nthnthdo-with

  2. rangeチャンクされた seq を生成しmap、それらを非常に効率的に処理します。(基本的に、各入力チャンクの内部配列に対して順番にタイトなループを実行し、結果を出力チャンクの内部配列に配置することにより、最大 32 要素のチャンクを生成します。ここでは、実際には正確に 32 になります。)

  3. でのベンチマークでtimeは、安定した状態のパフォーマンスは得られません。(これが、適切なベンチマーク ライブラリを実際に使用する必要がある理由です。Clojure の場合、Criteriumが標準的なソリューションです。)

ちなみに、(map #(/ %1 %2) xs ys)と簡単に書けます(map / xs ys)。

アップデート：

それぞれのケースで両方の入力として (質問テキストのように) 使用して、Criterium を使用しmapて元のバージョンとdo-with新しいバージョンのバージョンをベンチマークし、次の平均実行時間を取得しました。do-with(range 1 1000)

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

さらに、Var に格納されたベクトルを範囲ではなく入力として使用して、ベンチマークを繰り返しました (つまり、各ベンチマーク(def r (vec (range 1 1000)))の最初とr両方のコレクション引数として使用します)。当然のことながら、オリジナルdo-withが最初に登場しnthました。ベクターでは非常に高速です (さらにnth、ベクターを使用すると、seq トラバーサルに関連するすべての中間割り当てが回避されます)。

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

do-with線形時間の複雑さを持つ新しいものは次のとおりです。

(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))))
于 2013-08-05T07:40:54.597 に答える