サイトにアクセスするたびにページのアドレスをログに記録する分析プログラムを構築しているとしましょう。これにより、log.txtは次のようになります。
x.com/a
x.com/b
x.com/a
x.com/c
x.com/a
カウンターはなく、ログファイルだけであり、SQLは使用されません。これには、数千の固有のドメインアドレス（x.com/a x.com/b）に数千の要素が含まれているため、最も効率的な方法は何ですか。このリストを調べて、上位10個のURLを吐き出します。
私の最善の解決策は、ログファイルを調べ、そのドメインがハッシュテーブルに存在しない場合は、それをキーとして追加し、その値をインクリメントします。次に、ハッシュで最大10個の値を検索します。
スペースの複雑さ（一意のドメインが数千から数百万になったらどうなるか）だけでなく、ハッシュテーブルで別の検索を実行して最大のものを見つける必要があるため、これが最善の解決策であるとは確信していません。値。
数千または数百万のエントリの場合でも（アプローチは問題ありません）、平均O(n)実行時間は線形です（）ので、それほど悪くはありません。
ただし、スケーラビリティを高めたい場合は、 map-reduceアプローチを使用できます。
map(file):
for each entry in file:
emitIntermediate(getDomainName(entry),"1"))
reduce(domain,list):
emit(domain,size(list))
上記は効率的に(domain,count)タプルのリストを提供します、そしてあなたがしなければならないのはトップ10を選択することだけです。
トップ10の選択は、スケーラビリティのためにmap-reduce（分散）ソートを使用するか、最小ヒープを使用して行うことができます（ヒープで検出されたトップ10要素を維持しながら繰り返します）。2つ目は、このスレッドで詳細に説明されています
スペースの複雑さについて：64ビットシステムを使用している場合は、それをRAMとして使用し、OSに（必要に応じて要素をディスクに交換することで）できることを実行させることができます。あなたが64ビットマシン上に持っている仮想メモリの。別の方法は、ファイルシステム用に最適化されたハッシュテーブル（またはB +ツリー）を使用して、同じアルゴリズムを実行することです。
ただし、これが実際に当てはまり、データがRAMに適合せず、map-reduceを使用できない場合は、ディスクアクセスの数が多いため、並べ替えと反復がO(nlogn)より効率的になります（外部並べ替えを使用）と思われます。最小化され、ディスクアクセスはRAMアクセスよりもはるかに遅くなります。
毎回ファイルを検査するのは間違った方法だと思います。より良い解決策は、ファイルを解析してデータをデータベースにプッシュすることです（ravendb、または別のno-sqlが最も簡単なはずです）。そこに到達すると、非常に大量のデータがある場合でも、データのクエリは簡単になります。