これは面接の質問です。数台のコンピューターがあり、各コンピューターがアクセスしたURLの非常に大きなログファイルを保持しているとします。最も訪問されたURLのトップ10を見つけます。
例：コンピューターが3台しかなく、最もアクセス数の多い上位2つのURLが必要であるとします。
コンピューターA：url1、url2、url1、url3 コンピューターB：url4、url2、url1、url1 コンピューターC：url3、url4、url1、url3 url1はすべてのログに5回表示されます url2 2 url3 3 url4 2 したがって、答えはurl1、url3です。
ログファイルが大きすぎてRAMに収まらず、ネットワークでコピーできません。私が理解しているように、計算を並列化し、指定されたすべてのコンピューターを使用することも重要です。
どのようにそれを解決しますか？
これはかなり標準的な問題であり、よく知られた解決策があります。各コンピューターのログファイルをURLで並べ替えてから、「マスター」コンピューターのサイズk（必要なアイテムの数）の優先キューを介してそれらをマージするだけです。この手法は1960年代から存在しており、現在でもMapReduceの形式で（わずかに変更されていますが）使用されています。
各コンピューターで、ログファイルからURLとカウントを抽出し、URLで並べ替えます。ログファイルはメモリに収まるよりも大きいため、ディスク上でマージする必要があります。これには、ログファイルのチャンクの読み取り、URLによる並べ替え、ディスクへのチャンクの書き込みが含まれます。次のチャンクの読み取り、並べ替え、ディスクへの書き込みなど。ある時点で、M個のログファイルチャンクがあり、それぞれが並べ替えられています。その後、M-wayマージを実行できます。ただし、アイテムをディスクに書き込む代わりに、並べ替えられた順序（つまり、URLで並べ替えられた順序）で「マスター」にアイテムを提示します。
各マシンは独自のログをソートします。
「マスター」コンピューターは、別々のコンピューターからのデータをマージし、上位Kの選択を行います。これは実際には2つの問題ですが、1つにまとめることができます。
マスターは2つの優先キューを作成します。1つはマージ用、もう1つは上位Kの選択用です。1つ目はサイズNで、Nはデータをマージするコンピューターの数です。2つ目はサイズKです。選択するアイテムの数です。簡単で適度に高速なので、これには最小ヒープを使用します。
マージキューを設定するには、キューを初期化し、各「ワーカー」コンピューターから最初のアイテムを取得します。以下の擬似コードでは、「マージキューから最下位のアイテムを取得する」とは、マージキューからルートアイテムを取得し、そのアイテムを提示した動作中のコンピューターから次のアイテムを取得することを意味します。したがって、キューにが含まれ[1, 2, 3]、アイテムがコンピューターB、C、Aから（この順序で）取得された場合、最も低いアイテムを取得すると、コンピューターBから次のアイテムを取得し、それを優先キューに追加することになります。
次に、マスターは次のことを行います。
working = get lowest item from merge queue
while (items left to merge)
{
temp = get lowest item from merge queue
while (temp.url == working.url)
{
working.count += temp.count
temp = get lowest item from merge queue
}
// Now have merged counts for one url.
if (topK.Count < desired_count)
{
// topK queue doesn't have enough items yet.
// so add this one.
topK.Add(working);
}
else if (topK.Peek().count < working.count)
{
// the count for this url is larger
// than the smallest item on the heap
// replace smallest on the heap with this one
topK.RemoveRoot()
topK.Add(working)
}
working = temp;
}
// Here you need to check the last item:
if (topK.Peek().count < working.count)
{
// the count for this url is larger
// than the smallest item on the heap
// replace smallest on the heap with this one
topK.RemoveRoot()
topK.Add(working)
}
この時点で、topKキューにはカウントが最も高いK個のアイテムがあります。
したがって、各コンピューターはマージソートを実行する必要があります。これはO（n log n）です。ここnで、はそのコンピューターのログ内のアイテムの数です。マスターでのマージはO（n）です。ここnで、は個々のコンピューターからのすべてのアイテムの合計です。上位k個のアイテムを選択するのはO（n log k）です。ここで、は一意のURLnの数です。
もちろん、並べ替えは並行して実行され、各コンピューターは独自の並べ替えリストを作成します。ただし、この種の「マージ」部分は、マスターコンピューターがマージされると同時に実行されるため、ある程度の調整が行われ、すべてのマシンがその段階で関与します。
ログファイルの規模と質問の一般的な性質を考えると、これを解決するのは非常に難しい問題です。すべての状況に最適なアルゴリズムが1つあるとは思いません。これは、ログファイルの内容の性質によって異なります。たとえば、すべてのURLがすべてのログファイルですべて一意であるというコーナーケースを考えてみましょう。その場合、基本的にどのソリューションもその結論を引き出すのに長い時間がかかります（それがそこまで進んだとしても...）、トップ10がないため、あなたの質問に対する答えすらありません。
提示できる防水アルゴリズムはありませんが、URL自体ではなく、URLのハッシュ値のヒストグラムを使用するソリューションを検討します。これらのヒストグラムは、ワンパスファイル読み取りによって計算できるため、任意のサイズのログファイルを処理できます。擬似コードでは、次のようなものを選びます。
このメカニズムでは、アルゴリズムとハッシュ関数のいくつかの側面に関して調整と最適化が必要になることに注意してください。また、どの計算をいつでも実行する必要があるかについて、サーバーによるオーケストレーションが必要になります。結論を導き出せない場合、つまりURLハッシュ値の「スペクトル」が平坦すぎて計算を続行する価値がない場合に結論を出すためにも、おそらくいくつかの境界を設定する必要があります。
ただし、URLに明確な分布がある場合は、このアプローチがうまく機能するはずです。とにかく、実際には、その場合にのみ質問が意味をなすのではないかと思います。
前処理：各コンピューターシステムは完全なログファイルを処理し、それらに対するカウントを含む一意のURLリストを作成します。
トップURLの取得：
PS：システム全体で上位10個のURLがあり、必ずしもこの順序である必要はありません。実際の順序を取得するには、照合を逆にすることができます。トップ10の特定のURLについて、dist-computersから個々のカウントを取得し、最終的な注文を作成します。
以下の条件が当てはまると仮定します。
私は以下のアプローチを取ります：
各ノードはファイルの一部（つまり、MAX urls、たとえばMAXは1000 urls）を読み取り、配列arr [MAX] = {url、hits}を保持します。
ノードがファイルからMAXURLを読み取ると、リストをマスターノードに送信し、MAXurlに再び到達するまで読み取りを再開します。
ノードがEOFに到達すると、残りのURLリストとEOFフラグをマスターノードに送信します。
マスターノードはURLのリストを受信すると、それを最後のURLのリストと比較し、更新された新しいURLを生成します。
マスターノードがすべてのノードからEOFフラグを受け取り、自分のファイルの読み取りを終了すると、リストの最後のバージョンの上位n個のURLが検索対象になります。
または
マスターをすべての仕事から解放する別のアプローチは次のようになります。
すべてのノードはファイルを読み取り、上記と同じ配列を格納し、EOFまで読み取ります。
EOFの場合、ノードはリストの最初のURLとヒット数をマスターに送信します。
マスターが各ノードの最初のURLとヒット数を収集すると、リストが生成されます。マスターノードのURLがn未満の場合、2番目のURLを送信するようにノードに要求します。マスターがn個のURLをソートするまで。
各ノードで、URLの出現回数をカウントします。次に、シャーディング関数を使用して、URLのキーを所有する別のノードにURLを配布します。これで、各ノードに一意のキーが割り当てられます。次に、各ノードで再び削減してURLの出現回数を取得し、上位N個のURLを見つけます。最後に、上位N個のURLのみをマスターノードに送信します。マスターノードは、K*Nアイテムの中から上位N個のURLを検索します。Kはノードの数です。
Eg: K=3
N1 - > url1,url2,url3,url1,url2
N2 - > url2,url4,url1,url5,url2
N3 - > url1,url4,url3,url1,url3
ステップ1：各ノードのURLごとの発生をカウントします。
N1 -> (url1,2),(url2,2),(url3,1)
N2 -> (url4,1),(url2,2),(url5,1),(url1,1)
N3 -> (url1,2),(url3,2),(url4,1)
ステップ2：シャーディングはハッシュ関数を使用します（簡単にするために、URL番号％Kとします）
N1 -> (url1,2),(url1,1),(url1,2),(url4,1),(url4,1)
N2 -> (url2,2),(url2,2),(url5,1)
N3 -> (url3,2),(url3,1)
ステップ4：ノード内の各キーの出現回数を再度見つけます。
N1 -> (url1,5),(url4,2)
N2 -> (url2,4),(url5,1)
N3 -> (url3,3)
ステップ5：上位Nのみをマスターに送信します。N=1とします
Master -> (url1,5),(url2,4),(url3,3)
結果を並べ替えて、url1である上位1つのアイテムを取得します
ステップ1はマップサイドリデュースと呼ばれ、ステップ2で発生する巨大なシャッフルを回避するために行われます。
以下の説明は、ソリューションのアイデアです。擬似コードではありません。
システムのコレクションがあると考えてください。
1.for each A：Collections（systems）
1.1）ログファイルで変更をプローブするdaemonAを各コンピューターで実行します。
1.2）変更に気付いたら、AnalyzerThreadAをウェイクアップ
します。1.3）AnalyzerThreadAが正規表現を使用してURLを見つけた場合は、localHashMapAをcount++で更新します。
（キー= URL、値=カウント）。
2）localHashMapAのtopTenエントリをAnalyzeAllデーモンが実行されるComputerAにプッシュします。
上記のステップは、各システムの最後のステップになります。これにより、topTenエントリがマスターシステム（たとえば、computerA）にプッシュされます。
3）computerAで実行されているAnalyzeAllは、重複を解決し、URLのmasterHashMapのカウントを更新します。
4）masterHashMapからtopTenを印刷します。