4

C++のファイルシステムで重複ファイルを見つけたい。それをできるだけ速く行うためのアルゴリズムはありますか？また、マルチスレッドアプリケーションを作成する必要がありますか、それとも1つのスレッドを使用して作成できますか？

4

3 に答える 3

11

これには C++ よりも優れたツールがあるという Kerrek SB の意見に同意しますが、実際に C++ でこれを行う必要があると仮定して、実装で考慮すべきいくつかの提案と事項を次に示します。

  1. 移植可能なファイルシステムのトラバーサルに boost::filesystem を使用する

  2. ファイルごとのハッシュの提案は非常に合理的ですが、最初にファイルサイズが重要なマルチマップを作成する方が効率的かもしれません。次に、重複するサイズのファイルがある場合にのみハッシュを適用します。

  3. 空のファイルとシンボリック リンク/ショートカットをどのように処理するかを決定します

  4. 特別なファイルをどのように扱いたいかを決定しました。たとえば、unix では、ディレクトリ fifos、socket などがあります。

  5. アルゴリズムの実行中にファイルまたはディレクトリ構造が変更、消失、または移動する可能性があるという事実を考慮してください

  6. 一部のファイルまたはディレクトリにアクセスできない、または破損している可能性があるという事実を説明します (再帰的なディレクトリ リンクなど)。

  7. 意味のある並列化の量は、基盤となるディスク ハードウェアと構成に依存するため、スレッドの数を構成可能にします。シンプルなハード ドライブと高価なドライブを使用している場合は異なります。ただし、推測しないでください。テストしてみてください。たとえば、Linux はファイルのキャッシュに非常に優れているため、読み取りの多くはメモリから行われるため、I/O でブロックされません。

于 2012-08-01T13:52:30.267 に答える
9

1) C++ を使用しないでください。必要なツールはすべて既に存在しています。

2) すべてのファイルを (たとえば でmd5sum) ハッシュし、ファイル名、ファイル サイズ、およびハッシュ値のインデックスを作成します。*

3) ハッシュ値でソートし、重複するハッシュ値とサイズのペアを探します (例: を使用sort)。

diff4)重複候補に対して通常の処理を行います。

ステップ 2) は多少の作業で並列化できますが、ストレージの I/O 速度によって制限されます。ステップ 3) を並列化するには、大きなインデックス ファイルをビットに分割し、それらを個別に並べ替えてからマージします ( sort -m)。

*) @frankc が言うように、実際にはすべてのファイルをハッシュするのではなく、サイズが一意でないファイルのみをハッシュしてください。サイズベースのインデックスから始めます。多くの小さなファイルをハッシュする必要がありますが、大きなファイルはごくわずかです。

于 2012-08-01T13:36:06.473 に答える
5

私はこれを行います：

  • 各ファイルのサイズを調べて、関心のあるディレクトリをスキャンします。multimapファイルサイズをインデックスとして、ファイルサイズ/パスのペアを aに保存します。
  • multimap次に、キーごとに 1 つの要素だけを含むバケット (サイズが一意のファイル) をスキャンします。それらは確かに重複することはできません。
  • 残りのファイルの内容をハッシュし、以前と同じことを行います (multimapハッシュをキーとして、パスを値として)。
  • 次に、同じハッシュを持つファイルのみの実際の (バイトごとの) 比較を実行します。

このプロセスは、ほとんどのファイルのサイズが異なり、それを見るだけで区別できるため、すべてのファイルをやみくもにハッシュするよりもはるかに高速です。また、ファイル サイズのチェックは、ファイルの内容全体を読み取るのではなく、ファイル システム属性のルックアップにすぎないため、ファイルをハッシュするよりもはるかに安価です。

同じハッシュを持つ異なるファイルが存在する可能性があるため、最後の手順が必要です。しかし、関連のないファイルのハッシュ衝突は非常にまれであるため、適切なハッシュ関数を使用すると、ほとんどの作業は既に完了しています。

ハッシュ関数が暗号的に安全である必要も、特に高速である必要もないことに注意してください (このプロセスの時間は IO によって支配されると思います)。

また、ソートされたコンテナを実際に持つ必要はないので、 の代わりに をmultimap使用できます。unordered_multimapこれは、ルックアップ時間が短縮され、処理する必要があるファイルの数がわかればreserve、明確な要素の最大数、再割り当てを回避します。

于 2012-08-01T13:37:54.373 に答える