6

アマゾンのインタビューでこの質問をされました。

多くの行があるファイルがありますが、2行は同じです。それらの2行を見つけます。私はN^2時間で実行された明白な答えを与えました。次に、ハッシュテーブルを使用した回答を思いつきましたが、ファイルがギガバイト単位の場合は機能しないと言われているため、その回答も気に入らなかったのです。私が思いついたもう1つの答えは、ハッシュ結果をメモリに保存する代わりに、ハッシュ値と同じ名前のファイルを作成し、同じハッシュ値の行をファイルに保存することでした。彼らは私の解決策を理解できなかったか、彼らはそれを気に入らなかった。

何かご意見は？

ありがとう

4

3 に答える 3

4

この問題に対する2つの重要な解決策を考えることができます。

  1. 確率的なメモリ内ソリューション。 ファイルの行の要約をメインメモリに保存することで、この問題の解決を試みることができます。次に、メインメモリで計算を実行して重複の可能性を特定し、ディスクを振り返って重複の可能性を確認します。これらのソリューションは、メモリ使用量が少なく、効率が高く、ディスクアクセスを最小限に抑えるため、おそらく最良のソリューションです。このカテゴリのソリューションには次のものがあります

    1. ファイルの各行のハッシュを計算してから、ハッシュを保存します。ハッシュ衝突がある行は、衝突する可能性のある1組の行を表し、それらの行だけを探索できます。
    2. ブルームフィルターを使用してファイルのすべての行を保存し、ブルームフィルターで衝突するペアのみをチェックします。これは本質的に（1）のバリエーションであり、よりスペース効率が高くなります。

  2. 決定論的なオンディスクソリューション。メインメモリを一時的なスクラッチスペースとして使用して、ディスク上のデータセット全体を使用して計算を試みることができます。これにより、ファイル全体をメモリに保持しなくても正確な回答を得ることができますが、後で処理を行ってデータを再構築することでメリットが得られない限り、おそらく遅くなります。このカテゴリのソリューションには次のものがあります

    1. 外部ソートアルゴリズム（外部クイックソート、外部基数ソートなど）を使用してファイルをソートし、重複する要素のペアを線形検索します。
    2. すべての文字列を保持するBツリーのようなディスク上のデータ構造を構築してから、Bツリーにクエリを実行します。これには多くの前処理時間がかかりますが、ファイルに対する将来の操作がはるかに高速になります。
    3. すべてをデータベースに入れて、データベースにクエリを実行します。

お役に立てれば！

于 2012-12-06T21:40:49.310 に答える
2

ブルームフィルターを使用できます。

http://en.wikipedia.org/wiki/Bloom_filter

次に、繰り返される行を（誤検知がほとんどない状態で）検出してメモリに保存し、ファイルをもう一度確認できます。

ファイルを2回通過し、メモリ使用量が非常に少なく、美しい

于 2012-12-06T21:35:03.310 に答える
0

行を実行し、各行の長さを計算します。最終的には次のようになります。

0: 4  
1: 6  
2: 10  
3: 4  
....

同じ長さの線だけを比較してください。このようなインデックスの操作は、さらに最適化できます（たとえば、すべてをフラット配列に格納するのではなく、ある種のツリーなどに格納します）。

ちなみに、ファイルに関する2番目のアイデアは、パフォーマンス上の理由で拒否される可能性があります。ハードディスクでランダムIOを頻繁に使用することは一般的に悪い考えです。できるだけ多くのメモリに保存するようにしてください。

于 2012-12-06T21:34:06.730 に答える