Mapreduce1

最近、全く新しい知識が入らないので自発的に勉強中。
Mapreduceは、googleで利用されている分散処理アルゴリズム。
名の通り、"Map処理"と"Reduce処理"の2段階に分けて処理が行われる。
詳しくは末尾の参照ページをば。
内容をざっくり書くと...

  • Map処理
    • 入力情報に何らかの処理を加えて連想配列(Key-Valueの組み合わせの配列)*1を構築する処理
    • 入力情報が膨大であっても、分割可能な問題であればMap処理を行う処理系の数に入力情報を分割して分散して処理ができる
  • Reduce処理
    • Map処理で作られた連想配列をまとめる処理をして出力情報を作る*2

といった具合。
やってることはシンプルなのだけど、googleもこのアルゴリズムを使ったアプリケーションはかなり多く書かれているそうだ。


で、何かプログラムを書いてみないとわからないということで書いてみる。
ほとんど、下の参照ページ "www.joelonsoftware.com"のままですが...。JavaScriptで書いてみました。
あと、ここではMap処理の出力のKeyと入力のKeyが一致していますが、一致している必要は本来はないはずだし、もう少し別の書き方もある気がする。Umm....

var Mapreduce = Class.create();
Mapreduce.prototype = {
   initialize : function(){
   },
   map : function(fn, ary){
      for(i=0; i<ary.length; i++){
         ary[i] = fn(ary[i]);
      }
   },
   reduce : function(fn, ary, init){
      var s = init;
      for(i=0; i<ary.length; i++){
         s = fn(s, ary[i]);
      }
      return s;
   }
};
    • 配列の各要素を2倍してその合計を求めるというもの
mapreduce = new Mapreduce();
sample_ary = [1,2,3];
mapreduce.map(function(a){return a*2}, sample_ary);
s = mapreduce.reduce(function(x,y){return x+y;}, sample_ary, 0);
alert(s);


もしかしたら、まだ続くかもしれない。

*1:PHP的な言い方?

*2:大ざっぱすぎる理解かもしれない...