遍历集合的最有效方法是什么?

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

or

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

请注意,这不是这个,这个,这个或这个的精确副本,尽管最后一个问题的答案之一很接近。这不是一个骗局的原因是,其中大多数是比较循环,在循环中调用get(i),而不是使用迭代器。

根据Meta上的建议,我会把我对这个问题的答案贴出来。


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

然而,如果你说的循环是旧的“c风格”循环:

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

然后,新的for循环或迭代器可以更高效,这取决于底层数据结构。这样做的原因是,对于某些数据结构,get(i)是一个O(n)操作,这使得循环是O(n2)操作。传统链表就是这种数据结构的一个例子。所有迭代器都有一个基本要求,即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循环,因为它具有较少的样板代码。


区别不在于性能,而在于能力。当直接使用引用时,你有更多的权力显式使用迭代器类型(例如List.iterator() vs. List.listIterator(),尽管在大多数情况下它们返回相同的实现)。您还可以在循环中引用迭代器。这允许你在不获得ConcurrentModificationException的情况下从集合中删除项目。

e.g.

这是可以的:

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);
     }
}

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

增强的for语句相当于如下形式的基本for语句:

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

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

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

因此,换句话说,出于所有实际目的,字节码将是相同的,或几乎相同。很难想象任何编译器实现会在两者之间产生任何显著差异。


在使用集合时,应该避免使用传统的for循环。 我要给出的简单原因是for循环的复杂度是O(sqr(n))阶,而Iterator甚至是增强的for循环的复杂度只有O(n)阶。 所以它会带来性能上的差异。 只需要拿出一个包含1000个项目的列表,并用两种方式打印出来。并打印执行时的时间差。你可以看到其中的区别。


Iterator是Java Collections框架中的一个接口,它提供了遍历或遍历集合的方法。

当您的动机只是遍历一个集合以读取其中的元素时,迭代器和for循环的作用是相似的。

for-each只是遍历集合的一种方法。

例如:

List<String> messages= new ArrayList<>();

//using for-each loop
for(String msg: messages){
    System.out.println(msg);
}

//using iterator 
Iterator<String> it = messages.iterator();
while(it.hasNext()){
    String msg = it.next();
    System.out.println(msg);
}

for-each循环只能用于实现迭代器接口的对象。

现在回到for循环和iterator的例子。

当您尝试修改一个集合时,区别就出现了。在这种情况下,迭代器更有效,因为它的快速失败属性。ie。在遍历下一个元素之前,它检查底层集合结构中的任何修改。如果发现任何修改,它将抛出ConcurrentModificationException。

(注意:迭代器的这个功能只适用于java中的集合类。util包。它不适用于并发收集,因为它们本质上是故障安全的)


Foreach在底层使用迭代器。它真的只是语法糖。

考虑下面的程序:

import java.util.List;
import java.util.ArrayList;

public class Whatever {
    private final List<Integer> list = new ArrayList<>();
    public void main() {
        for(Integer i : list) {
        }
    }
}

我们用javac编译, 并读取main()的分解字节码,使用javap -c Whatever:

public void main();
  Code:
     0: aload_0
     1: getfield      #4                  // Field list:Ljava/util/List;
     4: invokeinterface #5,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
     9: astore_1
    10: aload_1
    11: invokeinterface #6,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z
    16: ifeq          32
    19: aload_1
    20: invokeinterface #7,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
    25: checkcast     #8                  // class java/lang/Integer
    28: astore_2
    29: goto          10
    32: return

我们可以看到foreach编译成一个程序:

使用List.iterator()创建迭代器 If Iterator.hasNext():调用Iterator.next()并继续循环


至于“为什么这个无用的循环没有从编译的代码中得到优化?”我们可以看到它没有对列表项做任何事情”:好吧,你可以对你的iterable进行编码,使.iterator()产生副作用,或者使. hasnext()产生副作用或有意义的结果。

您可以很容易地想象,表示来自数据库的可滚动查询的迭代器可能会在. hasnext()上做一些戏剧性的事情(比如联系数据库,或者因为到达结果集的末尾而关闭游标)。

因此,即使我们可以证明在循环体中没有发生任何事情,但要证明在迭代时没有发生任何有意义的/结果性的事情是更昂贵的(棘手的?)编译器必须在程序中保留这个空循环体。

我们所能希望得到的最好结果是一个编译器警告。有趣的是,javac -Xlint:all Whatever.java没有警告我们这个空循环体。不过IntelliJ IDEA可以。诚然,我已经将IntelliJ配置为使用Eclipse Compiler,但这可能不是原因所在。


foreach底层正在创建迭代器,调用hasNext()并调用next()来获取值;只有在使用实现了RandomomAccess的东西时,性能才会出现问题。

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

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

allocating an object even if the list is empty (Iterator<CustomObj> iter = customList.iterator();); iter.hasNext() during every iteration of the loop there is an invokeInterface virtual call (go through all the classes, then do method table lookup before the jump). the implementation of the iterator has to do at least 2 fields lookup in order to make hasNext() call figure the value: #1 get current count and #2 get total count inside the body loop, there is another invokeInterface virtual call iter.next(so: go through all the classes and do method table lookup before the jump) and as well has to do fields lookup: #1 get the index and #2 get the reference to the array to do the offset into it (in every iteration).

一个潜在的优化是切换到缓存大小查找的索引迭代:

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

这里我们有:

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

我们减少了大量的方法调用和字段查找。这不能用LinkedList或者不是RandomAccess集合obj的东西做,否则customlist。get(x)会变成每次迭代都要遍历LinkedList的东西。

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