0

テキスト ファイル (約300M ) があり、最も頻繁に発生する 10 の単語をカウントする必要があります (いくつかのストップ ワードは除外されます)。テスト マシンには 8 コアと Linux システムがあり、任意のプログラミング言語を使用でき、オープン ソース フレームワークのみを使用できます（hadoop はオプションではありません）。マルチスレッド プログラミングの経験はありません。ソリューションのコストを可能な限り短縮しますか?

4

4 に答える 4

0

300M は大したことではありません。適切に実行すれば、python のような高レベルのインタープリター言語でのシングルコア処理であっても、タスクにとっては数秒です。Python には、多くの下位レベルの言語と比較して、単語カウント プログラミングのコーディングとデバッグが非常に簡単になるという利点があります。それでも並列化したい場合 (Python でシングルコアを実行するのに数秒しかかからない場合でも)、誰かがそれを行うための迅速かつ簡単な方法を投稿できると確信しています。

于 2013-08-12T14:07:41.987 に答える
0

優れたスケーラビリティでこの問題を解決する方法:

この問題は、次の 2 つの map-reduceステップで解決できます。

ステップ1：

map(word):
   emit(word,1)
Combine + Reduce(word,list<k>):
   emit(word,sum(list))

このステップの後、あなたはのリストを持っています(word,#occurances)

ステップ2：

map(word,k):
   emit(word,k):
Combine + Reduce(word,k): //not a list, because each word has only 1 entry.
   find top 10 and yield (word,k) for the top 10. //see appendix1 for details

ステップ 2 では、単一のレデューサーを使用する必要があります。この問題 (単一のレデューサー) には10*#mappers入力としてエントリしかないため、問題は依然としてスケーラブルです。

300 MB ファイルのソリューション:

実際には、300MB はそれほど大きなファイルではないため、 (メモリ上に、ツリー/ハッシュ ベースのマップを使用して)ヒストグラムを作成し、そこから上位 k 値を出力することができます。

同時実行をサポートするマップを使用すると、ファイルを部分に分割し、必要に応じて各スレッドに変更させることができます。実際に効率的に分割できるかどうかは FS に依存し、場合によっては 1 つのスレッドによる線形スキャンが必須であることに注意してください。

付録 1:
上位 k を取得する方法:

最小ヒープを使用して要素を反復処理すると、最小ヒープには常に最高の K 個の要素が含まれます。

Fill the heap with first k elements.
For each element e:
     If e > min.heap():
         remove the smallest element from the heap, and add e instead.

また、詳細はこのスレで

于 2013-08-12T14:21:31.327 に答える