MapReduce と map 関数と reduce 関数を組み合わせたパターンの違い

なんでこんなめんどくさいタイトルになるのかといえば, それはすべて某 G が紛らわしいフレームワーク名をつけたからです. すべて某 G が悪い.

それはさておき, map 関数とか reduce 関数というのはリストに関数を適用する高階関数である. map 関数 とは, 1引数関数をリストの全ての要素に並行に適用する高階関数であり, reduce 関数とは, 2引数関数を2分木のようにリストに適用して1つの結果を得る高階関数である. これらは性質が良いため並列計算のパターンとしてセットでよく使われる.

MapReduce はおそらくこの辺のアナロジーから付けられた名なのだろう. 大体の流れは次のようになる.

リスト
  ↓ 分割
リストのリスト
  ↓ Map
結果のリスト
  ↓ Shuffle
並び替えられた結果のリスト
  ↓ Reduce
結果

元祖と比べると map も reduce も適用されるのは, 元のリストそのものではなく, 部分リストのリストであるし, shuffle されて順番が入れ替わるから, 可換でなくてはいけない.

微妙に違うとも言えるし, あまり違ってないとも言えるし, 面倒くさい... しかし, 並列計算の重要なパターンとフレームワーク名の混同だけは絶対によくないと思う.