8

我一直在用一堆不同的方法来搜索集合、集合集合等。做了很多愚蠢的小测试来验证我的理解。这是让我感到困惑的一个（源代码在下面）。

简而言之，我正在生成 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% 的收益……更多的困惑。

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.");
    }
}
4

3 回答 3

6

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

这确实搜索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 次方法调用和一次类型转换1。

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

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

您的结果也可能由于其他原因而失真。您的代码没有考虑 JVM 预热。阅读此问题以了解更多详细信息：如何在 Java 中编写正确的微基准测试？

于 2012-10-20T05:30:21.190 回答
3

这是区别：

当您使用 时contains，它使用对象的内部数组并进行如下搜索：

    for (int i = 0; i < size; i++)
        if (searchObject.equals(listObject[i]))
            return true;
    return false;

这里当它试图获取ith元素时，它直接从内部数组中获取第 i 个元素对象。

当您编写自己的代码时，您会这样写：

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

它相当于：

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

执行的步骤比contains.

于 2012-10-20T04:52:32.147 回答
1

所以我不完全确定你正在测试任何东西。Javac（编译器）足够聪明，可以意识到您的 for 循环和 if 语句中没有任何代码。在这种情况下，Java 将从其编译中删除该代码。您可能会获得时间回来的原因是因为您实际上是在计算打印字符串所需的时间。系统输出时间可能会因系统正在执行的操作而有很大差异。编写时序测试时，任何 I/O 都可能创建无效测试。

首先，我会从您的计时中删除字符串打印。

其次，ArrayList.contains 是线性的。它不像你正在做的那样使用特殊的 for 循环。您的循环有一些从集合中获取迭代器然后对其进行迭代的开销。这就是特殊的 for 循环在幕后工作的方式。

希望这可以帮助。

于 2012-10-20T04:59:13.257 回答