哪个更有效,for-each循环还是迭代器？

Question

哪种是最有效的遍历集合的方式？

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a) {
  integer.toString();
}

要么

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   integer.toString();
}

请注意,这不是这个,这个,这个或这个的完全重复,尽管最后一个问题的答案之一很接近.这不是欺骗的原因是,大多数都是比较你get(i)在循环中调用的循环,而不是使用迭代器.

正如Meta上所建议的,我将发布我对这个问题的回答.

Answer 1

如果你只是漫游集合来读取所有值,那么使用迭代器或新的for循环语法之间没有区别,因为新语法只是在水下使用迭代器.

但是,如果你的意思是循环旧的"c风格"循环:

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

然后,新的for循环或迭代器可以更高效,具体取决于底层数据结构.其原因在于,对于某些数据结构,get(i)是O(n)操作,这使得循环成为O(n ²)操作.传统的链表是这种数据结构的一个例子.所有迭代器都有一个基本要求,它next()应该是一个O(1)操作,使得循环为O(n).

要通过新的for循环语法验证迭代器是否在水下使用,请比较以下两个Java代码段中生成的字节码.首先是for循环:

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a)
{
  integer.toString();
}
// Byte code
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 3
 GOTO L2
L3
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 2 
 ALOAD 2
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L2
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L3

第二,迭代器:

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();)
{
  Integer integer = (Integer) iterator.next();
  integer.toString();
}
// Bytecode:
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 2
 GOTO L7
L8
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 3
 ALOAD 3
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L7
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L8

如您所见,生成的字节代码实际上是相同的,因此使用任何一种形式都不会有性能损失.因此,对于大多数将成为for-each循环的人来说,你应该选择最具美学吸引力的循环形式,因为它具有较少的样板代码.

Answer 2

差异不在于性能,而在于能力.直接使用引用时,您可以使用迭代器类型(例如List.iterator()与List.listIterator()相比具有更强大的功能,尽管在大多数情况下它们返回相同的实现).您还可以在循环中引用Iterator.这允许您执行诸如从集合中删除项而不会收到ConcurrentModificationException之类的操作.

例如

还行吧:

Set<Object> set = new HashSet<Object>();
// add some items to the set

Iterator<Object> setIterator = set.iterator();
while(setIterator.hasNext()){
     Object o = setIterator.next();
     if(o meets some condition){
          setIterator.remove();
     }
}

这不是,因为它将引发并发修改异常:

Set<Object> set = new HashSet<Object>();
// add some items to the set

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}

Answer 3

为了扩展Paul自己的答案,他已经证明字节码在特定编译器上是相同的(可能是Sun的javac？)但是不能保证不同的编译器生成相同的字节码,对吧？要了解两者之间的实际差异,让我们直接查看源代码并检查Java语言规范,特别是14.14.2,"增强的语句":

增强for语句等同于for表单的基本语句:

for (I #i = Expression.iterator(); #i.hasNext(); ) {
    VariableModifiers(opt) Type Identifier = #i.next();    
    Statement 
}

换句话说,JLS要求两者是等价的.从理论上讲,这可能意味着字节码的边际差异,但实际上,增强的for循环需要:

• 调用.iterator()方法
• 使用 .hasNext()
• 通过提供局部变量 .next()

换句话说,就所有实际目的而言,字节码将是相同的或几乎相同的.很难设想任何可能导致两者之间存在显着差异的编译器实现.

Answer 4

底层foreach是创建iterator，调用 hasNext() 并调用 next() 来获取值；仅当您使用实现 RandomomAccess 的东西时，才会出现性能问题。

for (Iterator<CustomObj> iter = customList.iterator(); iter.hasNext()){
   CustomObj custObj = iter.next();
   ....
}

基于迭代器的循环的性能问题是因为它是：

1. 即使列表为空也分配对象 ( Iterator<CustomObj> iter = customList.iterator(););
2. iter.hasNext()在循环的每次迭代期间，都会有一个 invokeInterface 虚拟调用（遍历所有类，然后在跳转之前进行方法表查找）。
3. 迭代器的实现必须执行至少 2 个字段查找才能使hasNext()调用计算值：#1 获取当前计数，#2 获取总计数
4. 在主体循环内部，还有另一个 invokeInterface 虚拟调用iter.next（因此：在跳转之前遍历所有类并进行方法表查找），并且还必须进行字段查找：#1 获取索引，#2 获取对数组来对其进行偏移（在每次迭代中）。

一个潜在的优化是切换到index iteration缓存大小查找：

for(int x = 0, size = customList.size(); x < size; x++){
  CustomObj custObj = customList.get(x);
  ...
}

这里我们有：

1. customList.size()在初始创建 for 循环时调用一个 invokeInterface 虚拟方法来获取大小
2. customList.get(x)在 for 循环体中调用 get 方法，这是对数组的字段查找，然后可以对数组进行偏移量

我们减少了大量的方法调用和字段查找。你不想用LinkedList不是RandomAccess集合 obj 的东西来做这件事，否则它customList.get(x)会变成LinkedList每次迭代都必须遍历的东西。

当您知道这是任何RandomAccess基于列表的集合时，这是完美的。