如果将ArrayList引用为List,为什么ArrayList性能会有所不同？

Question

在kjellkod的文章中提到过,如果我们传入作为参数ArrayList接收的方法List,那么我们会失去性能,因为ArrayList实现了额外的RandomAccess接口.文章示例:

// SLOWER: as shown in http://ideone.com/1wnF1
private static void linearInsertion(Integer[] intArray, List<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

// FASTER: as shown in http://ideone.com/JOJ05
private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

参考:

鼓励使用通用列表算法来检查给定列表是否是此接口的实例,然后应用将在应用于顺序访问列表时提供较差性能的算法,并在必要时更改其行为以保证可接受的性能.

但是,如果我们真的在上面的方法中传递ArrayList并检查list instanceof RandomAccess,那么在两种情况下都是如此.那么,我的第一个问题是为什么Java VM应该将其解释为第一种方法中的顺序列表？

我已经修改了文章中的测试,以检查我的机器上的这种行为.当对ideone运行测试时,它会显示类似于kjellkod的结果.但是当我在本地运行时,我得到了意想不到的结果,这与文章解释以及我的理解相反.在我的情况下,作为List迭代的ArrayList似乎比作为ArrayList引用它快5-25%:

如何解释这种差异？它取决于架构还是处理器核心数量？我的工作机配置是Windows 7 Professional x64,Intel Core i5-3470(4核,4个线程),16 GB RAM.

Answer 1

所以，我的第一个问题是为什么 Java VM 应该将其解释为第一个方法中的顺序列表？

JVM 没有顺序或随机访问列表的概念。（除了标记接口）实现的开发人员认识到 ArrayList 在 O(1) 时间内而不是 O(n) 时间内执行随机访问查找。

它取决于架构或处理器核心的数量吗？

-client不，您会看到32 位 Windows 和-server任何 64 位 JVM之间的差异。

我怀疑你第二次运行了列表测试。这可能会更快，因为代码在 JIT 和 CPU 缓存中都得到了更多的警告。我建议您至少执行每个测试三次，首先运行最长的测试并忽略第一次运行。

注意：对于列表来说 contains() 是 O(n)，这就是为什么你的时间会增长 O(n^2) 显然，如果你想忽略重复项并且查看真正低效代码的行为，你不会使用列表令人困惑的是，您很容易受到优化和未优化的微妙之处的影响。通过比较已经相当优化的代码，您将获得更有意义的结果。