きしだのはてな このページをアンテナに追加 RSSフィード

2012-07-04(水) [翻訳]MVCは死んだ。MOVEするときがきた

[]MVCは死んだ。MOVEするときがきた 10:41 MVCは死んだ。MOVEするときがきた - きしだのはてな を含むブックマーク

Conrad Irwinさんの「MVC is dead, it's time to MOVE on.」を訳してみました。

MVC is dead, it’s time to MOVE on.


この訳文も原文のライセンスを引き継いでCC-BY-3.0ライセンスで利用可能とします。


追記13:58 すでに訳してた方がいました。MVCの時代は終わった。MOVEを使い始めましょう。 - ふじこのプログラミング奮闘記


MVCは死んだ。MOVEするときがきた

MVCはすばらしいアイデアだ。モデルを持ち、モデルは内部に少しの状態をもつ。ビューは内部に少しのUIをもつ。そして、コントローラは内部に少しの・・・


何を持つ?


私は確かにこのことに気づいた最初の人物ではない。しかし示されたようなMVCの問題のために、あなたは最後には過剰なコードをコントローラに詰め込むことになる。なぜなら、他にどこに入れていいかわからないからだ。

この問題を解決するために、私は「MOVE: モデル(M),オペレーション(O),ビュー(V),イベント(E)」という新しいパターンを使っている。


概要

Architecture of a MOVE app

詳細な定義はもう少しあとにしよう。この図はMOVEアプリケーションの基本的な構造を表している。

  • モデルはアプリケーションが知っていることを全てカプセル化する。
  • オペレーションはアプリケーションが行うことを全てカプセル化する。
  • ビューはアプリケーションとユーザーを仲立ちする。
  • イベントはこれら全てのコンポーネントを一緒に安全に結びつける。

スパゲティコードを避けるために、それぞれの種類のオブジェクトが何を許されるか、お勧めがあるということも記しておこう。これらは上図で矢印として示しておいた。例えば、ビューはモデルから発せられたイベントを待ち受けることができる。そして、オペレーションはモデルを変更することが許されている。しかしモデルはビューもオペレーションも参照しない。


モデル

典型的なモデルは「ユーザー」オブジェクトである。最低限はメールアドレスと、恐らく名前や電話番号を持つ。


MOVEアプリケーションでは、モデルは知識をラップするだけである。ということは、ゲッターやセッターに加えて、「これはこのユーザーのパスワードか」をチェックする関数を含んでもよい。しかし、データベースにユーザー情報を保存したり、外部APIにアップロードしたりする関数は含まない。それらはオペレーションの仕事である。


オペレーション

アプリケーション間で共通のオペレーションといえば、ユーザーのログインである。これは実際は二つのサブオペレーションを組み合わせたものだ。最初の1つはユーザーからメールアドレスとパスワードを得る。2番目は「ユーザー」モデルをデータベースから読み込んで、パスワードが正しいかチェックする。


オペレーションは、MOVEの世界での実行者である。それらは、モデルの変更を行い、正しいビューを正しいタイミングで表示し、そして、ユーザーの操作をきっかけにしたイベントに応答する役割を持つ。よく因子分解されたアプリケーションでは、それぞれのサブオペレーションはその親から独立して動かすことができる。これが上の図で、イベントの向きが上向きで、変更が下向きになっている理由である。


オペレーションをこのような方法で使うといいことは、アプリケーション全体で、プログラムがブートして開始するときと同じようにオペレーションを扱うことができることである。必要なだけ多くのサブオペレーションを生成して、それぞれの同時に存在するサブオペレーションを並列に動かし、そしてすべてが完了したときにプログラムが終わる。


ビュー

ログイン画面はいくつかのテキストボックスをユーザーに表示する役割を持ったビューである。ユーザーが「ログイン」ボタンをクリックすると、ビューはユーザーが入力したユーザー名とパスワードを持った「loginAttempt」イベントを引き起こす。


ユーザーが見るもの、操作するもの全ては、ビューによって制御される。アプリケーションの状態をわかりやすく表示するだけではなく、やってくるユーザーの操作のストリームを、意味のあるイベントに簡潔化する。大事なのは、ビューはモデルを直接変更せず、単純にオペレーションへのイベントを発する。そして、モデルから発せられるイベントを受けつけて変更を待つ。


イベント

「loginAttempt」イベントはユーザーが「ログイン」ボタンを押したときにビューから発せられる。加えて、ログインオペレーションが完了したときに、「currentUser」モデルはそれが変更されたことをアプリケーションに伝えるイベントを発する。


イベントの受けつけは、IoC、制御の逆転をMOVE(とMVC)に与え、モデルに直接どのビューを更新するか気づかせることなしに、そのモデルにビューの更新を可能にする。これは、強力な抽象化技術で、互いに妨げることなくコンポーネントを結び合わせる。


なぜ今?

MVCが悪いと暗示しているように誤解してほしくはない。それは確かに、大きなアプリケーションを組み立てるための、信じられないほど成功する方法であった。この数十年は。とはいえそれが発案されてから、新しいプログラミング技術が一般的になってきた。クロージャー(または匿名ブロック)なしでは、イベントの構築は非常に退屈である。そして、遅延制約(遅延評価やプロミスとして知られている)なしでは、個々のオペレーションをそれぞれのオブジェクトとして正しく扱うこのアイデアは、多くの意味をもたない。


繰り返すが、MVCは素晴らしい。しかし10年古い技術によって設計されている。MOVEは新しく我々が手に入れた道具を使って更新しただけだ。


P.S.

私はただ一人このように考え始めたわけではない。MOVEのアイデアを気に入ったなら、objectifyinteractionsをチェックしよう。これらはすでに存在するMVCアプリケーションにMOVEの利点を追加することを試みている。ここに追加するべきリンクを知っていたら教えてほしい

Conrad IrwinConrad Irwin 2012/07/04 11:23 Hi,

Thank you very much for translating this!

Conrad

rokugenrokugen 2012/07/04 13:06 因子分解はリファクタリングですか?

rokugenrokugen 2012/07/04 13:07 あ、すみません。自分で原文読めば良かったですね…自己解決しました。

nowokaynowokay 2012/07/04 15:53 factorですね。分解だけでなく、要素が最低限ってニュアンスも必要かなと思って「因子分解」としました。

tockritockri 2012/07/05 18:09 なにがMでVでCなのかを最適に決めたい、という手法としてイベントとオペレーションっていう考え方は一つ有効かもしれないですね。でも別にMVC死んでねえ…

