[java] 为什么迭代List会比编制索引更快?


Answers

答案暗示在这里:

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

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

如果您查看LinkedListJavaDoc ,您会看到评论

所有这些操作的执行情况可能与双向链表相符。 索引到列表中的操作将从开始或结束遍历列表,以哪个更接近指定的索引为准。

JavaDoc for ArrayList具有相应的

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

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

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

Question

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

List接口提供了四种位置(索引)访问列表元素的方法。 列表(如Java数组)基于零。 请注意,对于某些实现(例如,LinkedList类),这些操作的执行时间可能与索引值成比例。 因此,如果调用者不知道实现,遍历列表中的元素通常更适合通过索引进行索引。

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




迭代查找偏移量的列表(如i )类似于画家算法的Shlemiel

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

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

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

“我无法帮助它,”史莱米尔说。 “每天我都离油漆罐越来越远!”

来源

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




Related