10 
(require '[clojure.core.reducers :as r])

(def data (into [] (take 10000000 (repeatedly #(rand-int 1000)))))

(defn frequencies [coll]
  (reduce (fn [counts x]
    (merge-with + counts {x 1}))
    {} coll))

(defn pfrequencies [coll]
  (r/reduce (fn [counts x]
    (merge-with + counts {x 1}))
    {} coll))


user=> (time (do (frequencies data) nil))
"Elapsed time: 29697.183 msecs"

user=> (time (do (pfrequencies data) nil))
"Elapsed time: 25273.794 msecs"

user=> (time (do (frequencies data) nil))
"Elapsed time: 25384.086 msecs"

user=> (time (do (pfrequencies data) nil))
"Elapsed time: 25778.502 msecs"

そして、大幅な高速化の例を誰が教えてくれますか?

Intel Core i7 (2 コア、 http://ark.intel.com/products/54617 )で Java 1.7 を搭載した Mac OSX 10.7.5 を実行しています。

4

3 に答える 3

19

これは、質問のタグpfrequenciesとともに、parallel-processing何かがここで複数のスレッドを使用していると思われることを示唆しています。そうではなく、レデューサー ライブラリの「主な」目標でもありません。

レデューサーが購入する主な点は、遅延シーケンスに多くの中間コンス セルを割り当てる必要がないことです。レデューサーが導入される前は、使用frequenciesするベクトルのシーケンシャル ビューを作成するために 10000000 コンス セルを割り当てていましたreduce。レデューサーが存在するようになったので、ベクトルはそのような一時オブジェクトを作成せずに自分自身を縮小する方法を知っています。しかし、その機能は にバックポートされておりclojure.core/reduce、まったく同じように動作r/reduceします (ここでは関係のないいくつかの小さな機能は無視します)。したがって、関数自体の同一のクローンに対して関数をベンチマークしているだけです。

reducers ライブラリには、 a の概念も含まれてfoldいます。これは、いくつかの作業を並行して実行し、後で中間結果をマージすることができます。これを使用するには、必要以上の情報を提供する必要reduceがあります。何もないところから「チャンク」を開始する方法を定義する必要があります。関数は連想でなければなりません。また、チャンクの結合方法を指定する必要があります。A.Webbの回答foldは、複数のスレッドで作業を行うために正しく使用する方法を示しています。

ただし、折り畳みからメリットを得られる可能性は低いです。彼が指摘する理由 (に比べてトランジェントをあきらめるclojure.core/frequencies) に加えて、マップの構築は簡単に並列化できません。の作業の大部分frequenciesが追加である場合 ( のようなものになるように(frequencies (repeat 1e6 1)))、次にfold役立ちます。しかし、ほとんどの作業はハッシュマップ内のキーを管理することであり、これは最終的にシングル スレッド化する必要があります。マップを並行して作成することはできますが、それらをマージする必要があります。その結合ステップには一定時間ではなく、チャンクのサイズに比例する時間がかかるため、チャンクを別のスレッドで実行してもほとんど得られません。

于 2013-05-20T18:16:35.647 に答える
4

ここでの回答には、真剣に考えるべきことがいくつかあります。この特定のケースでは、結果のドメインを簡単に予測して、インデックスを使用できるベクトルに入れることができるため、マップは必要ありません。したがって、単純な問題の単純な実装は次のようになります。

(defn freqs
  [coll]
  (reduce (fn [counts x] (assoc counts x (inc (get counts x))))
          (vec (int-array 1000 0))
          coll))

(defn rfreqs
     [coll]
     (r/fold
       (fn combinef
         ([] (vec (int-array 1000 0)))
         ([& cols] (apply mapv + cols)))
       (fn reducef
         [counts x] (assoc counts x (inc (get counts x))))
       coll))

ここで、combinef は、結果のコレクションの 1000 列に対する単純なマップの追加であり、無視できるはずです。

これにより、レデューサー バージョンは通常のバージョンよりも約 2 倍から 3 倍速くなり、特に大きなデータセット (10 倍から 100 倍) の場合に顕著です。微調整として、r/fold (オプションの「n」パラメーター) のパーティション サイズをいじることができます。1E8 のデータ サイズ (少なくとも 6GB の JVM が必要) で (* 16 1024) を使用するのに最適なようです。

両方のバージョンでトランジェントを使用することもできましたが、あまり改善が見られませんでした。

このバージョンが一般的な使用には適していないことはわかっていますが、ハッシュ管理のオーバーヘッドなしで速度が向上する可能性があります。

于 2013-05-21T15:13:59.420 に答える