1

ここでは、理解を容易にするために、要件の簡略化したバージョンを提示しようとしています。

私はこのクラスを持っています

public class MyClass {
   private byte[] data1;
   private byte[] data2;
   private long hash1;  // Hash value for data1
   private long hash2;  // Hash value for data2
   // getter and setters }

ここで、このクラスの 2 つの List インスタンスを検索し、2 つのインスタンス間で一致する hash1 の数と、すべての一致に対して対応する hash2 の一致数を見つける必要があります。2 番目のリストには、約 1,000 万個の MyClass オブジェクトが含まれます。

今、最初のリストを反復処理し、2 番目のリストを検索することを計画しています。特定の方法でソートまたは順序付けして検索を最適化する方法はありますか? 両方のリストをソートする必要がありますか、それとも 1 つだけをソートする必要がありますか?

4

4 に答える 4

0

2番目にのみ並べ替え、最初に繰り返し、2番目にバイナリ検索を実行し、O（nlogn）を並べ替え、n個のアイテムO（nlogn）をバイナリ検索します。

または、2番目にハッシュセットを使用し、最初に反復して2番目に検索します。O（n）

于 2012-10-12T18:21:52.813 に答える
0

最善の解決策は、これよりも速い解決策はないことを繰り返すことです。ハッシュマップを作成して、マップが同じキーを追加しないことを利用できますが、独自の作成オーバーロードがあります

于 2012-10-12T18:23:46.483 に答える
0

すべての要素をチェックする必要がある場合は、最初のリストを反復処理し、AmitD が言ったように 2 番目のリストの Hashmap を作成する必要があると思います。

クラスで正しくオーバーライドする必要がequalsありhashcodeますMyClass。最後に、できるだけ基本的な型を使用することをお勧めします。たとえば、最初のリストの場合、リストの代わりに単純な配列を使用する方が適切です。

また、最初に、2 つのリストのどちらが短いか (サイズに違いがある場合) を選択し、そのリストを反復処理することもできます。

于 2012-10-12T18:31:57.993 に答える
0

リストの1つにハッシュマップを作成する必要があると思います（たとえばlist1）-

Map<Long, MyClass> map = new HashMap<Long, MyClass>(list1.size());//specify the capacity
//populate map like - put(myClass.getHash1(), myClass) : for each element in the list

次に、2番目のリストを反復処理します（両方をソートしても意味がありません）-

int hash1MatchCount = 0;
int hash2MatchCount = 0;
for(MyClass myClass : list2) {
    MyClass mc = map.get(myClass.getHash1());
    if(mc != null) {
        hash1MatchCount++;
        if(myClass.getHash2() == mc.getHash2) {
            hash2MatchCount++;
        }
    }
}

hash1注:重複に関して問題がないと仮定します。

于 2012-10-12T18:43:51.820 に答える