nowokaynowokay 2012/07/05 18:33 MOVEがいいとしても、MVC死んでないね、たしかに

2012-06-04(月) 翻訳:平方根を使わずに高速で2点間の距離を近似する

[]平方根を使わずに高速で2点間の距離を近似する 10:37 平方根を使わずに高速で2点間の距離を近似する - きしだのはてな を含むブックマーク

2点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。

flipcode - Fast Approximate Distance Functions

(12:02 補足:おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう)


距離関数高速近似

by Rafael Baptista (27 June 2003)



2点間のユークリッド距離を求める計算式は次のようになる。

d = (x^2 + y^2 + z^2)^{¥frac{1}{2}}

二次元では次のようになる。

d = (x^2 + y^2)^{¥frac{1}{2}}


この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与えられた許容誤差に収まるまで繰り返す。もし、もっと制約の多いハードウェアで作業していて、ハードウェアでの平方根実装がなければ、小さい数の平方根の計算でさえも禁止されるだろう。


多くの計算で、二乗距離での比較が可能で、平方根をまったく使わないようにできる。例えば、必要な計算が距離の比較だけだと考えられるなら、二乗距離での計算は等価である。しかしながら、本当に距離を求めないといけない計算もある。あげてみると、ベクトルの正規化だとか、球面のバウンディングボリュームを使った衝突システムの実装だとか。


これらの場合に、標準的な距離関数を計算する余裕がないとして、距離関数のちょっといい近似をして、計算の簡単な線形演算だけで構成される関数クラスがある。理論上はもっと演算を追加することで、線形近似を保ったまま任意の精度で非線形関数を計算できる。実際これは、コンピュータで実装されるときに平方根関数が行うことと似ていないわけではない。ここで述べようとしている関数は、概して距離を2.5%の平均誤差で近似し、少ない線形計算の場合でだいたい最大5%の誤差あるが、そのため実行が非常に高速である。最大誤差と平均誤差のトレードオフの調整は可能で、そして誤差を適切な値にもってくるように関数を構成することも可能である。


最初に、正しい距離関数の3Dグラフを見てみよう。この3Dグラフはxとyで-1から1までの範囲のユークリッド距離をあらわす。グラフの高さは負の距離を表す。xとyが0のとき、距離は0であり、円錐の頂上になる。xとyの値を増やすと、それに応じて円錐の点は下がっていく。このグラフの断面は円のようになる。


ここに、xとyの絶対値の最大と最小の、xとyの範囲が-1から1までのグラフがある。最大のグラフは4面のピラミッドになる。xとyが0になる点は、このピラミッドの頂点になる。この断面は正方形になる。

最小値のグラフはピラミッドとは逆の操作になることがわかる。その断面は十字になる。


その結果、このふたつの関数の線形合成を行うと、距離関数へのちょっとよい近似を得ることができる。 最大と最小の異なった比率の値は異なる属性の近似を生成する。ここに挙げたものは、最大誤差を抑えるように調整してある。この関数を平均誤差が最小になるよう、もしくは平均二乗誤差が最小になるように調整することもできる。最大誤差になるのはxとyが0に近づくところであることがわかる。そして、これらは断面の形が理想円からもっともはずれる場所である。 (比率の項を調整することで、この点での誤差をゼロに減らすことは可能である。しかし、ほかの場所での精度を大きく犠牲にする)


これらの点での誤差を補正するため特別に設計した項を追加することで、この関数の精度をあげることができる。この場合、xやyがより大きいところ、xとyの小さいほうの16倍になるところだけで関数の比率を変えればよい。この新しい関数のグラフには、xやyが0に近づくところにギザギザがややできあがっていることを見ることができる。目的にあった誤差になるまで、処理を繰り返して総誤差を減らすことができる。もちろん、線形の項を追加すると、関数の計算はより高価になる。


計算したい、xとyの絶対値の最大と最小を伴った距離関数の近似を証明することは簡単だ。正しい距離関数を考えると、与えられたどんな距離Xについても半径Xの円を得る。本質的には円のグラフを直線で近似することを試す。xとyの絶対値を取るのは、距離関数の結果を変えないことに注意する。最初にxとyの絶対値を最初に取ることで、問題を円のひとつの象限だけの近似に減らすことができる。もうすこし考えると、xとyの最大最小をとることで、問題を8分円だけに限定できる。これは、ちょっとよい近似を少数の直線だけで得るのに十分小さい弧である。


これらの関数は非常に簡単に計算でき、最近のハードウェアでは定数時間で計算することができる。今回使った係数は1024の分数として表せることに注意する。これはこの関数を整数レジスタと少しの掛け算だけを使って実装するできることを意味し、最終的にシフトを使うだけで結果をスケールダウンできる。2の乗数になる分母を使った係数を選べば、これが可能になる。どれだけ多くのビットを使うかは、レジスタサイズと必要な精度に依存する。


これはひとつの近似関数の実装例である。

u32 approx_distance( s32 dx, s32 dy )
{
   u32 min, max, approx;

   if ( dx < 0 ) dx = -dx;
   if ( dy < 0 ) dy = -dy;

   if ( dx < dy )
   {
      min = dx;
      max = dy;
   } else {
      min = dy;
      max = dx;
   }

   approx = ( max * 1007 ) + ( min * 441 );
   if ( max < ( min << 4 ))
      approx -= ( max * 40 );

   // add 512 for proper rounding
   return (( approx + 512 ) >> 10 );
} 

この近似は、ハードウェアが制限されているのであれば、掛け算さえ使わずに実装することも可能である。


u32 approx_distance( s32 dx, s32 dy )
{
   u32 min, max;

   if ( dx < 0 ) dx = -dx;
   if ( dy < 0 ) dy = -dy;

   if ( dx < dy )
   {
      min = dx;
      max = dy;
   } else {
      min = dy;
      max = dx;
   }

   // coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min )
   return ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) +
            ( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 );
} 

(翻訳ここまで)


単語

原文で出てきた単語について

cross section断面
ideal理想の
diviate基準からはずれる
quadrant象限
demonstrate証明
constrain制限
coefficient係数
denominator分母

参考になる本

こういった、実数値を求めるような計算を数値計算だとか数値解析というけど、機械学習とかやろうと思うと知っておく必要がある。

数値計算の入門としてはこの本がおすすめ。

