性能：Java中迭代列表

Question

像这样在Java中遍历列表是否会更慢：

for (int i=0;i<list.size();i++) {
    .. list.get(i)
}

相反：

for (Object o: list) {
    ... o
}

- syker

Answer 1

我认为你只是出于纯好奇心而提问，并不会引用 Knuth（可能有人会这么做）。

我认为，一旦你的代码被编译，就没有什么区别了。它在之前确实有所区别（例如示例2更易读更简洁），因此请使用第二个，不必担心其他问题。

仅供参考。

编辑

请注意，片段1中的代码每次循环运行时都会计算list.size()，这可能比第2个示例还要慢。

另一个编辑

我需要再次确认一下，Joshua Bloch 建议使用for each循环（请参阅Effective Java的第46项）。我相信这将结束所有讨论。感谢 Josh！ ：）

- Pablo Fernandez

---

+1 很好的观点，即使第一个是在 LinkedList 上完成的，编译也可能会给出相同的性能。 - Rhangaun

@Skeptic 即使现在不行，它将来肯定会表现得一样好甚至更好。 - Pablo Fernandez

编译可能不会给出相同的性能，除非编译器能够确定列表的内容没有改变。它能做到吗？我不知道！第二个版本会更快，因为它会假设列表内容不会改变，我相信。问题中的第二个版本更像是我回答中的第一个示例。据我所知，大小被假定为恒定的。 - Jonathon Faust

过早的优化并不是万恶之源，而复制粘贴才是！ - OscarRyz

提前优化的代码，直接复制粘贴怎么样？那是多么邪恶的行为啊！！ - Newtopian

通过放松疗法，您可以预防过早优化。 - Rob Kielty

Answer 2

对于普通列表，性能不应该有任何明显的差异。

对于链表，迭代器将更快，特别是对于大型列表。

- SLaks

---

“正常列表”是什么？我猜你实际上是指“对于ArrayList”。 - Stephen C

Answer 3

创建了一个微基准测试（microbenchmark），并惊讶地发现for-each循环比索引循环运行速度快2倍至3倍。我唯一的解释是for-each版本可能不需要由ArrayList.get（int index）进行的范围检查。

对于非常小的列表（10个元素），结果大致相同。对于100个元素，for-each快1.5倍，对于10000-100000个元素，速度快2倍至3倍。

这些测试是在随机数据集上运行的，并且在最后验证了校验和，因此JIT chearing很不可能发生。

- Andrey Chaschev

---

这里进行了更多的比较：https://dzone.com/articles/iteration-over-java-collections-with-high-performa。此外，他们使用“标准化”的JMH库进行微基准测试。 - Lubo

Answer 4

不是的。当列表也实现了RandomAccess（就像ArrayList这样做了，而LinkedList没有这样做）时，它应该会更快。

然而，你应该始终使用后者：

 for( Object o: list ) {
 }

仅在您有充分证据表明使用它会导致性能问题时（例如，您对应用程序进行了剖析，并且发现代码的这一部分需要改进），才切换到前者。

如果不这样做，您可能无法在以后的重构中切换实现（因为您将被绑定到for( int i = 0 ; i < list.size(); i++ )惯用语）。

- OscarRyz

Answer 5

根据While loop, For loop and Iterator Performance Test – Java中的基准测试和JavaRanch问题“使用ArrayList.iterator()比在for循环中循环ArrayList更快吗?”，迭代器实际上稍微慢一些。但是，除非我对整个应用程序进行了基准测试并发现该循环是我的瓶颈，否则我仍然会偏向于可读性。

- Bill the Lizard

---

我认为for-each循环不会成为任何应用程序的瓶颈。 - Pablo Fernandez

@Pablo：很难想象。循环的内容很容易成为瓶颈，但我怀疑这个习语会有任何区别。 - Bill the Lizard

Answer 6

可能会有所不同。

如果一个列表实现也实现了java.util.RandomAccess（例如ArrayList），那么使用它的get()方法比使用迭代器要快得多。

如果它没有实现java.util.RandomAccess（例如LinkedList），那么使用迭代器会更快。

然而，这只有在您使用包含数千个（可能分散的）对象或经常遍历的列表时才会有影响（就像对表示数值向量的List对象执行大量数学运算一样）。

- luis.espinal

---

实现RandomAccess接口并不能保证get()方法的速度快。你可以编写一个实现了RandomAccess接口的链表，但它可能会非常慢。 - kibibu

@Kibiku - 是的，你可以编写一个违反其接口合同协议的RandomAccess实现。对于任何记录的接口合同，没有任何东西可以在编译时阻止这样做。那将是一个糟糕的编写或恶意编写的实现，这超出了RandomAccess应提供的范围。作为一名工程师，你必须在某个时候划定界限，按照契约设计进行编程，并进行有效推断。如果有人违反了这样一个简单的接口标记的合同，我会质疑他/她的编码能力。 - luis.espinal

此外，我可以创建一个实现java.util.Map接口的类，该类以只读模式运行，但会静默地忽略对put()、remove()和putAll()的调用，而不是抛出UnsupportedOperationException()（这是只读Map实例应实现的预期行为）。除非你极端情况下需要这样做，否则有能力这样做是不理解接口所暗示的契约的标志。接口不仅仅是一个标记或一组方法，它们是开发人员应遵循的语义契约。 - luis.espinal

Answer 7

每次迭代检查大小确实会增加i个操作，但对性能影响不大。

我的意思是，这两种方法之间只有微小的差别。

int lsize = myList.size();
for(int i=0; i < lsize; i++)
{
   Object o = myList.get(i);
}

对比：

for(int i=0; i < myList.size(); i++)
{
   Object o = myList.get(i);
}

但实际上这并不重要。使用你问题中的第二个选项可以提高可读性，还有其他原因。

- Jonathon Faust

---

我想知道为什么这里常常这样做，而不是使用“for(int i=0,siz=myList.size(); i<siz; i++)”？ - Lawrence Dol

可能是因为这是一种过早的微优化，大多数人认为它并没有提高可读性。编译器应该会自动优化掉大小检查，即使在大多数情况下它没有这样做，也不会成为瓶颈。 - Brian

Answer 8

我自己没有深入研究所有列表实现中get()的代码，所以我写的可能是一些虚假信息（FUD）。我学到的是，在for循环中使用get(i)会导致每次循环都对整个列表进行迭代。而使用迭代器（就像增强型for循环一样）只会将迭代器移动到下一个列表元素，而不会再次对整个列表进行迭代。

我的结论是，使用迭代器或增强型for循环应该更高效，因为使用get()会导致复杂度为O(n^2)，而不是O(n)。

- jham

---

正如之前的回答所述，这取决于列表的类型。你所写的只适用于不实现RandomAccess的列表（例如LinkedList，而不是ArrayList）。 - Philipp Wendler

Answer 9

我们认识到随机访问和顺序访问之间的区别常常模糊不清。例如，一些List实现在它们变得非常大时提供渐进线性的访问时间，但在实践中提供恒定的访问时间。这样的List实现通常应该实现此接口。作为一个经验法则，如果对于类的典型实例，以下循环：

    for (int i=0, n=list.size(); i < n; i++)
        list.get(i);

比以下循环运行得更快，则List实现应该实现此接口：

    for (Iterator i=list.iterator(); i.hasNext(); )
        i.next();

- Gaurav