我一直在胡思乱想各种搜索集合、集合的集合等的不同方法。做了很多愚蠢的小测试来验证我的理解。这是让我感到困惑的一个(源代码在下面)。

简而言之，我正在生成 N 个随机整数并将它们添加到列表中。该列表未排序。然后，我使用 Collections.contains() 在列表中查找值。我有意寻找一个我知道不会存在的值，因为我想确保整个列表空间都被探测到。我为这次搜索计时。

然后我手动进行另一个线性搜索，遍历列表的每个元素并检查它是否与我的目标匹配。我也为这次搜索计时。

平均而言，第二次搜索比第一次搜索花费的时间长 33%。按照我的逻辑，第一次搜索也必须是线性的，因为列表是未排序的。我能想到的唯一可能性(我立即放弃)是 Java 正在制作我的列表的排序副本只是为了搜索，但是(1)我没有授权使用内存空间和(2)我认为如此大的 N 会节省更多的时间。

因此，如果两个搜索都是线性的，那么它们应该花费相同的时间。 Collections 类以某种方式优化了此搜索，但我不知道如何优化。那么...我错过了什么？

import java.util.*;

public class ListSearch {

    public static void main(String[] args) {

        int N = 10000000; // number of ints to add to the list
        int high = 100; // upper limit for random int generation

        List<Integer> ints;
        int target = -1; // target will not be found, forces search of entire list space

        long start;
        long end;

        ints = new ArrayList<Integer>();
        start = System.currentTimeMillis();
        System.out.print("Generating new list... ");
        for (int i = 0; i < N; i++) {
            ints.add(((int) (Math.random() * high)) + 1);
        }
        end = System.currentTimeMillis();
        System.out.println("took "  + (end-start) + "ms.");
        start = System.currentTimeMillis();
        System.out.print("Searching list for target (method 1)... ");
        if (ints.contains(target)) {
            // nothing
        }
        end = System.currentTimeMillis();
        System.out.println(" Took "  + (end-start) + "ms.");

        System.out.println();

        ints = new ArrayList<Integer>();
        start = System.currentTimeMillis();
        System.out.print("Generating new list... ");
        for (int i = 0; i < N; i++) {
            ints.add(((int) (Math.random() * high)) + 1);
        }
        end = System.currentTimeMillis();
        System.out.println("took "  + (end-start) + "ms.");
        start = System.currentTimeMillis();
        System.out.print("Searching list for target (method 2)... ");
        for (Integer i : ints) {
            // nothing
        }
        end = System.currentTimeMillis();
        System.out.println(" Took "  + (end-start) + "ms.");
    }
}

编辑:下面是这段代码的新版本。有趣的是，现在我的手动线性循环比 contains 方法执行 快 16%(注意:两者都旨在有意搜索整个列表空间，所以我知道它们迭代次数相等)。我无法解释这 16% 的 yield ……更多的是困惑。

import java.util.*;

public class ListSearch {

    public static void main(String[] args) {

        int N = 10000000; // number of ints to add to the list
        int high = 100; // upper limit for random int generation

        List<Integer> ints;
        int target = -1; // target will not be found, forces search of entire list space

        long start;
        long end;

        ints = new ArrayList<Integer>();
        start = System.currentTimeMillis();
        System.out.print("Generating new list... ");
        for (int i = 0; i < N; i++) {
            ints.add(((int) (Math.random() * high)) + 1);
        }
        end = System.currentTimeMillis();
        System.out.println("took "  + (end-start) + "ms.");
        start = System.currentTimeMillis();
        System.out.print("Searching list for target (method 1)... ");
        if (ints.contains(target)) {
            System.out.println("hit");
        }
        end = System.currentTimeMillis();
        System.out.println(" Took "  + (end-start) + "ms.");

        System.out.println();

        ints = new ArrayList<Integer>();
        start = System.currentTimeMillis();
        System.out.print("Generating new list... ");
        for (int i = 0; i < N; i++) {
            ints.add(((int) (Math.random() * high)) + 1);
        }
        end = System.currentTimeMillis();
        System.out.println("took "  + (end-start) + "ms.");
        start = System.currentTimeMillis();
        System.out.print("Searching list for target (method 2)... ");
        for (int i = 0; i < N; i++) {
            if (ints.get(i) == target) {
                System.out.println("hit");
            }
        }
        end = System.currentTimeMillis();
        System.out.println(" Took "  + (end-start) + "ms.");
    }
}

最佳答案

您的比较代码有问题，这会扭曲您的结果。

这会搜索 target

    if (ints.contains(target)) {
        // nothing
    }

但这不是!

    for (Integer i : ints) {
        // nothing
    }

您实际上只是在不测试列表元素的情况下对其进行迭代。

话虽如此，由于以下一个或多个原因，第二个版本比第一个版本慢:

• 第一个版本将使用简单的 for 迭代支持数组循环和索引。第二个版本等同于:

  Iterator<Integer> it = ints.iterator();
  while (it.hasNext()) {
      Integer i = (Integer) it.next();
  }
  

  换句话说，每次循环涉及 2 个方法调用和一个类型转换¹。

• 第一个版本会返回true一旦匹配。由于您的实现中存在错误，第二个版本每次都会迭代整个 列表。事实上，考虑到 N 的选择和 high ，这种影响很可能是性能差异的主要原因。

^{1 - 实际上，JIT 编译器将如何处理所有这些并不完全清楚。它可以理论上内联方法调用，推断 typcaset 是不必要的，甚至可以优化整个循环。另一方面，有一些因素可能会阻碍这些优化。例如，ints声明为 List<Integer>这可能会抑制内联……除非 JIT 能够推断出实际类型始终相同。}

您的结果也可能由于其他原因而失真。您的代码没有考虑 JVM 预热。阅读此问题以获取更多详细信息:How do I write a correct micro-benchmark in Java?

关于java - java.util.Collections.contains() 如何比线性搜索执行得更快？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12985342/