检查Java数组是否包含一个值

2020-03-21 1058 words 3 minutes

Contents

1. 概述

在本文中，我们将研究在数组中搜索指定值的不同方法。

我们还将使用JMH （Java Microbenchmark Harness）比较这些方法的执行情况，以确定哪种方法效果最好。

2. 设置

对于我们的示例，我们将使用一个包含每个测试随机生成的String的数组：

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、Set或使用循环检查每个成员直到找到匹配项。

让我们从实现每种算法的三种方法开始：

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 以微秒为单位输出平均时间并运行五次预热迭代以确保我们的测试可靠：

@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)。

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：二进制搜索的最坏情况性能为$$ O(\log{n}) $$，其性能介于数组搜索和哈希表之间。