211

「MapReduceで長いテキストの単語を数える方法」タスク以外に良い例は考えられませんでした。これは、このツールがいかに強力であるかを他の人に印象付けるための最良の例ではないことがわかりました。

私はコードスニペットを探しているのではなく、実際には単なる「テキスト」の例を探しています。

4

4 に答える 4

311

Map Reduceは、大量のデータを効率的に処理するために開発されたフレームワークです。たとえば、データセットに100万件のレコードがあり、それがリレーショナル表現で格納されている場合、値を導出し、これらに対してあらゆる種類の変換を実行するのは非常にコストがかかります。

たとえば、SQLの場合、生年月日を考えると、100万レコードに対して30歳を超える人の数を調べるには時間がかかります。これは、クエリの複雑さが増す場合にのみ、マグニチュードの順に増加します。Map Reduceは、データが分散方式で処理されるクラスターベースの実装を提供します

これがすべてについて説明しているウィキペディアの記事ですmap-reduce

もう1つの良い例は、map reduceを介して友達を見つけることは、概念を理解するための強力な例であり、よく使用されるユースケースです。

個人的には、このリンクは概念を理解するのに非常に役立つことがわかりました

ブログで提供されている説明をコピーする（リンクが古くなった場合）

友達を探す

MapReduceは、もともとGoogleで開発されたフレームワークであり、多数のドメインにまたがる大規模な分散コンピューティングを容易にします。ApacheHadoopはオープンソースの実装です。

詳細については詳しく説明しますが、2つの関数を定義することになります。map関数とreduce関数です。map関数は値を取り、キーと値のペアを出力します。たとえば、文字列を受け取り、単語の長さをキーとして出力し、単語自体を値として出力するmap関数を定義すると、map（steve）は5：steveを返し、map（savannah）は8：savannahを返します。 。map関数はステートレスであり、出力値を計算するために入力値のみが必要であることに気付いたかもしれません。これにより、値に対してマップ関数を並行して実行できるようになり、大きな利点が得られます。reduce関数に到達する前に、mapreduceフレームワークはすべての値をキーごとにグループ化するため、map関数が次のkey：valueペアを出力する場合：

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

それらは次のようにグループ化されます。

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

次に、これらの各行は、キーと値のリストを受け入れるreduce関数に引数として渡されます。この例では、特定の長さの単語がいくつ存在するかを把握しようとしている可能性があるため、reduce関数はリスト内のアイテムの数をカウントし、次のようにリストのサイズでキーを出力します。

3 : 3
4 : 3
5 : 2
8 : 2

削減は並行して行うこともでき、これも大きな利点をもたらします。次に、これらの最終結果を見ると、コーパスなどに長さ5の単語が2つしかないことがわかります...

mapreduceの最も一般的な例は、コーパスで単語が出現する回数をカウントすることです。あなたがインターネットのコピーを持っていて（私は幸運にもそのような状況で働いていた）、インターネット上のすべての単語とそれが発生した回数のリストが必要だったとします。

これにアプローチする方法は、所有しているドキュメントをトークン化して（単語に分割し）、各単語をマッパーに渡すことです。マッパーは、値とともに単語を吐き出します1。グループ化フェーズでは、すべてのキー（この場合は単語）を取得し、1のリストを作成します。次に、reduceフェーズは、キー（単語）とリスト（キーがインターネットに表示されるたびに1のリスト）を取得し、リストを合計します。次に、レデューサーはその単語とそのカウントを出力します。すべてが言われ、完了すると、インターネット上のすべての単語のリストと、それが出現した回数が表示されます。

簡単ですよね？mapreduceについて読んだことがあるなら、上記のシナリオは新しいものではありません...それはmapreduceの「Hello、World」です。したがって、これが実際のユースケースです（Facebookは実際に次のことを行う場合と行わない場合がありますが、これは単なる例です）。

Facebookには友達のリストがあります（友達はFacebook上で双方向のものであることに注意してください。私があなたの友達なら、あなたは私のものです）。また、多くのディスクスペースがあり、毎日何億ものリクエストに対応しています。彼らは、リクエストの処理時間を短縮できる場合は、計算を事前に計算することにしました。一般的な処理要求の1つは、「あなたとジョーには230人の友人がいます」機能です。誰かのプロフィールにアクセスすると、共通の友達のリストが表示されます。このリストは頻繁に変更されないため、プロファイルにアクセスするたびに再計算するのは無駄です（まともなキャッシュ戦略を使用できることを確認してください。ただし、この問題についてmapreduceについて書き続けることはできません）。mapreduceを使用して、全員を計算できるようにします。s一般的な友人は1日1回、それらの結果を保存します。後でそれはただのクイックルックアップです。私たちはたくさんのディスクを持っています、それは安いです。

友達がPerson->[Listof Friends]として保存されているとすると、友達リストは次のようになります。

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

各行はマッパーへの引数になります。友達リスト内のすべての友達について、マッパーはキーと値のペアを出力します。鍵はその人と一緒に友達になります。値は友達のリストになります。キーは友達が順番になるように並べ替えられ、友達のすべてのペアが同じレデューサーに移動します。これはテキストで説明するのは難しいので、それを実行して、パターンが表示されるかどうかを確認してみましょう。すべてのマッパーの実行が完了すると、次のようなリストが表示されます。

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

各行は、引数としてレデューサーに渡されます。削減機能は、値のリストを単純に交差させ、交差の結果と同じキーを出力します。たとえば、reduce（（AB）->（ACDE）（BCD））は（AB）：（CD）を出力し、友人AとBが共通の友人としてCとDを持っていることを意味します。

削減後の結果は次のとおりです。

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

これで、DがBのプロファイルにアクセスすると、すぐに調べて(B D)、3人の共通の友達がいることがわかります(A C E)。

于 2012-09-11T18:37:24.077 に答える
27

HadoopのようなMapReduce実装の最良の例の1つ。

ただし、これらはMapReduceアイデアのKey-Valueベースの実装に限定されていることに注意してください（したがって、適用性が制限されています）。

于 2012-09-11T20:57:16.243 に答える
5

MapReduceで実行できる使い慣れた操作のセットの1つは、通常のSQL操作のセットです：SELECT、SELECT WHERE、GROUPBYなど。

もう1つの良い例は、行列の乗算です。ここでは、Mの1行とベクトルx全体を渡し、M*xの1つの要素を計算します。

于 2012-09-11T18:36:51.690 に答える
3

時々私はMRの概念を人々に提示します。私は、人々に馴染みのある処理タスクを見つけて、それらをMRパラダイムにマッピングします。

通常、私は2つのことを取ります。

  1. Group By/Aggregations。ここで、シャッフル段階の利点は明らかです。シャッフルも分散ソートであるという説明+分散ソートアルゴリズムの説明も役立ちます。

  2. 2つのテーブルの結合。DBを使用する人々は、この概念とそのスケーラビリティの問題に精通しています。MRでどのように実行できるかを示します。

于 2012-09-12T09:49:12.220 に答える