5

現在、可変サイズの ArrayList 内の各ファイルを比較する必要があるプログラムを作成しています。現在、私がこれを行っている方法は、ネストされたコード ループを使用することです。

         if(tempList.size()>1){
            for(int i=0;i<=tempList.size()-1;i++)
                //Nested loops.  I should feel dirty?
                for(int j=i+1;j<=tempList.size()-1;j++){
                    //*Gets sorted.
                    System.out.println(checkBytes(tempList.get(i), tempList.get(j)));
                }
            }

ネストされたループの必要性についていくつかの異なる意見を読みましたが、より効率的な代替手段があるかどうか疑問に思っていました。

一見すると、どちらの方法でも各比較を行う必要があるため、パフォーマンスはかなり安定しているはずですが、これを行うためのよりクリーンな方法があるとある程度確信しています。ポインタはありますか？

編集:: わかりやすくするために、これは関数の一部にすぎません。ファイルは比較され、長さに基づいてバケットに入れられました。セットのマップを調べて、長さが 1 より大きいバケットを見つけた後、これを実行します。つまり、これらはすべて同じサイズのファイルです。バイトに到達する前にチェックサムの比較も行いますが、今はループをクリーンアップしようとしています。

また、このサイトは迅速に対応します。みんなありがとう。

EDIT2:: 申し訳ありませんが、さらに明確にするために: ファイル処理部分については、私が十分に把握していると思います-最初に、長さ、次にチェックサム、次にバイトで比較してソートします-問題は、適切にすべてを比較する必要があると仮定して、ArrayList 内のすべてのファイルを効率的に比較する必要があることに対処します。ネストされたループがこれに十分である場合、それはクールです。これが慣習的に適切な方法であることを確認したかっただけです。

4

5 に答える 5

4

あなたのEDIT2の質問に対する私の答えは2つの部分に分かれています

重要なのは、ファイルの数が少ない場合は、ネストされたループのアプローチで問題ないはずです。パフォーマンスはO(N**2)で、最適解はO(N)です。ただし、Nが十分に小さい場合は、使用するアプローチに大きな違いはありません。N が大きくなる可能性があることが確実な場合にのみ、代替ソリューションを検討する必要があります。

2 番目の部分では、ファイル ハッシュを利用してO(N)重複を検出するためのソリューションを取得するアルゴリズムについて説明します。これは、以前の回答がほのめかしたものです。

  1. FileHashファイル ハッシュ値を表すクラスを作成します。これには、ファイル ハッシュのバイト単位の等価性を実装するメソッドを定義する必要がequals(Object)あります。hashCode()

  2. HashMap<FileHash, List<File>>マップ インスタンスを作成します。

  3. Fileあなたの入力のそれぞれについてArrayList：

    1. ファイルのハッシュを計算し、そのFileHashオブジェクトを作成します。
    2. FileHashマップで を検索します。
    3. エントリが見つかった場合は、マップから取得したリスト内の各ファイルと現在のファイルをバイト単位で比較します。リストに重複したファイルが見つかったら、BINGO! それ以外の場合は、現在のファイルをリストに追加します。
    4. エントリが見つからない場合は、"FileHash` をキーとして、現在のファイルを値リストの最初の要素として、新しいマップ エントリを作成します。

(上記のマップは実際にはマルチマップであり、利用可能なサード パーティの実装があることに注意してください。たとえば、Apache コモン コレクションや Google コレクションなどです。簡単にするために、上記の形式でアルゴリズムを提示しました。)

いくつかのパフォーマンスの問題:

  • 適切な暗号化ハッシュ関数を使用してファイル ハッシュを生成する場合、3.3 でリストに複数の要素を持つエントリを見つける可能性は非常に低く、ファイルのバイト単位の比較で一致しない可能性はほとんどありません。ファイルが等しいと言うのも無視できるほど小さいです。ただし、暗号ハッシュを計算するコストは、低品質のハッシュを計算するコストよりも高くなります。

  • 低品質のハッシュを使用する場合は、バイト単位の比較を行う前にファイル サイズを確認することで、より多くのファイルを比較する潜在的なコストを軽減できます。これを行うと、aとその長さの両方を保持するクラスであるHashMap<FileHash, List<FileTuple>>マップタイプを作成できます。FileTupleFile

  • 各ファイルの最初のブロック (たとえば) だけのハッシュを使用することで、ハッシュのコストを削減できる可能性があります。ただし、これにより、2 つのファイルのハッシュが同じでも異なる可能性が高くなります。たとえば、2 番目のブロックで。これが重要かどうかは、ファイルの性質によって異なります。(しかし、たとえば、ソース コード ファイルのコレクションの最初の 256 バイトをチェックサムしただけでは、膨大な数の衝突が発生する可能性があります...同一の著作権ヘッダーが存在するためです!)

