为什么迭代List会比通过它索引更快?

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

List接口提供了四种位置(索引)访问列表元素的方法。 列表(如Java数组)基于零。 请注意,这些操作的执行时间可能与某些实现(例如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)来遍历列表!

如果我做了这个:

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

那么会发生什么呢?

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

所有在一个单一的遍历,这是O(N)

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

答案暗示在这里:

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

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

如果您查看LinkedList的JavaDoc ,您将看到注释

所有的操作都可以预期为双向链表。 索引到列表中的操作将从开始或结束遍历列表,以哪个更接近指定的索引为准。

而JavaDoc for ArrayList有相应的

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

sizeisEmptygetsetiteratorlistIterator操作在一定的时间内运行。 add操作以分摊的恒定时间运行,即添加n个元素需要O(n)个时间。 所有其他的操作都在线性时间内运行(粗略地说)。 与LinkedList实现相比,常数因子较低。

标题为“Java集合框架的Big-O总结”的相关问题有一个答案指向这个资源, “Java Collections JDK6” ,你可能会发现它有帮助。

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

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

这并不完全正确。 事实是,那

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

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

请注意,手写循环是指索引迭代。 我怀疑它是因为用于增强for循环的迭代器。 它在一个连续arrays支持的结构中产生一个小的惩罚performance。 我也怀疑Vector类可能是这样的。

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

我只想指出,在Android的发展背景下,ArrayLists的遍历不一定是等价的 。 只是思考的食物。

迭代查找偏移量的列表,比如i ,类似于画家algorithm的Shlemiel

史莱米尔得到了一个街头画家的工作,在路中间画了点线。 第一天,他把一jar油漆涂在路上,完成了300码的路。 “这很好!” 他的老板说:“你是个快工人!” 并支付给他一个科比。

第二天什莱米尔只完成了150码。 “呃,那还不如昨天,但你还是一个快速的工人,150码是可敬的,”他付出了一个科比。

第二天什莱米尔画了30码的道路。 “只有三十!” 喊老板。 “这是不可接受的!第一天你做了十次这么多的工作,发生了什么事?

“我忍不住了,”史莱米尔说。 “每天我都离油漆jar越来越远!”

来源 。

这个小故事可能会让人更容易理解内部发生的事情,以及为什么这么低效。

为了查找LinkedList的第i个元素,实现遍历所有元素直到第i个元素。

所以

 for(int i = 0; i < list.length ; i++ ) { Object something = list.get(i); //Slow for LinkedList }