Java For-loop& For-each & Iterator 效率分析

本文最后更新于:2021年3月27日 晚上

  • public static native long nanoTime(); 来测试时间,主程序外围获取当前时间,然后作差得到运行时间。

  • 程序中同时测试 ArrayListLinkedList两种实现方式的遍历效率,代表了数组和链表两种数据结构。

  • 成员变量 public static final int MAGNITUDE = 10000;用来控制数据的 数量级

  • 初始化声明两种 List<String>,并递增变量至数量级大小,过程中转化为 String 存储到集合当中,作为实验数据。

  • 测试的运行程序逻辑是:将集合中的数据取出来,并赋值给另一个元素 str。但是这里存在时间复杂度的区别, ArrayList中的 get(int index)在数组实现上 时间复杂度是常数级i的 O(1),而 LinkedList中的 get(int index)在链表实现上 时间复杂度是线性 O(n),但是测试的 ArrayListLinkedList的时间比较是同数据结构之间比较,符合控制变量法,所以不需要结果上的 数值,而关注 运行时间的 时间数量级,这样比较才有意义。

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;

public class Solution {

public static final int MAGNITUDE = 10000; // 数量级

public static long testForloop(List<String> list) {
long start, end;
String str = null;
start = System.nanoTime();
for (int i = 0; i < MAGNITUDE; i++) {
str = list.get(i);
}
end = System.nanoTime();
return end - start;
}

public static long testForeach(List<String> list) {
long start, end;
String str = null;
start = System.nanoTime();
for (String s : list) {
str = s;
}
end = System.nanoTime();
return end - start;
}

public static long testIterator(List<String> list) {
long start, end;
String str = null;
start = System.nanoTime();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
str = iterator.next();
}
end = System.nanoTime();
return end - start;
}

public static void main(String[] args) {
/* initialize */
List<String> arrayList = new ArrayList<String>();
List<String> linkedList = new LinkedList<String>();
for (int i = 0; i < MAGNITUDE; i++) {
arrayList.add(String.valueOf(i));
linkedList.add(String.valueOf(i));
}
System.out.println("========Test for ArrayList========");
System.out.println("For loop: " + testForloop(arrayList));
System.out.println("Foreach: " + testForeach(arrayList));
System.out.println("Iterator: " + testIterator(arrayList));

System.out.println("========Test for LinkedList========");
System.out.println("For loop: " + testForloop(linkedList));
System.out.println("Foreach: " + testForeach(linkedList));
System.out.println("Iterator: " + testIterator(linkedList));
}
}

实验结果

  • 如上文分析:同数据结构 比较原则。

数量级:1,000

========Test for ArrayList========
For loop: 99000
Foreach: 321700
Iterator: 194500
========Test for LinkedList========
For loop: 1215800
Foreach: 341500
Iterator: 94900

数量级:10,000

========Test for ArrayList========
For loop: 933200
Foreach: 942500
Iterator: 585800
========Test for LinkedList========
For loop: 129958500
Foreach: 1433000
Iterator: 967600

数量级:100,000

========Test for ArrayList========
For loop: 3730800
Foreach: 6669800
Iterator: 5215100
========Test for LinkedList========
For loop: 18907275800
Foreach: 7468100
Iterator: 5632400

  • ArrayList:在小数量级上,For-loop效率会高一点,For < Iterator < For-each,这里得出的结论根据时间消耗得出,无法仔细比较效率高低,数量级小时,For效率高一点,整体来说,三者速度级别差不多。
  • LinkedList:链表中很明显 For loop 效率就低很多了。For-each和Iterator相差不大。数量大(一般超过 100,000级别)效果更明显。Iterator < For-each < <<For-loop。Iterator和For-each效率在链表中差不多,For差一些就是了。

分析

  • For-each 和 Iterator 基本都在一个数量级上,这可能与 For-each 就是基于 Iterator 实现的,至于 For-each 会稍微慢一点,可能是 For-each 隐式转换 Iterator 耗费多余时间,

  • ArrayList基于数组,index都是确定的,在查改反面效率会高一点,自然带着下表的 For 效率会高很多。LinkedList基于链表,查改开销会比较大,但它是双向循环带头节点的链表,增删会比数组快,这两种数据结构的比较差别就在这,实际中还是要看在哪方面的应用来确定。

工程中三种循环的使用建议。

  • 《Effective Java》第三版第58条中建议,一般采用 Foreach 进行循环,因为它在 简洁性预防Bug上优于For-loop 和 Iterator(确切说是 Iterator 配合 while 使用)

简洁性就不需要多阐述了,光看代码量和可读性,就知道 For-each 的简洁性特点。

For-each 优势于 while-loop


预防Bug
  • 说到预防Bug,这里牵涉到 第57条 中的 将局部变量的作用域最小化
为什么要“将局部变量的作用域最小化”

书中提到,原因类似于 第15条的本质,使类和成员的可访问性最小化。将局部变量作用域最小化,可以增强代码的可读性和可维护性,并降低出错的可能性。

循环中提供了特殊的机会来将变量的作用域最小化。无论是传统的for循环,还是for-each形式的 for 循环,都允许声明循环变量,它们的作用域被限定在正好需要的范围之内。如果在循环终止之后不再需要循环变量的内容,for-loop就优先于 while loop。

  • 如下是一种遍历集合的首选做法:
1
2
3
4
// Preferred idiom for iterating over a collection or array
for (Element e : c) {
... // Do Someting with e
}
  • 如果需要访问迭代器,可能要调用它的 remove 方法,首选做法是利用传统的 for 循环替代 for-each 循环:
