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

Question

阅读ADT列表的Java文档,它说:

List接口提供了四种对列表元素进行位置(索引)访问的方法.列表(如Java数组)基于零.请注意,对于某些实现(例如,LinkedList类),这些操作可以与索引值成比例地执行.因此,如果调用者不知道实现,则迭代列表中的元素通常优选通过它进行索引.

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

Answer 1

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

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)只是遍历列表!

如果相反我做了这个:

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

然后会发生什么:

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

所有这一切都在一次遍历中O(N).

现在,去的其他实现List这ArrayList,是一个由简单的阵列支持.在这种情况下,上述两个遍历都是等效的,因为一个数组是连续的,所以它允许随机跳转到任意位置.

Answer 2

答案在这里暗示:

请注意,这些操作可能会与某些实现的索引值成比例地执行(例如,LinkedList类)

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

如果您查看JavaDocLinkedList,您将看到评论

对于双向链表,所有操作都可以预期.索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准.

而JavaDoc for则ArrayList具有相应的功能

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

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

标题为"Java-Collections Framework的Big-O摘要"的相关问题有一个答案,指向这个资源,"Java Collections JDK6",您可能会发现它很有帮助.

Answer 3

虽然接受的答案肯定是正确的,但我可以指出一个小缺陷.引用都铎王朝:

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

这不完全正确.事实是,那

使用ArrayList,手写计数循环的速度提高约3倍

来源:设计性能,谷歌的Android文档

请注意,手写循环指的是索引迭代.我怀疑它是因为迭代器与增强的for循环一起使用.它在由连续数组支持的结构中产生较小的惩罚性能.我也怀疑Vector类可能是这样.

我的规则是,尽可能使用增强型for循环,如果您真的关心性能,请仅对ArrayLists或Vectors使用索引迭代.在大多数情况下,您甚至可以忽略这一点 - 编译器可能会在后台对此进行优化.

我只是想指出,在Android的开发环境中,ArrayLists的遍历并不一定相同.只是值得深思.

Answer 4

迭代具有查找偏移量的列表,例如i,类似于画家的算法Shlemiel.

Shlemiel得到了一个街头画家的工作,画在路中间的虚线.第一天,他把一罐油漆涂在路上,完成了300码的路程."那太好了!" 他的老板说,"你是个快工!" 并付给他一个科比.

第二天Shlemiel只完成150码."嗯,这不像昨天那么好,但你仍然是一个快速的工作者.150码是值得尊敬的,"并给他一个科比.

第二天,Shlemiel画了30码的路."只有30个!" 喊他的老板."这是不可接受的!第一天你做了十倍的工作!发生了什么事？"

"我无法帮助它,"Shlemiel说."每天我都能远离油漆罐!"

来源.

这个小故事可以让您更容易理解内部发生的事情以及为什么效率如此低下.