看啥推荐读物

专栏名称: 眼若繁星丶

即使看清这个世界真实的样子，仍喜爱它

今天看啥

微信公众号rss订阅, 微信rss, 稳定的RSS源

微信公众号RSS订阅方法

B站投稿RSS订阅方法

知乎回答RSS订阅方法

知乎专栏 RSS订阅方法

雪球动态RSS订阅方法

微博RSS订阅方法

微博搜索关键词订阅方法

豆瓣日记 RSS订阅方法

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

眼若繁星丶 · 简书 · · 2021-03-16 10:37

public static native long nanoTime(); 来测试时间，主程序外围获取当前时间，然后作差得到运行时间。
程序中同时测试 ArrayList 和 LinkedList 两种实现方式的遍历效率，代表了数组和链表两种数据结构。
成员变量 public static final int MAGNITUDE = 10000; 用来控制数据的 数量级 。
初始化声明两种 List<String> ，并递增变量至数量级大小，过程中转化为 String 存储到集合当中，作为实验数据。
测试的运行程序逻辑是：将集合中的数据取出来，并赋值给另一个元素 str 。但是这里存在时间复杂度的区别， ArrayList 中的 get(int index) 在数组实现上时间复杂度是常数级i的 O(1) ，而 LinkedList 中的 get(int index) 在链表实现上时间复杂度是线性 O(n) ，但是测试的 ArrayList 和 LinkedList 的时间比较是 同数据结构 之间比较，符合控制变量法，所以不需要结果上的数值，而关注运行时间的 时间数量级 ，这样比较才有意义。

测试代码：

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。

如下是一种遍历集合的首选做法：

// Preferred idiom for iterating over a collection or array
for (Element e : c) {
    ... // Do Someting with e
}

如果需要访问迭代器，可能要调用它的 remove 方法，首选做法是利用传统的 for 循环替代 for-each 循环：

// 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

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 来展开讨论

// 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 异常。

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

下面是打印一对骰子出现的所有可能情况：

// 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

// 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 ，让这个问题完全消失，并且产生的代码也能很简洁。

// 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 接口的任何对象，只需要实现接口对应的方法即可。

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循环。

原文地址：访问原文地址
快照地址：访问文章快照

分享到微博