于 2010-04-24T05:40:12.403 に答える
4

適切な最適化は、最初にファイルのすべてのハッシュを計算してから、リストに対して単一のループを実行することです。

これは基本的に、リストのファイルの各ペアをチェックする必要があるためですが、これは、チェックするファイルごとに多くのことを計算する代わりに、各ペアの O(1) 複雑さを意味します。

あなたは次のように行くことができます：

HashSet<YourFile> fileSet = new HashSet<YourFile>();
ArrayList<YourFile> files = new ArrayList<YourFile>();

class YourFile
{
  int hashcode = -1;

  public int hashCode()
  {
     // override it to provide an hashcode based on file contents
     // you can also cache it to avoid recalculating anything

     if (hashcode == -1)
       hashcode = calculateIt();

     return hashcode;
  }
}

// fill up files
files.add(...);

// do comparisons
for (YourFile f : files)
{
  if (fileSet.contains(f))
    // f and fileSet.get(f) are equal: this is a tricky utilization of the hashCode() method so be careful about it!
  else
  {
    fileSet.put(f);
    // since there's not a file with same hashcode you just add this one
  }
}

hashSet.containsこれを使用すると、すでに追加されているすべてのファイルがチェックされるため、実際には内部ループが削除されますが、O(1) の複雑さがあります。

doublep から述べたように、パフォーマンスについて注意する必要があります。単純にバイトをチェックすると、ハッシュの計算中に 2 つの異なるバイトが見つかるとすぐに停止し、ファイル全体をチェックする必要があるためです。これは、多くのファイルがある場合、またはファイルがかなり小さい場合にうまく機能します。最善の方法は、両方のアプローチをベンチマークして、顕著な違いがあるかどうかを確認することです。

于 2010-04-23T22:17:35.063 に答える
3

正確に何をしているのかにもよりますが、サイズの異なるファイルを比較しないことで、かなりのスピードアップが得られる場合があります。他の回答で示唆されているように、同じサイズのファイルの中で、（アルゴリズムに関係なく）同じハッシュを持つファイルのみを比較します。

編集：

ただし、ハッシュの計算は非生産的な場合があります。まず、ファイルを相互に比較するだけの場合は絶対に行わないでください。ハッシュを作成するにはファイルを完全に読み取る必要があり、比較には 1 回の読み取りで十分であるため、何も得られません。

第 2 に、一致することをめったに期待せず、実際に (早い段階で) ファイルがかなり異なる場合、比較するファイルの数に関係なく、ハッシュの計算は逆効果になる可能性があります。これは、このような状況で失敗した比較は早期に失敗する (つまり、ファイル全体を読み取らない) ためですが、ハッシュを構築するには完全な読み取りが必要になります。別の方法として、「部分的な」ハッシュ (たとえば、ファイルの最初の 10 kb のハッシュ) を作成することもできますが、その場合は、すべてのファイルの等しいチャンクを使用することを忘れないでください。

于 2010-04-23T22:19:29.127 に答える
2

そのようなすべてのものを他のすべてのものと比較すると、O(n²) になります。しかし、あなたが試すことができるトリックがあります。主なものは、比較を安くすることです。これは、各ファイルのハッシュ コードを生成し、それらを最初に比較することで実行できます。これにより、少なくとも比較の大部分を回避できます (十分に優れたアルゴリズムを使用すると、事実上すべての比較を回避できます)。どのファイルが等しいかに関する情報を保持する必要がない場合は、処理を高速化することもできます。各ファイルのハッシュコードを生成Setし、最後にセットのサイズがファイルのリストのサイズと同じかどうかを確認します。

于 2010-04-23T22:15:17.927 に答える
2

小さなクリーンアップの 1 つは、最初のサイズ テストを削除することです。サイズが 2 未満の場合、比較を行わずに単純に脱落します。Java コーディング規約をより適切に順守するには、ループ内で比較するi < tempList.size()のではなく、i <= tempList.size() - 1他のプログラマーがコードを理解しやすくするだけです。これらの変更はいずれも、パフォーマンスに影響を与えません。

for (int i = 0; i < tempList.size(); i++)
    for (int j = i + 1; j < tempList.size(); j++) {
        //*Gets sorted.
        System.out.println(checkBytes(tempList.get(i), tempList.get(j)));
    }
于 2010-04-23T22:25:54.737 に答える