1
2
3
4
5
// Idiom for iterating when you need the iterator
for (Iterator<Element> i = c.iterator(); i.hasNext(); ) {
Element e = i.next();
... // Do someting with e and i
}

为什么有些时候不能用 for-each ,它的实现还是基于 iterator 的 hasNext() + next(),但是有时候需要在循环过程中对集合进行操作,此时就必须使用 iterator 对象进行操作了,因为使用 iterator 循环时,集合的操作权就交给了 iterator,虽然可以用集合对象进行操作,如 romove()但这样会破坏 iterator 初始化的结果,导致最终程序运行的结果与预期偏差很大,这里引用我的另一篇文章,有 Java 在 iterator 中 remove() 的 bug详解。

https://www.jianshu.com/p/642d6fd39013

  • 至于为什么 for loop 要比 while loop 更好,参考一下代码片段,连续的两个 whIle loop,以及出现的一个 bug
1
2
3
4
5
6
7
8
9
Iterator<Element> i = c.iterator();
while (i.hasNext()) {
doSometing(i.next());
}
...
Iterator<Element> i2 = c.iterator();
while (i.hasNext()) { // This is bug!
doSometing(i2.next());
}

在第二个 while loop 中,使用了 迭代器 i 的判断,实际操作的是 i2 遍历的对象,bug 就在这里,实际工程中,因为 迭代器 i的产生是在 while loop 外面的,作用于包含了整段程序,包括 while loop 使用结束之后,加上中间有其他的逻辑代码,难免会不小心使用到上面残余的 迭代器i,这就造成很严重的 bug,而不会轻易被发现,IDE也不会报错。 所以要利用好 for loop 声明迭代器,控制它的作用范围。

上面的bug程序最终的结果是下面的 while loop 不会执行,因为在上面的 while loop 执行结束之后,迭代器 i就会遍历到尽头,这样继续判断 i.hasNext()只会返回 false

For-each 优势于 For-loop


  • 以下面一个 两层集合嵌套迭代出现的 bug 来展开讨论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Can you spot the bug?
enum Suit {CLUB, DIAMOND, HEART, SPADE}
enum Rank {
ACE, DEUCE, THREE, FOUR, FIVE, SIX, SEVEN,
EIGHT, NINE, TEN, JACK, QUEEN, KING
}
...
static Collection<Suit> suits = Arrays.asList(Suit.values());
static Collection<Rank> ranks = Arrays.asList(Rank.values());

List<Card> deck = new ArrayList<>();
for (Iterator<Suit> i = suits.iterator(); i.hasNext(); )
for (Iterator<Rank> j = ranks.iterator(); j.hasNext(); )
deck.add(new Card(i.next(), j.next()));

这里的bug比较难找,可能很多大师也会犯这个错误。bug在于,在迭代器上对外部的集合 suits 调用太多 next 方法,它应该从外部的循环进行调用,以便每种花色都调用一次,但它却是从内部循环调用,因此每次牌调用一次。在用完所有花色之后,循环就会抛出 NoSuchElementException异常。

如果碰巧外部集合的大小是内部集合大小的几倍(可能因为它们是相同的集合),循环就会正常终止,但是实际完成情况跟预期是有出入的。

  • 下面是打印一对骰子出现的所有可能情况:
1
2
3
4
5
6
7
// Same bug, different symptom!
enum Face {ONE, TWO, THREE, FOUR, FIVE, SIX}
Collection<Face> faces = EnumSet.allOf(Face.class);

for (Iterator<Face> i = faces.iterator(); i.hasNext(); )
for (Iterator<Face> j = faces.iterator(); i.hasNext(); )
System.out.println(i.next() + " " + j.next());

ONE ONE
TWO TWO
THREE THREE
FOUR FOUR
FIVE FIVE
SIX SIX

同样的错误,也是重复调用 next。这种程序不会抛出异常,所以往往找bug会特别难受。

  • 下面开始修正此 bug
1
2
3
4
5
6
// Fixed, but ugly - so we need for-each
for (Iterator<Suit> i = suits.iterator(); i.hasNext(); ) {
Suit suit = i.next();
for (Iterator<Rank> j = ranks.iterator(); j.hasNext(); )
deck.add(new Card(suit, j.next()));
}
  • 至此引出 for-each ,让这个问题完全消失,并且产生的代码也能很简洁。
1
2
3
4
// Preferred idiom for neat iteration on collections and arrays
for (Suit suit : suits)
for (Rank rank : ranks)
deck.add(new Card(suit, rank));

For-each 无法使用的地方


  • 解构过滤:如果需要遍历集合,并删除指定元素,需要使用显式的迭代器,以便使用它的 remove 方法。使用 Java 8 中添加的 Collection 的 removeIf,常常可以避免显式遍历。
  • 转换:如果需要遍历列表或者数组,并取代它的部分或者全部元素值,就需要列表迭代器或者数组索引,以便设置元素的值。
  • 平行迭代:如果需要并行地遍历多个集合,就需要显式地控制迭代器或者索引变量,以便所有迭代器或者索引变量都可以同步前进(就如上述有问题的牌和骰子的示例中无意间所示范的那样)

For-each 拓展使用

  • for-each 不止能遍历集合和数组,还能遍历实现 Iterable接口的任何对象,只需要实现接口对应的方法即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Iterable<T> {
/**
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
Iterator<T> iterator();

default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
}

总结

总而言之,与传统的for循环相比,for-each循环在简洁性、灵活性以及出错预防性方面都占有绝对优势,并且没有性能惩罚的问题。因此,当可以选择的时候,for-each循环应该优先于for循环。