Java 配列内の重複する整数を効率的に検出するにはどうすればよいですか?

Java 配列内の重複の認識: 旅

Java の領域では、整数の配列 (int [])。ただし、これらの重複を識別しようとすると、よくある落とし穴が発生します。問題とその解決策を見てみましょう。

次のコードを考えてみましょう:

int[] zipcodelist = // ...

duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
    for(k = 0; k < zipcodeList.length; k++){
        if (zipcodeList[k] == zipcodeList[j]){
            duplicates = true;
        }
    }
}

このコードは、指定された zipcodelist に重複する要素が含まれているかどうかを判断することを目的としています。ただし、重複が存在しないシナリオは考慮されていません。その結果、重複は常に true になります。

欠陥の特定

欠陥を理解するために、ロジックを分析してみましょう。コードには、リスト内の各要素を他のすべての要素と比較するネストされたループがあります。いずれかの 2 つの要素が一致する場合、重複が true に設定され、重複の存在が示されます。ただし、重複がない場合、ループは必然的に要素をそれ自体と比較します。すべての要素について、この自己比較により重複が true に設定されます。

修正されたアプローチ

重複を正しく検出するには、コードで自己比較を除外する必要があります。これを実現する 1 つの方法は、ネストされたループ構造を次のように変更することです:

duplicates=false;
for (j=0;j<zipcodeList.length;j++)
  for (k=j+1;k<zipcodeList.length;k++)
    if (k!=j &amp;&amp; zipcodeList[k] == zipcodeList[j])
      duplicates=true;

この変更では、次のインデックス (k=j 1) で内部ループを開始することで自己比較をスキップします。

代替ソリューションの検討

修正されたアプローチは効果的に機能しますが、より高速な代替手段も利用できます。次のハッシュマップベースのソリューションを検討してください。

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

このソリューションは、ハッシュ セットを利用して重複要素を効率的にチェックします。各要素はハッシュ セットに追加され、要素がすでに存在する場合、それは重複を意味します。

もう 1 つの効率的なアプローチには、ビットマップの使用が含まれます。

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodelist)
     if (!(bitmap[item] ^= true)) return true;
   }
   return false;
}

このソリューションでは、ビットマップが作成されます。配列内の最大値 (MAXZIP) と等しいサイズの配列。次に、ビット操作を使用して、入力配列内の各要素に対応するビットを設定します。ビットがすでに設定されている場合は、重複を示します。

ベンチマーク結果

これらのアプローチのパフォーマンスを評価するために、さまざまなリスト サイズでベンチマークを実行しました。結果は、特に大きなリストの場合、効率の点でビットマップアプローチが明らかに勝者であることを示しました:

Array Size	Bitmap (ms)	Hash Set (ms)	Nested Loops (ms)
10	0.0	0.0	0.0
1,000	0.0	0.0	0.0
10,000	0.0	0.0	100.0
100,000	0.0	0.16	9,923.3

結論

落とし穴を理解すれば、Java 配列内の重複を特定するのは簡単な作業になります。自己比較を回避したり、ハッシュ セットやビットマップなどの代替アプローチを活用したりすることで、効率的かつ正確な重複検出を実現し、Java アプリケーションのパフォーマンスを最適化できます。

以上がJava 配列内の重複する整数を効率的に検出するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。