logo标签列表

java.util.Collections.contains() 如何比线性搜索更快？

javacollectionslinear-search
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.");
    }
}
你意识到你的第二个“搜索”甚至没有在搜索吗？它只是在迭代列表的元素... - Stephen C
是的，我其实几分钟前才意识到这一点，现在正在调试我的代码。对此感到抱歉。可能很快就要离开了，但稍后会更新这篇文章。 - The111
3个回答
6
你的比较代码有bug，这会导致结果扭曲。
代码中确实对目标值进行了搜索。
    if (ints.contains(target)) {
        // nothing
    }

但这并不行！
    for (Integer i : ints) {
        // nothing
    }

你实际上只是在迭代列表元素而没有测试它们。

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

  • The first version will be iterating the backing array using a simple for loop and an index. The second version is equivalent to the following:

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

    In other words, each time around the loop involves 2 method calls and a typecast1.

  • The first version will return true as soon as it gets a match. Because of the bug in your implementation, the second version will iterate the entire list every time. In fact, given the choice of N and high, this effect is the most likely the main cause of the difference in performance.

1 - 实际上，目前并不清楚JIT编译器会对所有这些内容做什么。理论上，它可以内联方法调用、推断类型转换是不必要的，甚至可以优化整个循环。另一方面，也有可能存在阻碍这些优化的因素。例如，ints被声明为List<Integer>，这可能会阻止内联...除非JIT能够推断实际类型始终相同。

还有一个可能导致结果失真的原因是您的代码没有考虑到JVM的预热。请阅读此问题以获取更多详细信息：如何在Java中编写正确的微基准测试？

谢谢Stephen。关于您提到的第二点，您是正确的，我忽略了在第二种情况下实际搜索的部分，但是您可能错过了我有意每次尝试迭代整个列表的部分。为了进一步达到这个目的，我正在寻找一个我知道不会被找到的值。我已经更新了我的帖子，包括第二个程序。在这个程序中，手动线性搜索（整个列表）比contains方法（也在搜索整个列表）快16％。您能解释一下这个新发现吗？再次感谢。 - The111
1
一个原因是你使用 == 而不是 .equals() 来比较值。这是不可靠的...它会在大整数时出错。而且你还没有解决 JVM 预热问题，这使得你的结果仍然存在疑问。 - Stephen C
我这里没有展示，但我做的一件事是将整个生成/搜索块包装在一个大的重复循环中，以强制每个块运行多次。我注意到，在前几次运行之后，报告的时间稳定下来，不再变化那么多。不确定是否算作JVM预热。但是，我刚刚将“==”更改为“.equals()”，确实使搜索速度变慢了很多，现在“contains”版本又开始表现出色了。 - The111
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方法多得多。

2
The111：大多数情况下，我会参考源代码本身 :) 你可以打开任何集合实现（例如ArrayList）的源代码并查看其中的方法。 - Yogendra Singh
有点尴尬地承认，我甚至从未考虑过这一点。谢谢。 - The111
1
它不适用于他的情况，因为他的for循环中没有进行任何验证。 - Daniel Pereira
1
对于你关于仅检查源代码的评论，我给予+1，但是对于答案，我给予-1。你提出的循环展开没有意义，增强型for循环会扩展为一个“迭代器”，在未知数据结构上使用“get”进行迭代是非常不明智的。 - Tim Bender
@AmitD：早些时候我在主题行中解释了线性搜索。我现在更新了答案，对代码中的for循环展开进行了更正。如果您认为现在已经好了，请重新考虑负面投票。 - Yogendra Singh
显示剩余2条评论
1

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

首先，我会从定时内部删除字符串打印。

其次，ArrayList.contains是线性的。它不像您所做的那样使用特殊的for循环。您的循环需要从集合中获取迭代器，然后对其进行迭代，这就是特殊的for循环背后的工作原理。

希望这可以帮助您。

谢谢。这是有趣的信息。但在这种情况下，我不认为循环被编译器删除了，因为在早期的测试中，我在其中执行了一个简单的操作，并且那些测试的时间也相似。此外，刚才，我注释掉了所有的打印行，它仍然似乎需要同样的时间运行程序（尽管这大约需要半秒钟，所以很难估计...但如果它真的什么都没做，它将是瞬间完成而不是大部分一秒钟）。 - The111
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接