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

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上的建议,我会把我对这个问题的答案贴出来。


当前回答

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的列表集合时,这是完美的。

其他回答

如果您只是在集合中漫游以读取所有值,那么使用迭代器或新的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循环,因为它具有较少的样板代码。

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,但这可能不是原因所在。

为了扩展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()使局部变量可用

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

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的列表集合时,这是完美的。

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