秀吉とMapReduce

高校のとき数学の先生がよく授業の合間に雑談をしてくれた。そのなかで聞いた豊臣秀吉の話しが面白かったのでいろいろ絡めて紹介。

あなたはいきなり鬱蒼とした森に連れてこられて、「あの山に生えている樹の本数を可能なかぎり正確に数えてこい」って命令されたらどうしますか？　もちろん秀吉の話しなので部下はそれなりにたくさん居るとします。

山の表面積を計測して、ランダムに区画を選んでその中の樹を数えて、ひと山の概算をしますか？
それとも部下を何グループかに分けて麓から地道に樹の本数を数えながら登らせますか？
秀吉はどっちの方法もとらず、さらに精度が良い方法で樹の本数を部下たちに数えさせました。

それはこんな話し。

豊臣秀吉はあるとき、一つの山に何本の樹が生えているか調べるという任務を仰せつかった（理由は建築資材の見積もりだったかな？）。ひと山は広い。いちいち数えていたのでは何日経っても終わらないし、重複して数えるミスも出てくるだろう。

秀吉はどうしたか。

まずたくさんの紐を用意した。そしてその紐を部下たちに配りこう言った。
「あの山にある樹に紐を縛り付けてこい、ただし一本の樹に紐は一本だけしか縛ってはいけない」
たくさんの部下たちを動員してもう縛り付ける樹が見つからないほどその作業を続けた後、今度はこう言った。
「樹に縛り付けた紐を解いて持ってきなさい」
そして秀吉は集めた紐の数を数えてひと山の樹の本数を調べた。

「これは数学における１対１対応の応用である。秀吉はとても数学的な思考力を持った武将であった」と数学の先生は最後に付け加えた。

これってMapReduceの考え方とも似てないだろうか？

MapReduceっていうのは、Googleが膨大なサーバ群で分散処理を実行するときに使われているプログラミングフレームワーク。

MapReduceでは処理するデータをKey-Valueの組みとして扱い、それをプログラマが書いたMap関数とReduce関数で処理していきます。
ラフに説明するとMap関数では「Keyの値ごとにValueをどう処理するか」を書いて、Reduce関数では「処理結果を各Keyに対してどのように集計するのか」書く感じ。


MapReduce論文（PDF）のP.3, Figure 1の処理手順を書き出して、それに上記の秀吉の数え方を対応させてみよう。処理の詳細は同論文の”3.1 ExecutionOverview”から抜粋。

• Input files
• MapReduce（以下MP）:処理するデータを一定サイズに切り分ける
• 秀吉: 兵たちに紐を配る
• Map phase
• MR : 複数のWorkerがUser Programに従って切り分けたデータを処理する
• 秀吉: 兵たちが山に登って木に紐を縛り付ける
• Intermediate files
• MR: Map phaseで処理した結果を保持する
• 秀吉: 縛り付けられた紐（でいいのかな？）
• Reduce phase
• MR: Keyごとに保持された結果を集計する
• 秀吉: 兵に命じて縛り付けた紐を回収すると同時に本数を集計。
• Output files
• MR: 集計結果
• 秀吉: 紐の数すなわちひと山にある樹の本数

秀吉の方法が優れているのは動員する部下を増やせば増やすほど早く数えられるというところだろう。つまり作業の並列化によるスケールアウトができる。サーバを増やせば性能が比例して上がるWebのバックグラウンドシステムみたい。
１、２、３と数えて行く方法は並列化しづらいし、間違い防止やらで末端作業者の負担が大きい。
秀吉の方法では、末端の作業者には単純なルールを守らせるだけでミスを減らすことが出来る（一本の樹に一本の紐）。だから人員の調達も低コストで行える。
さすが後に天下を取る男、素晴らしく頭が切れて無駄がないですね。

ということで、
「豊臣秀吉は戦国時代からMapReduceを駆使する関数型武将だったんだよ！」「な、なんだってー!!」
というエントリでした。



･･････正直言いまして、上記のリストがMapReduceの説明に本当に合っているのか自信がありません。あと秀吉の逸話もソースが不明です。そこらへん、コメントで教えてくれる方がいたら有難いです。m(__)m