扱う範囲がしぼってあって、読みやすい。例はBASICだけど、なんとなくわかると思う。

数値計算のはなし―パソコンを使って解こう

数値計算のはなし―パソコンを使って解こう


具体的な計算の方法は、定番のニューメリカルレシピ。まあ古くていろいろ批判があってバグもあって、本当は新しい版の訳がほしいところだけど、手始めに。本気でやるなら原著の最新版のほうがいいです。


あと、テイラー展開とかは知っておく必要があるので、無印数学ガールなど読んでおくといいと思います。

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

さとうさとう 2012/10/24 22:55 試してみました。
最大でも誤差3%、多くの場合1%以内に収まるようです。
掲載ありがとうございます。

FPUの載っていないマイコンを使ったロボットの制御に応用させて頂きます。

nowokaynowokay 2012/10/25 19:15 おぉ、お役にたててよかったです

toriPtoriP 2012/12/26 01:12 掲載ありがとうございます。
ラジオのAM復調でこのアルゴリズムを使わせていただきました。
マイコンに処理させる関係で、軽いアルゴリズムを探していました。
助かりました。ありがとうございました。

nowokaynowokay 2012/12/27 16:03 やはりマイコンでの処理に向いてるんですね。

じゅんじゅん 2013/05/19 09:40 私の場合、大昔のゲーム機でゲームを作っていた時は、もっと粗い、max+3/8minで距離を出していました。
といっても画面の解像度が320x240程度だったので、やはり誤差は最大3%程度。1/60秒ごとに再計算するし、問題なかったです。
max,minを出すまでは同じで、あとはmin>>3して、max+min+min+min。
読んでて、1サイクルを気にする時代が懐かしくなりました。

nowokaynowokay 2013/05/19 12:25 おぉ、その計算だと8bitマシンにやさしそう!

2012-05-21(月) 翻訳:2012年のブラウザとアプリ

[]2012年のブラウザとアプリ 01:28 2012年のブラウザとアプリ - きしだのはてな を含むブックマーク

Tim Brayさんのブログでの、ブラウザとアプリの比較記事を翻訳しました。

http://www.tbray.org/ongoing/When/201x/2012/05/02/Web-Futurez


Browsers and Apps in 2012

Updated: 2012/05/15 Tim Bray


こんな感じ:ブラウザは終わってる。なぜなら、アプリに未来があるからだ。待って!アプリは終わってるよ、なんたってHTML5に未来があるから。私はほとんど毎日、どっちがどっちか言っているのを目にする。ただ、それはだいたい間違っている。

(もし私の意見を読みたくなかったら、この投稿の最後 の、数か月分のリンクに飛ぼう。この話題について読む価値があると思う。)


アプリの勝ち

もし、グラデーションやテクスチャ、タッチによって画面上にどんな反応があるかの高精度な制御を行った、没入型やインタラクティブに仕上げたかったら、アプリが必要だ。

端末のカメラをキャプチャして、どれだけ激しく振ったかでその色を変更して、振るのを止めるタイミングをユーザーの手に伝えるのにバイブさせたいなら、アプリが必要だ。

目的地までの5分のドライブを決めるための緊急の電話をかけるためには、アプリが必要だ。

電子ストアに並べて、労力なしで2タップで購入させて、月々の電話代で支払わせるなら、アプリが必要だ。

大きなゲームエンジン上の、すでにあるC++のシューティングゲームを、新しいモバイルプラットフォームに移植するなら、アプリが必要だ。


ブラウザの勝ち

アプリケーションが主に読みやすいテキストを配信して、周りに画像があって、ナビゲーションのリンクを含むなら、ブラウザでやろう。

どこかの電子ストアにならべて利用者のアクセス動作に課金することを望まないなら、ブラウザでやろう。

AndroidアプリとiOSアプリと(たぶんしばらくしたら)Windows Phoneアプリとを書く価値がないなら、ブラウザでやろう。

十分お金がなかったり最新のPocket Jewel*1を知らないような人も含め、いろいろなところのいろいろな人に到達したいなら、ブラウザでやろう。

アプリケーションのアップデートを、iOSウィークや、Androidのユーザー自身でののんびりしたアップデートではなく、まさに今、行う必要があるなら、ブラウザでやろう。


簡単なケーススタディ

アプリ絶対論者はInstagramやyepを取り上げることが好きだ。興味深いし、そのとおり。Scott Hanselmanによるこの幻想的な写真を考えよう。これはWebの一部?確かにそうじゃなきゃいけない。まさにここでリンクしているから。しかし、Google検索で見つけれる?直接は無理だ。Instagramは明示的に検索エンジンを避けている。しかし、そう、いくらかは好きにできる。この事例はすべてを証明する?各自で決めてほしい。


Developers! Developers! Developers! *2

私が少しオタッキーでモバイルソーセージ工場のモンスターに位置づけられてるとしても、もう少しつきあってほしい。


  • HTML5/ブラウザ技術は、急速に発達している。上に挙げたいくつかのトレードオフも変わっていくだろう。しかしそれは、モバイルアプリ技術もそうだ。事情は複雑だ。
  • モバイルアプリのプログラミングモデルは、DOM・JS・CSSとその仲間によるロココ調迷宮よりは良い。そうは言っても、なぜCoffeeScriptやDart、WebSocketsのようなものが存在する必要があるんだろう?事情は複雑だ。
  • この世界には純粋なものなどほんの少ししかない。多くの多くのアプリが内部でWebViewを持っていて、重たいコンテンツの表示を向上させている。事情は複雑と言おうか。

私には、ブラウザプラットフォームには、ソフトウェアの歴史の偉大な80/20ポイントに該当する、なにかシンプルで美しさを秘めたものがあるというのは、非常にありそうに見える。しかし私はそれが何かを、10年以上、今も考えている。


さらに読むもの

もちろん、この意見は「公開」を押したあと、朝にもすたれていくだろう。しかし、それでもなお。

http://www.tbray.org/ongoing/When/201x/2012/05/02/Web-Futurez#p-4

(リンク集は原文のほうを見てください)

*1:ゲームの名前?

*2:これはバルマーさんのパロディ?

2012-05-17(木) 翻訳:HTML5モバイルWebフレームワークの比較

[]HTML5モバイルWebフレームワークの比較 18:19 HTML5モバイルWebフレームワークの比較 - きしだのはてな を含むブックマーク

モバイル用でJavaScriptでアプリケーションを作成できるフレームワークについて比較した記事を翻訳しました。

