Java配列に値が含まれているかどうかを確認する

投稿日: 2019-10-18 2022-10-27
タグ: Java, Java Array, Java Search

1. 概要

この記事では、指定された値の配列を検索するさまざまな方法を見ていきます。

また、 JMH （Javaマイクロベンチマークハーネス）を使用してこれらのパフォーマンスを比較し、どちらの方法が最適かを判断します。

2. 設定

この例では、テストごとにランダムに生成されたStringsを含む配列を使用します。

String[] seedArray(int length) {
    String[] strings = new String[length];
    Random value = new Random();
    for (int i = 0; i < length; i++) {
        strings[i] = String.valueOf(value.nextInt());
    }
    return strings;
}

各ベンチマークで配列を再利用するために、配列とカウントを保持する内部クラスを宣言して、JMHのスコープを宣言できるようにします。

@State(Scope.Benchmark)
public static class SearchData {
    static int count = 1000;
    static String[] strings = seedArray(1000);
}

3. 基本検索

配列を検索するために一般的に使用される3つの方法は、リスト、セット、または一致するものが見つかるまで各メンバーを調べるループを使用する方法です。

各アルゴリズムを実装する3つの方法から始めましょう。

boolean searchList(String[] strings, String searchString) {
    return Arrays.asList(SearchData.strings)
      .contains(searchString);
}

boolean searchSet(String[] strings, String searchString) {
    Set<String> stringSet = new HashSet<>(Arrays.asList(SearchData.strings));
    
    return stringSet.contains(searchString);
}

boolean searchLoop(String[] strings, String searchString) {
    for (String string : SearchData.strings) {
        if (string.equals(searchString))
        return true;
    }
    
    return false;
}

これらのクラスアノテーションを使用して、JMHにマイクロ秒単位の平均時間を出力し、5回のウォームアップ反復を実行して、テストの信頼性を確保するように指示します。

@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 5)
@OutputTimeUnit(TimeUnit.MICROSECONDS)

そして、各テストをループで実行します。

@Benchmark
public void searchArrayLoop() {
    for (int i = 0; i < SearchData.count; i++) {
        searchLoop(SearchData.strings, "T");
    }
}

@Benchmark
public void searchArrayAllocNewList() {
    for (int i = 0; i < SearchData.count; i++) {
        searchList(SearchData.strings, "T");
    }
}

@Benchmark
public void searchArrayAllocNewSet() {
    for (int i = 0; i < SearchData.count; i++) {
        searchSet(SearchData.strings, "S");
    }
}

メソッドごとに1000回の検索を実行すると、結果は次のようになります。

SearchArrayTest.searchArrayAllocNewList  avgt   20    937.851 ±  14.226  us/op
SearchArrayTest.searchArrayAllocNewSet   avgt   20  14309.122 ± 193.844  us/op
SearchArrayTest.searchArrayLoop          avgt   20    758.060 ±   9.433  us/op

ループ検索は他の検索よりも効率的です。しかし、これは少なくとも部分的にはコレクションの使用方法によるものです。

searchList（）を呼び出すたびに新しい List インスタンスを作成し、呼び出しごとに新しいListと新しいHashSetを作成します。 searchSet（）に。これらのオブジェクトを作成すると、配列をループする場合とは異なり、追加のコストが発生します。

4. より効率的な検索

ListとSetの単一インスタンスを作成し、それらを検索ごとに再利用するとどうなりますか？

やるだけやってみよう：

public void searchArrayReuseList() {
    List asList = Arrays.asList(SearchData.strings);
    for (int i = 0; i < SearchData.count; i++) {
        asList.contains("T");
    }
}

public void searchArrayReuseSet() {
    Set asSet = new HashSet<>(Arrays.asList(SearchData.strings));
    for (int i = 0; i < SearchData.count; i++) {
        asSet.contains("T");
    }
}

上記と同じJMHアノテーションを使用してこれらのメソッドを実行し、比較のために単純なループの結果を含めます。

非常に異なる結果が表示されます。

SearchArrayTest.searchArrayLoop          avgt   20    758.060 ±   9.433  us/op
SearchArrayTest.searchArrayReuseList     avgt   20    837.265 ±  11.283  us/op
SearchArrayTest.searchArrayReuseSet      avgt   20     14.030 ±   0.197  us/op

List の検索は以前よりわずかに高速ですが、 Set はループに必要な時間の1％未満に低下します。

各検索から新しいコレクションを作成するために必要な時間を削除したので、これらの結果は理にかなっています。

ハッシュテーブルを検索すると、 HashSet の基礎となる構造の時間計算量は0（1）ですが、 ArrayList の基礎となる配列は0（n）です。

5. 二分探索

配列を検索する別の方法は、二分探索です。非常に効率的ですが、バイナリ検索では、配列を事前に並べ替える必要があります。

配列を並べ替えて、バイナリ検索を試してみましょう。

@Benchmark
public void searchArrayBinarySearch() {
    Arrays.sort(SearchData.strings);
    for (int i = 0; i < SearchData.count; i++) {
        Arrays.binarySearch(SearchData.strings, "T");
    }
}

SearchArrayTest.searchArrayBinarySearch  avgt   20     26.527 ±   0.376  us/op

バイナリ検索は非常に高速ですが、 HashSet：よりも効率は劣りますが、バイナリ検索の最悪の場合のパフォーマンスは0（log n）であり、配列検索とハッシュテーブルのパフォーマンスの間にあります。

6. 結論

配列を検索するいくつかの方法を見てきました。

結果に基づくと、 HashSet は、値のリストを検索するのに最適です。ただし、事前に作成してセットに保存する必要があります。

いつものように、例の完全なソースコードは、GitHubでから入手できます。

getdocs

13036