MapReduce：より高度な例、zaumiなしで試してください

先延ばしにしないために、トピック「 ZaumiなしのMapReduce 」で約束されているMapReduceの他の例をすぐに説明します。 （MapReduceとは何かを完全に理解していない場合は、まずそのトピックを読んでください！それなしでは理解できません）



ここで、都市の国籍の計算、学生の平均成績とドライブ、TIC、PageRank、インバウンドリンク、ニッチキーワード、同義語、ソーシャルネットワーク、相互の友人について話しましょう。 数学記号やざみなしでやろうとします。



ただし、トピック自体は複雑であり、脳に負担をかける必要があります。 あなたが理解するとき-それは非常に簡単になります。

インバウンドリンク

インターネットがあるとしましょう。 インターネットには外部へのリンクがあります。



入り口に、スパイダーによって収集された発信リンクに関するデータがあるとします。



habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com, yandex.ru

thematicmedia.ru -> habrahabr.ru, autokadabra.ru

autokadabra.ru -> habrahabr.ru, yandex.ru







つまり HabrがApple、MS、Ubuntu、Yandexを指すことを知っていますが、Habrを指すのは誰ですか？ はい、質問は原始的ですが、MapReduceで分解します。 さらに興味深いものになり、この例が必要になります。



Mapステップ（独​​自に作成）は次のことを行います。

（もう一度-内容がわからない場合は、「 zaumiを使用しないMapReduce 」をお読みください）。



例の「 //



」の後に来るものはすべてコメントであり、それがどこから来たのかを説明するだけで、MapReduceは直接関連していません。



map("habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com")



->

["thematicmedia.ru", "habrahabr.ru"] // thematicmedia.ru habrahabr.ru

["apple.ru", "habrahabr.ru"]

.....







map("thematicmedia.ru -> habrahabr.ru, autokadabra.ru")



->

["habrahabr.ru", "thematicmedia.ru"]

["autokadabra.ru", "thematicmedia.ru"]

....







「Reduce」ステップは何もしません。なぜなら、入力時に次のようになっているからです。



["autokadabra.ru", ["thematicmedia.ru"]]

["habrahabr.ru", ["thematicmedia.ru", "autokadabra.ru"]] <-- ,

....









ここに答えがあります-着信リンク。

どのサイトがTICまたはPageRankを提供しますか？

ああ、TIC、リンク取引の聖杯（2010 年頃 ）。 従来の評価単位をメガランクと呼びましょう（TIC、PageRankなどの可能性があります-違いはありません）。



このような理論を想定してください。各サイトには特定のMegaRankがあり、MegaRankをある程度「送信」するか、「送信しない」で一般に「殺す」ことができます。 最終サイトのMegaRankのみを知っているので、最初のうちどれがMegaRankを送信するかを知る方法は？



繰り返しますが、初期データがあります。サイトAにはMegaRank 100があり、サイトB、C、Dからの着信リンクがあります。 サイトBにはMegaRank 0があり（この理論を排除できないため、MegaRankは不良リンクによって「殺された」と仮定）、サイトA、D、E、Fなどからの着信リンクがあります...



タスクを次のように分解します。サイトAはB、C、Dから100に等しくなるものを受け取りました。B、C、DのそれぞれがサイトAに33単位のMegaRankを与えたと仮定します。 サイトBはMegaRankを強制終了しました。MegaRank= -500であり、ゼロではないと想定しています。 したがって、MegaRankを「殺す」人を大幅に過小評価しようとします（これは、広告の質が低く、検索エンジンによって控えめにされているサイトAとしましょう）。 サイトA、D、E、Fのそれぞれが、サイトBに-500/4 = -125単位のMegaRankを与えたことがわかります。



発信リンクを着信リンクで数える方法-私はすでに上記で説明しましたが、すでにこれを行っていると仮定します...



したがって、入力データがあります。



A (100) <- B,C,D // MegaRank=100 B,C,D

B (-500) <- A,D,E







「マップ」は次のことを行います。



A（100）<-B、C、D：

B, 100/3 = 33 // B 33 MegaRank B A

C, 33

D, 33







B（-500）<-A、D、E、F：

A, -500/4 = -125

D, -125

E, -125

F, -125







Reduceのステップでは次のことが行われます。



A (-125) // "" -125 MegaRank

B (33)

C (33)

D (33, -125) // "D" 33-125 = -92 MegaRank

E (-125)

F (-125)







