Clojure

Reducer

Reducerは、標準的なClojureコレクションを操作するためのシーケンスを使う方法に代わるアプローチを提供します。シーケンス関数は通常、遅延評価され、順序どおりに適用され、中間結果を作成し、単一のスレッドで実行されます。しかし、多くのシーケンス関数(mapやfilterなど)は概念的には並列に適用でき、マシンがより多くのコアを持つようになるにつれて自動的に高速化するコードが生成されます。Reducerの考え方に関する詳細については、元のブログ 記事を参照してください。

Reducerは、リデュース可能なコレクション(自身をリデュースする方法を知っているコレクション)と、リデュース関数(リデュース中に実行する必要がある「レシピ」)の組み合わせです。標準的なシーケンス操作は、操作を実行するのではなく、リデュース関数を単に変換する新しいバージョンに置き換えられます。操作の実行は、最終的なリデュースが実行されるまで遅延されます。これにより、シーケンスで発生する中間結果と遅延評価がなくなります。

さらに、一部のコレクション(永続的なベクトルとマップ)はfoldableです。Reducerに対するfold操作は、以下のようにしてリデュースを並列に実行します。

  1. 指定された粒度(デフォルト=512要素)でリデュース可能なコレクションを分割する

  2. 各パーティションにreduceを適用する

  3. Javaのfork/joinフレームワークを使用して、各パーティションを再帰的に結合する。

コレクションがfoldingをサポートしていない場合、代わりに非並列reduceにフォールバックします。

reduceとfold

clojure.core.reducers名前空間(ここではrとしてエイリアス)は、代替のr/reduce関数を提供します。

(r/reduce f coll)
(r/reduce f init coll)

Reducer版の違いは次のとおりです。

  • Mapコレクションはreduce-kvでリデュースされます。

  • initが提供されない場合、fは引数なしで呼び出され、同一性値が生成されます。

    • 注:同一性値を提供するために、fは複数回呼び出される場合があります。

一般的に、ほとんどのユーザーはr/reduceを直接呼び出すことはなく、代わりに並列reduceとcombineを実装するr/foldを優先する必要があります。ただし、中間結果が少ないeagerなreduceを実行することが役立つ場合があります。

(r/fold reducef coll)
(r/fold combinef reducef coll)
(r/fold n combinef reducef coll)

r/foldは、リデュース可能なコレクションを受け取り、それを約n(デフォルト512)個の要素のグループに分割します。各グループはreducef関数を使用してリデュースされます。reducef関数は、引数なしで呼び出され、各パーティションで同一性値を生成します。これらのリデュースの結果は、combinef(デフォルトはreducef)関数を使用してリデュースされます。引数なしで呼び出された場合、(combinef)は自身の同一性要素を生成する必要があります - これは複数回呼び出されます。操作は並列に実行される場合があります。結果は順序を保持します。

次の関数(シーケンスバージョンと類似)は、リデュース可能またはfoldableなコレクションからReducerを作成します。r/map r/mapcat r/filter r/remove r/flatten r/take-while r/take および r/drop。これらの関数のいずれも、ソースコレクションを実際に変換しません。累積結果を生成するには、r/reduceまたはr/foldを使用する必要があります。出力コレクションを生成するには、clojure.core/intoを使用してコレクションの種類を選択するか、提供されているr/foldcatを使用して、リデュース可能、foldable、seqable、およびカウント可能なコレクションを生成します。

Reducerの使い方

+ を使用して fold で合計する

(require '[clojure.core.reducers :as r])
(r/fold + (r/filter even? (r/map inc [1 1 1 2])))
;=> 6

最終的なコレクションを生成するには into を使用します。

(into [] (r/filter even? (r/map inc (range 100000))))

または r/foldcat

(r/foldcat (r/filter even? (r/map inc (range 100000))))

fold で reduce 関数と combine 関数を指定する

(defn count-words
  ([] {})
  ([freqs word]
    (assoc freqs word (inc (get freqs word 0)))))

(defn merge-counts
  ([] {})
  ([& m] (apply merge-with + m)))

(defn word-frequency [text]
  (r/fold merge-counts count-words (clojure.string/split text #"\s+")))

いつ使うか

これらの操作のReducer形式を次の場合に使用します。

  • 複数ステップの変換を効率的にeagerに適用する場合

  • ぶら下がっているI/Oリソースの問題を回避する場合(遅延シーケンスで見られるように)

fold を使う場合

  • ソースデータが生成され、メモリに保持できる場合

  • 実行する作業が計算である場合(I/Oまたはブロッキングではない場合)

  • データ項目の数または実行する作業の量が「多い」場合