Comparing HTML5 Mobile Web Framework - Dzyngiri


Comparing HTML5 Mobile Web Framework

Apr 27, 2012 by Dzyngiri


今年はモバイルWebにとって面白い年になっている。HTML5とCSS3の採択、モバイルブラウザのパフォーマンス向上、モバイルアプリケーションフレームワークの爆発は、モバイルデバイスでのリッチでインタラクティブなWeb体験の作成がこれまでよりも現実的になったことを意味する。PhoneGapのようなラッパを使うことで、iPhoneやiPad、AndroidのネイティブのAppストアでアプリケーションを配布することも可能になった。単一のコードベースでマルチプラットフォームを対象にして。


モバイルWeb開発者はたくさんのフレームワークを手にいれた。変形のアニメーション、ツールバー、ボタン、リストビュー、そしてオフラインストレージでさえも。これらの多くは新しく、状況はせわしく移り変わる。私は、多くのモバイルWebフレームワークを試してみて、比較・考察した。これらは私が気づいたことである。


jQTouch

jQTouchは利用が簡単で、比較的ドキュメントが整っている。それは「Building iPhone Apps with HTML, CSS, and JavaScript」ですばらしくまとめられている。jQTouchは、適切に作成されたHTML上でiPhoneのような体験の構築ができるよう、プログレッシブエンハンスメントのアプローチをとっている。簡潔であり、基本的なウィジェットやアニメーションのセットを提供していて、動的なふるまいをプログラムで制御するのに十分である。

(訳注:プログレッシブエンハンスメントは、どのブラウザでも見れるHTMLに追加でUI表現などを構築していく考え方)


しかし、私の単純なテストアプリケーションでさえも、パフォーマンスの問題があった。ページ遷移は飛び飛びだったり抜けていたりする。そしてタップイベントの応答には断続的な遅延がある。そして、プロジェクトは技術的にはアクティブであるけども、立ち上げの作者は異動してしまって、開発はゆっくりになっているように見える。


jQTouchは寛大なMITライセンスで利用可能である。これは私のお気に入りのオープンソースライセンスのひとつだ。


jQuery Mobile

jQuery Mobileは新しく売り出し中である。2010年8月にアナウンスされ、非常に機能的なAlpha2まで迅速に進み、今では2月28日にJQM 1.1.0が来た。これはjQTouchと同じような、しかしもっと標準に準拠したアプローチで、幅広いUIコントロールとスタイルのセットがあり、そのフレームワークの後継者として非常によく感じる。


jQuery Mobileのパフォーマンスは変化しやすい(しかしながら、jQTouchよりもよい)。特に、タップイベントへの反応でのアニメーションのレンダリングで。また、もっと動的なアプリケーションを簡単に作成できるようにする、少数のプログラム可能なフックも欠けている。実際に、ページが読み込まれたときに発生するイベントがある(例えばスライドして表示される)。しかし、どのUIエレメントがページ切り替えのきっかけになるかを関連付けられたハンドラコードに知らせる方法や、追加の情報をハンドラに渡す方法がない。回避策を作成することもできるが、将来のバージョンではjQTouchから手がかりをえて、このような機能性をもう少し構築することを望む。


2011年末と2012年始めに、jQuery Mobileは多くのWebギークの目にとまった。そしてモバイルWeb開発において最も改善されたフレームワークである。


jQuery MobileはMITライセンスかGPL2ライセンスで利用可能である。


Sencha Touch

Sencha TouchExt JSフレームワークに対するモバイル版である。このアプローチは、jQTouchやjQuery Mobileとは明確に異なっている。用意したHTMLに機能追加するのではなく、JavaScriptで作成したオブジェクトに基づくDOMを生成する。このように、Senchaでの作業には「Webっぽさ」は少なく、JavaやFlexなど他の技術でアプリケーションを構築するほうに近く感じる(jQueryよりはYUIにすこし近い)。私は個人的にはプログレッシブエンハンスメントのアプローチをお勧めするが、これは完全に好みの問題だ。


Senchaは非常に豊富なUIコンポーネント、明確なiPadサポート、JSONやHTML5オフラインストレージを使ったストレージやデータバインディング機能など、競合に比べてはるかに広範である(Senchaのデータ構造内のアプリケーションデータを操作すると、対応するリストにリアルタイムで表示されるのは、とてもクールだ)。ツールバーのように、リストなど他のコンポーネントがスクロールしても動かないオブジェクトを元からサポートしている、私が見た中では唯一のWebフレームワークでもある。


明白な重厚さにもかかわらず、Senchaのパフォーマンスは目に見えてよく、私のテストではjQTouchやjQuery Mobileよりも頼りになった。起動時のロード時間を除いては。


ライブラリやフレームワークを使うときには、通常「フレームワークとの戦い」を行ってから自分の作業に入る。Sencha Touchで広範な機能が与えられているというのは、アプリケーションのほとんど全てをSenchaの方法で行わないといけない可能性があるということだ。私はもともとWebKit組み込みのSQLiteデータベースをオフラインストレージを使っていたが、Senchaデータストアで動かすようにするのに、複雑さとバグとで最終的に取り除いた。


ドキュメントは、幅広くはあるが、半端な抜けがある。これらと険しいサイズのフレームワークであることの両方で、私は多くの時間を、たどって理解することが難しいバグとの戦いに費やした。デベロッパフォーラムでの私の質問に対する返答は、他のフレームワークに比べて高頻度で役に立った。しかしまだ最終的には不十分である。Senchaは$300/年からの有償サポートを提供しており、購入しようと強く考えたが、しかし奇妙なことに、私の販売担当の問い合わせへの返答は、信じられないほど送金への興味を失わせた。


Sencha TouchはGPL3ライセンスで使用可能である。いくぶんまぎらわしいGPLへの例外があり、LGPLと同等に見える。もしくは無償の商業ライセンスで利用できる。


Titanium Mobile

Sencha Touchに似て、AppceleratorのTitanium MobileはJavaScript APIでアプリケーションを書くことを可能にする。ただしSenchaとは異なり、ほとんどのコードをiPhoneやAndroidのネイティブコードにコンパイルする。これは、本来のWebフレームワークではないことを意味するが、互換性のレイヤーでありコンパイラーである。(これは姉妹品のTitanium Desktopは、Webベースでデスクトップ上のネイティブラッパで動くHTML/JSアプリケーションの記述を可能にする。)