再度Reduceを実行すると、A、E、Fなどの最も価値のないサイトであり、他のデータがない場合、MegaRankがゼロのサイトのみを参照します。 しかし、Dは、AとBの両方を指すという事実にもかかわらず、「疑わしい」が、Aよりも優れている。



これで、MegaRankによって送信された降順で、ザミのないMapReduceの例を使用して（人気順にソート）並べることができます。



この例は、MapReduceが必要な理由をよりよく示しています-数十億のリンクで同時に数百万のサイトを分析し、1台のマシンでもメモリが限られているという問題に遭遇し、他のマシンを接続して並列処理を強化できます



（そして、あなたが尋ねる前に-はい、私はTICで理論をチェックしました、はい、それは動作します:)私は何とか興味のないこのTICを持っています）。



したがって、サイトからの発信リンクと、これらのリンクが向けられているサイトの特定のパラメーター（TIC、PageRank）のデータのみがあるため、このパラメーターに合格するサイトを見つけることができます。

都市の人口の割合

Gorod1のGdetto地方に150人のロシア人、190人のベラルーシ人、3​​人のUdmurtが住んでおり、Gorod1のTutto地方に3人のロシア人、5人のベラルーシ人が住んでいる都市地区に関する情報があるとします。



ここでのタスクは、都市の人口の割合を計算することです（これらの都市の地域で知っています）。 問題？ 数百万の地区、データは都市ごとにグループ化されておらず、すべてが一緒になってメモリに収まりません...



MapReduceで非常に簡単：



「地図」：



map(" Gdetto Gorod1 150 , 190 , 3 ")



->

"gorod1", [ (150, ""), (190, ""), (3, "") ]







map(" Tutto Gorod1 3 , 5 ")



->

"gorod1", [ (3, ""), (5, "") ]







map(" Butto Gorod2 1 ")



->

"gorod2", [ (1, "") ]







「削減」：



入り口で：

"gorod1", [ (150, ""), (190, ""), (3, ""), (3, ""), (5, "") ]

// , -

"gorod2", [ (1, "") ]







これらの値を加算するだけで、すでに記憶に収まり、各都市の人々の数で割ることができるのは明らかだと思います。



これを行う方法の別のオプション-あなたは自分で考え出すことができます。

誰が少なくとも2人の一般的な友人を持っていますか？

A、B、C、D、E-たとえば、SocketにFingersがあるソーシャルネットワークの3,000万人のユーザーによって発明されたとします。 次のことを知っているとします：



B, D, E

B A, D, E

C B, E







少なくとも2人の共通の友人がいる人を見つけるにはどうすればよいですか？



（推測？）MapReduceで非常に簡単です。 私たちは、一人一人の友人のカップルごとにブルートフォースを取り、最初の場所に置きます。



「地図」：



(B,D), A // "" " B D"

(B,E), A

(D,E), A

(A,D), B

(A,E), B

(D,E), B

(B,E), C







「Reduce」は受信します（2番目の要素が複数の値を持つすべての行を選択する以外は何も行いません）：



(A,D), (B) // "A,D" "B"

(A,E), (B)

(B,D), (A)

(B,E), (A,C) <-- - "B,E" "" ""

(D,E), (A,B) <--







答えは：



AとCには共通の友人B、Eがいます

AとBには共通の友人D、Eがいます



できた！ Algortime O（n ² ）は、タンクにいる人にとっては、大量の入力データがあれば、太陽が消える少し前に作業を完了する可能性が高いことを意味します。 実際には、もちろん前に、しかし二次アルゴリズムは悪いです。

キーワードでニッチなトピックを見つける

いくつかのキーワードがあるとしましょう：























それらの中で何を書くことができるかを強調したいとします。 このような「ニッチ」トピックは、この単語が参加する少なくとも2つの異なるキーワードを持ち、それ自体がキーワードであるものと見なすことができます。 たとえば、「コーヒーメーカー」と「babrababrコーヒーメーカー」は「コーヒーメーカー」がトピックですが、「ガレージ」はそれ自体がキーワードではないため、ニッチではありません。 「マイル」は「ニッチ」でもありません。なぜなら、それ自体を除いて、異なるキーワードがないからです。 まあどう？ MapReduceなしで見つける準備はできましたか？ :)



そしてそれは非常に簡単です。 各行を単語に分割します（できればn-gramに分割しますが、それはあなた自身です）。 それらのそれぞれについて、この単語が行全体を占める場合は「FULL」を発行し、一部のみを占める場合は「PART」を発行します。 つまり 上記の例から：



「地図」：



, PART // " "

, PART // " "

, FULL // ""

