java:List.contains()与手动搜索的性能差异

Question

我试图证明之间的差异,List.contains()并手动搜索执行时间,结果很棒.这是代码,

public static void main(String argv[]) {
    List<String> list = new ArrayList<String>();
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("b");

    long startTime = System.nanoTime();

    list.contains("b");

    long endTime = System.nanoTime();
    long duration = endTime - startTime;

    System.out.println("First run: "+duration);

    startTime = System.nanoTime();
    for(String s: list){
        if(s.equals("b"))
            break;
    }
    endTime = System.nanoTime();

    duration = endTime - startTime;
    System.out.println("Second run: "+duration);

}

输出:

• 首次运行:7500

• 第二轮:158685

  1. contains()函数如何产生如此大的差异？

  2. 它使用哪种搜索算法？

  3. 如果列表包含搜索到的元素,它会在第一个元素处终止搜索吗？

Answer 1

首先,相信来自单一测试的结果是不明智的.有太多的可变因素,要考虑的缓存含义以及其他类似的事情 - 您应该考虑编写一种在某种程度上使用随机化而不是试验的测试,并执行数百万次不同的检查,而不仅仅是一次.

那就是说,我希望你的结果会保持不变; ArrayList实现contains()使用其自己的indexOf()方法,它直接循环它存储底层阵列上.你可以在这里看到这个

另一方面,foreach循环需要实例化a Iterator,通过其所有方法访问数组,并且通常比ArrayList自己的直接实现做更多的工作.但是,再次,你应该更彻底地对它进行基准测试!