1概要

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

また、

JMH

(Java Microbenchmark Harness)を使用してこれらがどのように機能するかを比較して、どちらの方法が最適かを判断します。


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つの方法は、

    List、

    a

    Set、

    、または一致を見つけるまで各メンバーを調べる** ループです。

各アルゴリズムを実装する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

インスタンスを作成し、

searchSet()

を呼び出すたびに新しい

List

と新しい

HashSet

を作成します。

これらのオブジェクトを作成すると、追加のコストが発生し、配列をループするのにはコストがかかりません。


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)です。

配列を検索するための別の方法は

binary search

です。非常に効率的ですが、バイナリ検索では、配列を事前にソートする必要があります。

配列を並べ替えて二分検索を試してみましょう。

@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よりも効率的ではありませんが非常に高速です。


6. 結論

配列を検索する方法はいくつかあります。

結果に基づいて、

HashSet

は値の一覧を検索するのに最適です。ただし、それらを事前に作成して

Set.

に格納する必要があります。

いつものように、例の完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-arrays[GitHubで利用可能]です。