配列に特定の値が含まれているかどうかを効率的に判断する方法

前言
無秩序配列に特定の値が含まれているかどうかをどのように判断しますか?
これはJAVAで非常に実用的な操作であり、Stack Overflow質疑応答サイトでも同様に人気のある問題である.
この判断を完成するには、いくつかの異なる方法で実現することができ、それぞれの実現方式に対応する時間は複雑に読むことが大きく異なる.
次に,4つの異なる実装方式と,この4つの方式に対応する時間オーバーヘッドを示す.
配列に値が含まれているかどうかを確認するには、4つの方法があります.
1、使用List:

    public static boolean useList(String[] arr, String targetValue) {
        return Arrays.asList(arr).contains(targetValue);
    }

2、Setを使う:

    public static boolean useSet(String[] arr, String targetValue) {
        Set set = new HashSet(Arrays.asList(arr));
        return set.contains(targetValue);
    }

3、簡単な循環文を使う:

    public static boolean useLoop(String[] arr, String targetValue) {
        for (String s : arr) {
            if (s.equals(targetValue))
                return true;
        }
        return false;
    }

4、Arraysを使う.binarySearch()メソッド:
注意:次のコードは間違っています.以下に列挙されているのは完全性を考慮したためです(4つの判断方法)、binarySearch()二分検索は秩序配列にのみ使用できます.
次のプログラムを実行すると、異常な結果が得られる可能性があります.

    public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
        int a = Arrays.binarySearch(arr, targetValue);
        if (a > 0)
            return true;
        else
            return false;
    }

4つの実装方式に対応する時間オーバーヘッド
以下のコードは以上の4つの実現方式の大まかな時間消費を計算することができ、基本戦略は異なる大きさの配列(5,1 k,10 k)を使ってテストを行うことであり、正確ではないかもしれないが、この方法は簡単である.
配列サイズは5です.

public static void main(String[] args) {
        String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB" };
        // use list
        long startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            useList(arr, "A");
        }
        long endTime = System.nanoTime();
        long duration = endTime - startTime;
        System.out.println("useList: " + duration / 1000000);
        // use set
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            useSet(arr, "A");
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("useSet: " + duration / 1000000);
        // use loop
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            useLoop(arr, "A");
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("useLoop: " + duration / 1000000);
        // use Arrays.binarySearch()
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            useArraysBinarySearch(arr, "A");
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("useArrayBinary: " + duration / 1000000);
    }

実行結果:
useList: 13useSet: 72useLoop: 5useArraysBinarySearch: 9
配列サイズは1000です.

        String[] arr = new String[1000];
        Random s = new Random();
        for (int i = 0; i < 1000; i++) {
            arr[i] = String.valueOf(s.nextInt());
        }

実行結果:
useList: 112useSet: 2055useLoop: 99useArrayBinary: 12
配列サイズは10000です.

        String[] arr = new String[10000];
        Random s = new Random();
        for (int i = 0; i < 10000; i++) {
            arr[i] = String.valueOf(s.nextInt());
        }

実行結果:
useList: 1590useSet: 23819useLoop: 1526useArrayBinary: 12
結論
テスト結果から、任意のセットを使用するよりも簡単なループ文を使用する方が効率的であることがわかります.多くの開発者は第1の方法(List)を使用することを選んだが、この方法は実際には比較的非効率である.集合が提供するAPIを使用する前に、配列を集合に置く必要があり、これは特にSet集合に対して一定の時間を消費する必要がある.(注:実はArrayList集合の性能は普通のループ文とあまり差がありません.ArrayListに対して、集合に変換するときは、内部の配列インデックスを変えただけなので、判断を遍歴するときは、普通のループ文と似ています).
Arraysを使用する場合.binarySearch()法は,配列が秩序化されることを前提としており,このテストdemoでは配列が無秩序であることが明らかであるため,使用すべきではない.
実際、配列や集合に値が含まれているかどうかを効率的にチェックする必要がある場合は、秩序リストや秩序ツリーが時間の複雑さをO(log(n))に下げるか、ハッシュ集合を使用して時間の複雑さをO(1)にすることができます.
 
翻訳リンク:http://www.programcreek.com/2014/04/check-if-array-contains-a-value-java/