13

kjellkod 的文章中提到，如果我们传入作为参数ArrayList接收的方法，那么我们会损失性能，因为 ArrayList 实现了额外的RandomAccess接口。文章示例：List

// 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 和 check list instanceof RandomAccess，那么这两种情况都是如此。所以，我的第一个问题是为什么 Java VM 应该将其解释为第一种方法中的顺序列表？

我已经修改了文章中的测试以检查我的机器上的这种行为。在ideone上运行测试时，它显示的结果类似于 kjellkod 的结果。但是当我在本地运行它时，我得到了意想不到的结果，这与文章解释和我的理解相反。在我的例子中，ArrayList as List 迭代似乎比将其引用为 ArrayList 快 5-25%：

在此处输入图像描述

如何解释这种差异？它是否取决于架构或处理器内核的数量？我的工作机配置是 Windows 7 Professional x64、Intel Core i5-3470（4 核、4 线程）、16 GB RAM。

4

2 回答 2

3

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

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

它是否取决于架构或处理器内核的数量？

-client不，您会看到例如 32 位 Windows 和-server例如任何 64 位 JVM之间的区别。

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

注意：对于 List，contains() 是 O(n)，这就是为什么你的时间会增长 O(n^2)令人困惑，因为您很容易受到优化和未优化的微妙之处的影响。通过比较已经相当优化的代码，您将获得更有意义的结果。

于 2013-06-11T11:22:49.327 回答
1

尽管两种方法的代码相同，但理论上可能存在差异，因为在 JVM 级别调用接口方法与调用类方法不同。它们是 2 种不同的字节码操作：invokeinterface 和invokevirtual. 见http://bobah.net/d4d/source-code/misc/invokevirtual-vs-invokeinterface-performance-benchmark

于 2013-06-11T11:35:59.957 回答