TitaniumはWeb開発者にパフォーマンスの高い、スキンで外見を変えやすいネイティブアプリケーションをJavaScriptと少しのXMLを使うことで開発することを可能にする。Objective-CやCocoa Touchを学ぶ必要はない。私の単純なテストアプリケーションは、パフォーマンスの観点からは本来のWebフレームワークを立ち去らせた。そして両立させるのは難しいわけではない。


しかし、利点はまた大きな不利点でもある。Titaniumがサポートしているプラットフォームだけをターゲットにできる。そして開発ツールに疲れてしまう。この点を示すかのように、私のテストアプリケーションはさっさとiPhoneでは起動しない状態になってしまった。Titaniumはデバッガを含んでいない。TitaniumプロジェクトはXCode中で起動したりデバッグしたりできない。そしてシミュレータではうまく動き、問題に対処する現実的な方法がないままになっている。


考察

自分のアプリケーションをこれら4つのフレームワークのうち3つで構築しなおすことは退屈ではあったが勉強になった。私はjQTouchが好きではあるが、トラブルもあり、これからもっと進化すると信じている。jQuery Mobileの簡潔さと非常にWeb中心的な開発アプローチには声援を送る。しかしいくつか重要な機能が欠けており、Sencha Touchほどにはうまく動かない。


アルファ版の2つのプロダクトと1.0のプロダクトを比較するのは公平ではないが、ひとつ尊重するべき点を除いては。私はなにかを今必要としている。

私はSencha Touchに至った。最初はパフォーマンスと幅広さに印象付けられたが、その開発スタイルで利用に至った。私が掘り返したように、ドキュメントの穴にはがっかりしたが、幅広さには感激しつづけた。そして、そのコーディングスタイルに魅入られた。有償サポートがあることも関心を引く。そして、もし私のメールに答えてくれるなら、おそらく私は購入するだろう。しかし今は、焦点はSenchaベースのアプリケーションである。


まとめ

私は大きな問いに答えていない。Webベースのアプリケーションは本当にネイティブアプリケーションと並び立つだろうか。そうだとして、その挑戦で単一のコードベースの価値はあるだろうか。

答えはYESだ!なぜならWebベースのアプリケーションはHTML5とCSS3のコア知識を必要にするからだ。


訳注:参考文献

jQTouchであげられている書籍の邦訳


jQuery Mobileの本

jQuery Mobile

jQuery Mobile


Sencha Touchの日本語の本は見当たらないけど、Ext JSの本が役に立つと思う。

Sencha Ext JS 4実践開発ガイド

Sencha Ext JS 4実践開発ガイド


Titaniumの本

TitaniumMobile iPhone/Androidアプリ開発入門

TitaniumMobile iPhone/Androidアプリ開発入門

2012-02-23(木) 翻訳:MapReduceのパターン、アルゴリズム、そしてユースケース

[]MapReduceのパターン、アルゴリズム、そしてユースケース 02:23 MapReduceのパターン、アルゴリズム、そしてユースケース - きしだのはてな を含むブックマーク

Ilya Katsov氏による「MapReduce Patterns, Algorithms, and Use Cases」の翻訳

http://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/

(下書きに入れて推敲するつもりが、なんか公開されてしまっていたので、あとでいろいろ修正すると思います)


February 1, 2012

この記事では、Webや科学論文で見られる異なるテクニックの体系的な視点を与えるために、数々のMapReduceパターンとアルゴリズムをまとめた。

いくつかの実用的なケーススタディも提供している。

すべての説明とコードスニペットでは、Mapper、Reducer、Combiner、Partitionaer、ソーティングにおいてHadoopの標準的なMapReduceモデルを利用します。このフレームワークは、次の図に描かれています。


基本的なMapReduceパターン

カウントと合計

問題:多数の文書があり、それぞれの文書は単語の集合である。すべての文書内の各単語の出現数の合計を計算する必要がある。

もしくは、単語への任意の関数でもよい。例えば、ログファイルがあり、それぞれのレコードがレスポンス時間を含み、そして、レスポンス時間の平均を計算する必要がある。


解法:

本当にシンプルなものから始めよう。下のコードスニペットは、それぞれの単語ごとの処理で単純に「1」を発するMapperと、「1」のリストを走査してそれらを足し合わせるReducerを示す。

class Mapper
   method Map(docid id, doc d)
      for all term t in doc d do
         Emit(term t, count 1)

