MapReduceを勉強しよう - Java

MapReduceというのは、最近注目されているGoogleの分散処理アルゴリズムです。
最近って言っても2年以上前ですけどね…ｗｗ


始めに、MapReduceの処理はMapフェーズとReduceフェーズに分かれます。
Mapフェイズで、入力データを分割して処理。
Reduceフェイズで、処理したデータをまとめます。


まずはMapReduceの理解を深めるために、
ある小銭の束の合計金額をMapReduceの考え方を使って求めてみましょう。
1. Mapフェイズ
小銭を1,5,10,50,100,500円のグループに分けてそれぞれの枚数を数えます。そして、グループごとの合計金額を計算します。
2. Reduceフェイズ
グループごとの合計金額を全て足して、小銭の束の合計金額が求まります。

しかし、これだけだとMapReduceのすごさはちょっとわかりずらいですね。
じゃあもう少しスケールアップしてみましょう。

さて、小銭の数がもし50枚程度なら一人でもこの合計金額を計算することは簡単でしょう。
しかし、もし小銭が10000枚あったらどうでしょうか？

一人では大変ですよね。

じゃあ、6人でやりましょう。

私は1円、君は5円、ユーは10円、あなたは50円、お前は100円、あんたには500円をそれぞれ数えてもらいます。

最後に、みんなの求めた金額を足せば合計金額が求まります。
わかったかな？
このような分散処理の考え方がMapReduceというわけです。




さて次は、このMapReduceをJavaを使って体験してみましょう。

参考文献１を見て体験してください。


個人的には参考文献１のMapReduceはなんか違うなーって思ったんだけど
まあいいか、
一応、自分なりの解釈でメモ書きしておきます。


「ある文字列の英字をカウントする」プログラムについて考えます。

1. 準備
ある文字列は「abcaba」とします。
値を保持するためのMapEntryクラスを用意します。

MapEntry
char key;
int value;

2. Mapフェイズ
文字列を一文字ずつ読み取り、keyが文字、valueが1であるMapEntryオブジェクトを生成して、LinkedListに格納していきます。

abcaba
111111

MapEntryオブジェクトをソートします。

aaabbc
111111

このリストをa,b,cのグループに分けてさらに別のリストに格納します。 （入力データを分割）

  a  | b |c
aaa|bb|c
111|11|1

あとはa,b,cの要素ごとにカウント。

3. Reduceフェイズ
カウントした数をデータ保存用の配列に格納。そして、必要とあらば出力。


こんな感じかな。
MapとReduceの境目が微妙だけど…


参考文献
1. @IT「GoogleのMapReduceアルゴリズムをJavaで理解する」