为什么在 List 上迭代比在 List 上索引更快？

ADT 列表的 Java 文档上面写着:

List 接口为对列表元素的位置(索引)访问提供了四种方法。列表(如 Java 数组)是从零开始的。请注意，对于某些实现(例如 LinkedList 类) ，这些操作可能按照与索引值成比例的时间执行。因此，如果调用者不知道实现，那么迭代列表中的元素通常优于通过它进行索引。

这到底是什么意思? 我不明白得出的结论。

15702 次浏览
小开

这里暗示了答案:

请注意，对于某些实现(例如 LinkedList 类) ，这些操作可能按照与索引值成比例的时间执行

链表没有固有的索引; 调用 .get(x)将需要列表实现找到第一个条目并调用 .next() x-1次(对于 O (n)或线性时间访问) ，其中数组支持的列表只能在 O (1)或常量时间内索引到 backingarray[x]。

如果您查看 JavaDoc for LinkedList，您将看到注释

所有操作的执行情况都符合双链表的预期。将索引编入列表的操作将从开始或结束遍历列表，以较接近指定索引的位置为准。

而 用于 ArrayList的 JavaDoc有相应的

List 接口的可调整数组实现。实现所有可选的列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口之外，该类还提供了一些方法来操作内部用于存储列表的数组的大小。(这个类大致相当于 Vector，只是它是非同步的。)

size、 isEmpty、 get、 set、 iterator和 listIterator操作以恒定的时间运行。添加操作以分摊的常量时间运行，也就是说，添加 n 个元素需要 O (n)时间。所有其他操作都在线性时间内运行(粗略地说)。与 LinkedList实现相比，该常数因子较低。

题为“大澳 Java集合框架摘要”的相关问题有一个指向这个资源的答案，“ Java 集合 JDK6”，您可能会发现它很有帮助。

小开

要找到 LinkedList的第 i 个元素，实现需要遍历所有元素直到第 i 个元素。

那么

for(int i = 0; i < list.length ; i++ ) {
Object something = list.get(i); //Slow for LinkedList
}
小开
最佳答案

在链表中，每个元素都有一个指向下一个元素的指针:

head -> item1 -> item2 -> item3 -> etc.

要访问 item3，您可以清楚地看到，您需要从头部通过每个节点，直到到达 item3，因为您不能直接跳转。

因此，如果我想打印每个元素的值，如果我这样写:

for(int i = 0; i < 4; i++) {
System.out.println(list.get(i));
}

事情是这样的:

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

这是 效率极低，因为每次您正在索引它重新启动从列表的开始，并通过每个项目。这意味着仅仅为了遍历列表，您的复杂性实际上就是 O(N^2)！

If instead I did this:

for(String s: list) {
System.out.println(s);
}

then what happens is this:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

全部在一次遍历中，即 O(N)。

现在，转到 List的另一个实现，即 ArrayList，它由一个简单的数组支持。在这种情况下，上述两种遍历都是等价的，因为数组是连续的，所以它允许随机跳转到任意位置。

小开

尽管公认的答案肯定是正确的，但请允许我指出一个小缺陷:

Now, going to the other implementation of List which is ArrayList, that one is backed by a simple array. In that case both of the above traversals are equivalent, since an array is contiguous so it allows 随机跳到任意位置。

这不完全正确，事实是

使用数组列表，手写计数循环的速度要快3倍

来源: 为性能而设计，谷歌的 Android 文档

注意，手写循环引用了索引迭代。我怀疑这是因为迭代器与增强的 for 循环一起使用。它在一个由连续数组支持的结构中产生较小的性能损失。我还怀疑 Vector 类可能也是这样。

My rule is, use the enhanced for loop whenever possible, and if you really care about performance, use indexed iteration only for either ArrayLists or Vectors. In most cases, you can even ignore this- the compiler might be optimizing this in the background.

我只是想指出，在 Android 的开发环境中，数组列表的遍历都是 不一定等价。只是需要好好想想。

小开

对带有查找偏移量的列表(如 i)进行迭代类似于 画家 Shlemiel 的算法。

Shlemiel 找到一份街头画家的工作，画虚线 第一天，他拿了一罐油漆 开到路上，完成了300码的路程 “太好了!”他的老板说，“你干活真快!”然后付给他一戈比。

The next day Shlemiel only gets 150 yards done. "Well, that's not 差不多和昨天一样好，但你还是很快150码 是值得尊敬的,”并付给他一戈比。

第二天，施莱米尔在30码的路面上作画。“只有30码!” 他的老板说，“这是不可接受的! 在第一天你做了10次 那么多工作! 怎么回事?”

“我情不自禁,”施莱米尔说，“每天我都走得越来越远 远离油漆罐!”

来源 。

这个小故事可能会让我们更容易理解内部发生了什么，以及为什么效率这么低。


提交答案