class Reducer
   method Reduce(term t, counts [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + c
      Emit(term t, count sum)

このアプローチの明らかな欠点は、Mapperから発せられた多量のダミーカウンターである。Mapperはそれぞれの文章についてカウンターを足し合わせることで、カウンターの数を減らすことができる。

class Mapper
   method Map(docid id, doc d)
      H = new AssociativeArray
      for all term t in doc d do
          h{t} = h{t} + 1
      for all term t in H do
         Emit(term t, count H{t})

ひとつの文章のためではなく、ひとつのMapperノードで処理されるすべての文章のためのカウンターを計算するために、Combinerを投入することができる。

class Mapper
   method Map(docid id, doc d)
      for all term t in doc d do
         Emit(term t, count 1)

class Combiner
   method Combine(term t, [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + c
      Emit(term t, count sum)

class Reducer
   method Reduce(term t, counts [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + c
      Emit(term t, count sum)

応用:

ログ解析、データクエリー


照合

問題:

要素の集合があって、ひとつの要素に対する関数がある。関数の値が同じになるすべての要素をひとつのファイルに保存するか、グループとして処理するすべての要素に対してほかの計算を行う必要がある。もっとも典型的な例は、転置インデックスの構築である。


解法:

解法はそのままである。Mapperはそれぞれの要素について与えられた関数を計算し、関数の値をキーとして出力し、要素はそれ自体を値として出力する。Reducerは関数の値によってグループ化されたすべての要素を得て、それらの処理や保存を行う。転置インデックスの場合は、要素は単語であり、関数は要素がみつかった文章のIDである。


応用:

転置インデックス、ETL

※extract, transform and load


フィルタリング(grep)、パース、バリデーション

問題:

レコードの集合があって、ある条件に合うかそれぞれのレコードを(他のレコードと独立して)別の表現に変換するすべてのレコードを集める必要がある。


解法:

解法は全くそのままである。Mapperはひとつずつのレコードを取り、受け取った要素か変換結果を出力する。


応用:

ログ解析、データクエリー、ETL、データバリデーション


分散タスク処理

問題:

複数の部分に分割できて、すべての部分からの結果を結合すると最終的な結果になるような、大きな計算問題がある。


解法:

問題の記述は要求内容の集合に分割されていて、要求内容はMapperの入力データとして保存される。それぞれのMapperは要求内容を取り、対応する計算を行い、結果を出力する。Reducerはすべての出力された部分を最終的な結果に統合する。


ケーススタディ:デジタル通信システムのシミュレーション

システムモデル内でいくつかのランダムなデータを受け渡し、スループットの誤り確率を計算する、WiMAXのようなデジタル通信システムがある。それぞれのMapperは必要なサンプリングの1/N番目の決められた量のデータのシミュレーションを行い、誤り確率を出力する。Reducerは誤り確率の平均を計算する。


応用:

物理的、工学的シミュレーション、数値解析、パフォーマンステスト


ソート

問題:

レコードの集合があってそれらのレコードをいくつかのルールで整列する必要があり、またはレコードを特定の順序で処理する必要がある。


解法:

単純なソートは完全にそのままである。Mapperはまさにすべての要素をソートキーに結び付けられた値として出力し、要素の関数のして組み立てられる。それでも、実際のソートはしばしば本当に技巧的な方法で使われ、MapReduce(Hadoop)の心臓部だといわれる理由でもある。特に、複合キーを二次的なソートやグルーピングに使うのは非常に一般的である。


MapReduceでのソートはもともとキーと値のペアをキーでソートするようになっているが、Hadoop実装を活用して値によるソートを行うがテクニックが存在する。

詳細についてはこちらのブログを参照。

http://www.riccomini.name/Topics/DistributedComputing/Hadoop/SortByValue/


もしMapReduceを(途中のデータはなく)元のデータをソートするために使うなら注目に値し、BigTableのコンセプトを使って継続的にデータがソートされた状態を維持するには、しばしば良いアイデアになる。言い換えれば、データをMapReduceクエリーのたびではなくデータ挿入の間に一度ソートすることは、もっと効果的になりうる。


応用:

ETL、データ解析


基本的ではないMapReduceパターン

走査的メッセージパッシング(グラフ処理)

問題:

エンティティとそれらの間の関係によるネットワークがある。それらの隣のエンティティの属性に基づいた、それぞれのエンティティの状態を計算する必要がある。この状態は他のノードへの距離や、隣に特定の属性をもったエンティティがあること、近所の密度の特徴などを示します。


解法:

ネットワークはノードのセットとして保存され、それぞれのノードは近隣のノードのIDの一覧を含む。概念的に、MapReduceジョブは走査的な方法でふるまい、それぞれのノードへのそれぞれの走査で、隣のエンティティにメッセージを送る。それぞれの隣人は受け取ったメッセージに基づいて状態を更新する。

走査は固定の最大走査回数(ネットワークの直径)や、2つの連続した走査の間での無視できる更新のような、いくつかの条件によって終了する。技術的な観点からは、Mapperは近隣のノードのIDをキーとして使ってそれぞれのノードを出力する。結果として、すべてのメッセージは受け取り側ノードでグループ化され、Reducerは状態を再計算して新しい状態でノードを上書きできる。このアルゴリズムを次のコードに示す。

class Mapper
   method Map(id n, object N)
      Emit(id n, object N)
      for all id m in N.OutgoingRelations do
         Emit(id m, message getMessage(N))

class Reducer
   method Reduce(id m, [s1, s2,...])
      M = null
      messages = []
      for all s in [s1, s2,...] do
          if IsObject(s) then
             M = s
          else               // s is a message
             messages.add(s)
      M.State = calculateState(messages)
      Emit(id m, item M)

ひとつのノードの状態はスパース過ぎないネットワークのすべてのネットワークの間を迅速に伝播することは強調すべきである。すべてのノードはこのノードがすべての隣人たちへ「感染」を開始することで「感染される」ためである。このプロセスを下の図に示す。


ケーススタディ:カテゴリのツリーを通じた可能性伝播

問題:

この問題は実生活でのeコマースタスクに触発された。大きなカテゴリ(男性・女性・子供など)から小さなカテゴリ(男性用ジーンズ・女性用ドレスなど)に枝分かれして、最終的に末端の小さなカテゴリ(男性用ブルージーンズなど)に行きつくようなカテゴリーのツリーがある。末端のカテゴリは有効(商品を含む)であったり無効であったりする。いくつかの高階層のカテゴリは、サブツリーの中に少なくともひとつの有効な末端カテゴリがある場合に有効になる。コールは末端のカテゴリの有効性がわかっているときに、すべてのカテゴリの有効性を計算することである。


解法:

この問題は前節で記述したフレームワークを使って解決することができる。getMessageメソッドとcalculateStateメソッドを次のように定義する。

class N
   State in {True = 2, False = 1, null = 0}, initialized 1 or 2 for end-of-line categories, 0 otherwise

method getMessage(object N)
   return N.State

method calculateState(state s, data [d1, d2,...])
   return max( [d1, d2,...] )

ケーススタディ:幅優先探索

問題:

グラフがあり、ひとつのソースノードからグラフ中のほかの全てのノードへの距離(ホップ数)を計算する必要がある。


解法:

ソースノードはoを全ての隣人に出力し、それらの隣人はこのカウンターを1増やしてそれぞれのホップの間で伝播させる。

class N
   State is distance, initialized 0 for source node, INFINITY for all other nodes

method getMessage(N)
   return N.State + 1

method calculateState(state s, data [d1, d2,...])
   min( [d1, d2,...] )

ケーススタディ:ページランクとマッパー側データ集約

このアルゴリズムはGoogleによって提案され、Webページの妥当性をこのページにリンクしているページの信頼性(PageRank)の関数として計算する。実際のアルゴリズムは全く複雑だが、その核心部分は、それぞれのノードで入ってくる重みの平均を重みとして計算する、ノード間の重みの伝播である。

class N
    State is PageRank

method getMessage(object N)
    return N.State / N.OutgoingRelations.size()

method calculateState(state s, data [d1, d2,...])
    return ( sum([d1, d2,...]) )

利用するスキーマは一般的すぎて、状態が数値であるという事実を活用していないことを言及する価値がある。多くの実用的な場面で、この事実のおかげで値の集計をMapper側で行うことができる。この最適化は次のコードスニペットで(PageRankアルゴリズム用に)示される。

class Mapper
   method Initialize
      H = new AssociativeArray
   method Map(id n, object N)
      p = N.PageRank  / s.OutgoingRelations.size()
      Emit(id n, object N)
      for all id m in N.OutgoingRelations do
         H{m} = H{m} + p
   method Close
      for all id n in H do
         Emit(id n, value H{n})

class Reducer
   method Reduce(id m, [s1, s2,...])
      M = null
      for all s in [s1, s2,...] do
          if IsObject(s) then
             M = s
          else
             s = s + p
      M.PageRank = s
      Emit(id m, item M)

応用:

グラフ解析、Webインデクシング


別個の値(ユニークアイテムカウント)

問題:

フィールドとしてFとGを含むレコードの集合がある。同じGを持つレコードのサブセットについて、フィールドFのユニーク値の合計を数える(Gでグループ化される)。


この問題は、ファセット検索としてちょっとした一般化と定式化をすることができる。

(訳注 ファセット検索:タグなどでの検索)


問題:

レコードの集合がある。それぞれのレコードはフィールドFと任意の数のカテゴリラベルG={G1, G2, ...}を持つ。それぞれのラベルの値によるそれぞれのレコードサブセットについてフィールドFのユニーク値の数を数える。


例:

Record 1: F=1, G={a, b}
Record 2: F=2, G={a, d, e}
Record 3: F=1, G={b}
Record 4: F=3, G={a, b}

Result:
a -> 3   // F=1, F=2, F=3
b -> 2   // F=1, F=3
d -> 1   // F=2
e -> 1   // F=2

解法I:

最初のアプローチは2つのステージで問題を解く。最初のステージでは、MapperはFとGのそれぞれのペアについてダミーカウンタを出力する。Reducerはそのようなペアのそれぞれについて発生数の合計を計算する。このフェーズの主なゴールはFの値のユニークさの保証である。2番目のフェーズでは、ペアはGでグループ化され、それぞれのグループの要素の総個数が計算される。


フェーズI:

class Mapper
   method Map(null, record [value f, categories [g1, g2,...)
      for all category g in [g1, g2,...]
         Emit(record [g, f], count 1)

class Reducer
   method Reduce(record [g, f], counts [n1, n2, ...])
      Emit(record [g, f], null )

フェーズII:

class Mapper
   method Map(null, record [value f, categories [g1, g2,...] )
      for all category g in [g1, g2,...]
          Emit(value f, category g)

class Reducer
   method Initialize
      H = new AssociativeArray : category -> count
   method Reduce(value f, categories [g1, g2,...])
      [g1', g2',..] = ExcludeDuplicates( [g1, g2,..] )
      for all category g in [g1', g2',...]
         H{g} = H{g} + 1
   method Close
      for all category g in H do
         Emit(category g, count H{g})

解法II:

2番目の解法はひとつのMapReduceジョブしか必要としない。しかしそれは本当にスケールするわけではなく、応用性は制限されている。アルゴリズムはシンプルである。Mapperは値とカテゴリを出力し、Reducerはそれぞれの値についてのカテゴリのリストから重複を除き、それぞれのカテゴリについてカウンタを増加させます。最終ステップでは、Reducerが出力したすべてのカウンタを合計します。

このアプローチは、同じfの値をもつレコードの数がそんなに高くなく、カテゴリの総数もまた制限されているときに適用できます。例えば、このアプローチはWebログの処理やユーザー分類の処理について適用できます。ユーザーの総数が高く、しかしひとりのユーザーに対するイベントの数が制限されて、分類するカテゴリーも同様の場合。このやり方では、Reducerにデータが送られる前に、カテゴリリストから重複を排除するためにCombinerが使えることは特筆に価する。

class Mapper
   method Map(null, items [i1, i2,...] )
      for all item i in [i1, i2,...]
         for all item j in [i1, i2,...]
            Emit(pair [i j], count 1)

class Reducer
   method Reduce(pair [i j], counts [c1, c2,...])
      s = sum([c1, c2,...])
      Emit(pair[i j], count s)

応用:

ログ解析、ユニークユーザーカウント


相互相関

問題:

要素のタプルの集合がある。要素のそれぞれのありうるペアについて、それらの要素が同時に起こるタプルの数を計算する。要素の総個数がNならば、N*N個の値が報告される。


この問題はテキスト解析(要素は単語、タプルはセンテンスと言う)、市場分析(これを買った顧客があれも買う傾向があるか)で表れる。N*Nがまったく小さく、そのようなマトリクスが一台のマシンのメモリに納まれば、実装はそのままできる。


ペアアプローチ:

最初のアプローチはすべてのペアとダミーのカウンタをMapperから出力し、Reducerでそれらのカウンタを合計する。欠点は

  • Combinerの利点が、すべてのペアが別個のような場合など限定的
  • インメモリでの計算がない
class Mapper
   method Map(null, items [i1, i2,...] )
      for all item i in [i1, i2,...]
         for all item j in [i1, i2,...]
            Emit(pair [i j], count 1)

class Reducer
   method Reduce(pair [i j], counts [c1, c2,...])
      s = sum([c1, c2,...])
      Emit(pair[i j], count s)

ストライプアプローチ:

2番目のアプローチはペアの最初の要素によってデータをグループ化し、すべての隣接要素についてのカウンタが計算される連想配列(ストライプ)として扱う。Reducerは基準になる要素iについてのすべてのストライプを受け取り、統合し、ペア亜プローとと同じ結果を出力する。

  • 少ない中間キーの生成。ゆえにフレームワークはソートを少なくできる。
  • Combinerからの多大な貢献
  • インメモリでの計算を行う。これは適切に実装されないと問題になりうる。
  • より複雑な実装
  • 一般的に、「ストライプ」は「ペア」より速い。
class Mapper
   method Map(null, items [i1, i2,...] )
      for all item i in [i1, i2,...]
         H = new AssociativeArray : item -> counter
         for all item j in [i1, i2,...]
            H{j} = H{j} + 1
         Emit(item i, stripe H)

class Reducer
   method Reduce(item i, stripes [H1, H2,...])
      H = new AssociativeArray : item -> counter
      H = merge-sum( [H1, H2,...] )
      for all item j in H.keys()
         Emit(pair [i j], H{j})

応用:

テキスト解析、市場分析


参照:

Lin J. Dyer C. Hirst G. Data Intensive Processing MapReduce

(邦訳:Hadoop MapReduce デザインパターン ―MapReduceによる大規模テキストデータ処理)


リレーショナルMapReduceパターン

この章では、主なリレーショナル操作を並べて、これらの操作がMapReduceの文法でどのように実装できるか議論する。


セレクション
class Mapper
   method Map(rowkey key, tuple t)
      if t satisfies the predicate
         Emit(tuple t, null)

プロジェクション(投影)

プロジェクションはセレクションに比べて少し複雑だが、この場合ありうる重複の排除にReducerを使うべきである。

class Mapper
   method Map(rowkey key, tuple t)
      tuple g = project(t)  // extract required fields to tuple g
      Emit(tuple g, null)

class Reducer
   method Reduce(tuple t, array n)   // n is an array of nulls
      Emit(tuple t, null)

ユニオン

Mapperには複合させる二つの集合のすべてのレコードが与えられる。Reducerは重複を排除するために使われる。

class Mapper
   method Map(rowkey key, tuple t)
      Emit(tuple t, null)

class Reducer
   method Reduce(tuple t, array n)   // n is an array of one or two nulls
      Emit(tuple t, null)

交差

Mapperには交差させる二つの集合のすべてのレコードが与えられる。Reducerは2度現れたレコードだけを出力する。これは両方の集合がこのレコードを含む場合だけ可能である。なぜならレコードは主キーを含みひとつの集合に一度だけしか現れない。

class Mapper
   method Map(rowkey key, tuple t)
      Emit(tuple t, null)

class Reducer
   method Reduce(tuple t, array n)   // n is an array of one or two nulls
      if n.size() = 2
          Emit(tuple t, null)

相違

2つのレコード集合を持ってみよう。RとSとする。RとSの違いを計算したい。Mapperはすべてのタプルとレコードがどの集合から来たかわかる名前のタグを出力する。ReducerはRからきてSから来ていないレコードのみを出力する。

class Mapper
   method Map(rowkey key, tuple t)
      Emit(tuple t, string t.SetName)    // t.SetName is either 'R' or 'S'

class Reducer
   method Reduce(tuple t, array n) // array n can be ['R'], ['S'], ['R' 'S'], or ['S', 'R']
      if n.size() = 1 and n[1] = 'R'
          Emit(tuple t, null)

グループ化と集約

グループ化と集約は、次のようにひとつのMapReduceジョブで行える。Mapperはそれぞれのタプルの値を抜き出してグループ化や集約、それらの出力を行う。Reducerはすでにグループ化された集約する値を受け取り、集約関数の演算を行う。合計や最大値のような典型的な集約関数はストリーミング方式で計算できる。ゆえにすべての値のハンドルは同時には不要である。とはいえ、いくつかの場合では2フェーズMapReduceジョブが求められるだろう。「別個の値」パターンをサンプルとして見るといい。

class Mapper
   method Map(null, tuple [value GroupBy, value AggregateBy, value ...])
      Emit(value GroupBy, value AggregateBy)
class Reducer
   method Reduce(value GroupBy, [v1, v2,...])
      Emit(value GroupBy, aggregate( [v1, v2,...] ) )  // aggregate() : sum(), max(),...

ジョイン

ジョインはMapReduceフレームワーク内で完全に可能であるが、効率や適応するデータのボリュームで異なるいくつかのテクニックが存在する。この章では、いくつかの基本的なアプローチについて勉強する。参照のセクションにはジョインのテクニックの詳細な研究へのリンクを含む。


リパーティションジョイン(Reduceジョイン、ソートマージジョイン)


このアルゴリズムは、二つの集合RとLをあるキーkでジョインする。MapperはRとLのすべてのタプルを処理し、タプルからキーkを抜き出し、このタプルが(RかLか)どの集合から来たか示すタグで印をつけ、タグ付けされたタプルをkをキーとして出力する。Reducerは特定のキーkについてのすべてのタプルを受け取り、RについてとLについてのふたつのバケットに入れる。ふたつのバケットが満たされたとき、Reducerはそれらの上でネストしたループを走らせ、バケットのクロスジョインを出力する。出力されたそれぞれのタプルはRタプル、Lタプル、そしてキーkで連結される。このアプローチは次の点で不利である。

  • Mapperは絶対的にすべてのデータを、ひとつの集合でしか現れずもう片方にペアがないキーでさえも出力する。
  • Reducerはひとつのキーに対するすべてのデータをメモリに置くことになる。もしデータがメモリにフィットしないならば、これをある種のスワップによってとりまわすのはReducerの責任である。

とはいえリパーティションジョインは、ほかの最適化されたテクニックが実用的でないときでもうまく使える、最も一般的なテクニックである。

class Mapper
   method Map(null, tuple [join_key k, value v1, value v2,...])
      Emit(join_key k, tagged_tuple [set_name tag, values [v1, v2, ...] ] )

class Reducer
   method Reduce(join_key k, tagged_tuples [t1, t2,...])
      H = new AssociativeArray : set_name -> values
      for all tagged_tuple t in [t1, t2,...]     // separate values into 2 arrays
         H{t.tag}.add(t.values)
      for all values r in H{'R'}                 // produce a cross-join of the two arrays
         for all values l in H{'L'}
            Emit(null, [k r l] )

リプリケートジョイン(マップジョイン、ハッシュジョイン)


実際には、小さな集合と大きな集合(言うなら、ユーザーのリストとログレコードのリスト)でのジョインが典型的である。

RとLの2つの集合をジョインすると仮定しよう。Rは相対的に小さいとする。もしそうなら、RはすべてのMapperに分散できて、それぞれのMapperはそれを読み込み、ジョインキーによってインデックスできる。ここでのもっとも共通で効果的なインデックステクニックはハッシュテーブルである。このあと、Mapperは集合Lのタプルを走査し、ハッシュテーブルに保持されているRからの対応するタプルとジョインする。このアプローチは非常に効果的である。なぜならネットワーク越しでの集合Lのソートや変換の必要がないからである。しかし、RはすべてのMapperに分散できるほど本当に小さくなくてはならない。

class Mapper
   method Initialize
      H = new AssociativeArray : join_key -> tuple from R
      R = loadR()
      for all [ join_key k, tuple [r1, r2,...] ] in R
         H{k} = H{k}.append( [r1, r2,...] )

   method Map(join_key k, tuple l)
      for all tuple r in H{k}
         Emit(null, tuple [k r l] )

参照:


  1. Join Algorithms using Map/Reduce
  2. Optimizing Joins in a MapReduce Environment

機械学習と数学MapReduceアルゴリズム