, FULL

, FULL

, PART

, PART

, PART

, FULL

, FULL







入り口の「削減」は以下を受け取ります：



, (PART, FULL)

, (FULL, PART, PART)

, (PART)

, (PART, FULL, FULL)

, (FULL)









ここで、PARTおよびFULLがある場所を見てください。「babrababr」、「gates」、および「coffeemakers」-私たちが探していたのは「ニッチ」でした。

仮名を検索する

インターネットがあるとしましょう。 そこには多くのフレーズがあると仮定しますが、その中に「大きなコンピューターを買った」、「高価なコンピューターを買った」などのフレーズがあることに気づきます...ここでは、「高価な」と「大きな」は擬似同義語だと思います。 Gotoooo検索エンジンが不良サイトを破棄するまで、不良サイトを作成してWebCashを獲得する必要があります。



問題は、何十億もの単語があり、十分なメモリがないことです。 はい、それは「昨日コンピュータを買った」ことが判明するかもしれません、そして「昨日」は全く「大きく」なく、一般にそれは一度偶然それを乗り越えました...どうすればいいですか？ 使用するアルゴリズム（申し分なく、申し分なく、石を取り除きます。皆さんが推測したことはわかっています）。 行こう！



入力データを取得し、そこから3つの単語を選択するために、必要なものだけを残しておきます。

" "

" "

" "

" "

" "







ステージ1（2つのステージのカスケードが必要です）：



「地図」：



" * ", "" // " "

" * ", "" // " "

" * ", ""

" * ", ""

" * ", ""







アスタリスクは単なるアスタリスク記号であり、これは「任意の単語がここにある」ことを意味するため、Reduceは次のようになります。



" * ", ["", "", ""]

// "" ""



" * ", ["", ""]







Reduceは何もしません。



ステージ2（カスケード）：



「マップ」-入力は少し高く書かれたものを受け取り、2番目の値（["big"、 "yesterday"、 "dear"]）からの徹底的な検索によってペアを提供します。



, // ["", "", ""]

, // ["", "", ""]

, // ["", "", ""]

, // ["", "", ""]

, // ["", "", ""]

, // ["", "", ""]



, // ["", ""]

, // ["", ""]







Reduceでは、次のようになります。



, (, , )

, (, )

, (, , )







どこかに引用符があることに注意を払ってはいけません。これには秘密の意味はありません。どこかに引用符を付けてください。



現在、「Reduce」はカッコ内の単語（引数の2番目の要素）のみをカウントできるため、メモリに収まり、1回だけ出現する要素を破棄します。



- (2) // "" - "", 2

- (2)







できた！ 複雑さO（n ² ）再び！

参加する

結合する必要がある2つのMapReduceが既にあるとします。 MapReduceの1つは、1ダースの教師の雑誌のクラスの生徒の平均成績を平均と見なし、2つ目のMapReduceは、数百の警察署のデータに基づいて、過去1年間の生徒の警察への運転回数を考慮したとします 2つのMapReduceを1つの結果にマージするにはどうすればよいですか？つまり、INNER JOINまたはOUTER JOINを作成できます。



最初のMapReduceがプロデュースする（スコア）：

, ("", 3.5)







そして、2番目のMapReduceが生成しました（ドライブ）：

, ("", 2)







次に、これをすべて連続して直接送信します。

, ("", 3.5)

, ("", 2)







次に、「削減」で以下を受け取ります。

, [ ("", 3.5), ("", 2) ]

結論の代わりに

MegaRank、ニッチ、友人、同義語、国、二人組がMapReduceの唯一の使用法とはほど遠いことは明らかですが、今のところ、これを使用する方法について考え始めるにはこれで十分だと思います。 私は彼のために多くのアプリケーションを見つけました、そして、私は常にそれを使います。



すでに述べたように、ほとんどすべてのSQLクエリはMapReduceで分解されるため、少しトレーニングするだけです。 なんで？ 次に、高速化するために、SQLに必要な関数が必ずしもすべて存在するとは限りません。 たとえば、入力行からのn-gram（冗長フレーズ）の同じジェネレーター...もちろん間違っているかもしれませんが、MapReduceがドロップデッドであり、非常に有用である（そして同時にネットワーク上で驚くほど巧妙に記述されている）ことは事実です。 MapReduceネットワークにドラッグできるようになったことを願っています。



最後のトピックでは、PythonおよびPHPのMapReduceのリファレンス実装があります。



ヨイハジ

いつものように、Habrから

2010



（いつか簡単に説明することを学びます....）