-2

これは一種のアルゴリズムの質問です。明確にするために、私は作業コードには興味がありませんが、一般的にタスクにアプローチする方法に興味があります。

4 つの CPU を備えたサーバーがあり、データベースはありません。ディスクには 100,000 の HTML ドキュメントが保存されています。各ドキュメントのサイズは 2MB です。そのコレクションに含まれる単語「CAMERA」(大文字と小文字を区別しない) の数を効率的に判断する方法が必要です。

私のアプローチは

  • HTML ドキュメントを解析して単語のみを抽出する
  • そして言葉を並べ替え、
  • 次に、そのコレクションでバイナリ検索を使用します。

言い換えれば、スレッドを作成して、4 つの CPU をすべて使用して HTML ドキュメントを 1 つの大きな単語コレクション テキスト ファイルに解析し、それを並べ替えて、バイナリ検索を使用できるようにします。

これについてどう思いますか？

4

5 に答える 5

2

grepを試しましたか？それが私がすることです。

非常に多くのデータを渡す正しい方法を見つけ出し、結果が正しいことを事前に確認するには、おそらく多少の実験が必要になるでしょう。これには少し時間がかかるためです。

それほど多くのデータをソートすることはお勧めしません。

于 2013-01-05T21:24:44.573 に答える
0

ドキュメントが単一のローカルハードドライブにある場合、CPUではなくI/Oによって制約されます。

私は、すべてのファイルをメモリにシリアルにロードし、メモリをスキャンしてターゲットワードを検索し、カウンタを増やすという非常に単純なアプローチを使用します。

速度を上げるために4つのスレッドを使用しようとすると（すべてのスレッドに25000ファイルなど）、I / Oは競合するプロセス/スレッドからの重複するアクセスパターンを好まないため、遅くなる可能性があります。

ただし、ファイルが複数のハードドライブに分散している場合は、ドライブと同じ数のスレッドを開始する必要があり、各スレッドはそのドライブからのみデータを読み取る必要があります。

于 2013-01-04T10:51:38.780 に答える
0

まあ、それは完全な疑似コードの答えではありませんが、それはないと思います。最適なパフォーマンスを得るには、ハードウェア アーキテクチャについて詳しく知る必要があります。ここにメモがあります：

  1. データを並べ替える必要も、バイナリ検索を使用する必要もありません。ファイルを読み取り（ディスクから各ファイルを順番に読み取ります）、カメラという単語が含まれているかどうかを検索します。
  2. ディスク アクセスは CPU 計算よりもはるかに遅いため、プログラムのボトルネックは IO (ディスク読み取り) である可能性が高くなります。したがって、プログラムを最適化するには、ディスク読み取りの最適化に集中する必要があります。
  3. ディスクの読み取りを最適化するには、そのアーキテクチャを知っておく必要があります。たとえば、ディスクが 1 つしかない (そして RAID がない) 場合、ディスクが同時に 1 つの要求を処理できると仮定すると、マルチスレッド化には意味がありません。その場合は、単一のスレッドを使用してください。
  4. ただし、複数のディスクがある場合は、コアの数に関係なく、#disks スレッドを生成する必要があります (ファイルがディスク間で均等に分離されていると仮定します)。これがボトルネックであるため、ディスクからデータを同時に要求する複数のスレッドを用意することで、それらすべてを機能させ、消費時間を効果的に大幅に削減します。
于 2013-01-04T10:53:44.793 に答える
0

何かのようなもの？

htmlDocuments = getPathsOfHtmlDocuments()
threadsafe counter = new Counter(0)
scheduler = scheduler with max 4 threads
for(htmlDocument: htmlDocuments){
  scheduler.schedule(new SearchForCameraJob("Camera",htmlDocument,counter))
}
wait while scheduler.hasUnfinishedJobs
print Found camera +counter+ times


class SearchForCameraJob(searchString, pathToFile, counter){
    document = readFile(pathToFile);
    while(document.findNext(searchString)){
    counter.increment();    
   }
}
于 2013-01-04T10:54:40.490 に答える
0

Boyer-Moore アルゴリズムを使用できます。このようなアプリケーションの作成に適したプログラミング言語を特定することは困難ですが、ネイティブ コードを直接最適化するために C++ で作成することができます。明らかに、マルチスレッドを使用する必要があります。
HTML ドキュメント解析ライブラリから、Xerces-C++ を選択できます。

于 2013-01-04T13:09:17.847 に答える