我一直在尝试各种不同的搜索集合、集合内集合等方法,做了很多愚蠢的小测试来验证我的理解。以下是一个让我困惑的例子(源代码在下面)。
简而言之,我正在生成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.");
}
}