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

Why would iterating over a List be faster than indexing through it?

提问by nomel7

Reading the Java documentation for the ADT Listit says:

阅读ADT 列表的Java 文档，它说：

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.

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

What exactly does this mean? I don't understand the conclusion which is drawn.

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

回答by Tudor

In a linked list, each element has a pointer to the next element:

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

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

To access item3, you can see clearly that you need to walk from the head through every node until you reach item3, since you cannot jump directly.

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

Thus, if I wanted to print the value of each element, if I write this:

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

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

what happens is this:

发生的事情是这样的：

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

This is horribly inefficientbecause every time you are indexing it restarts from the beginning of the list and goes through every item. This means that your complexity is effectively O(N^2)just to traverse the list!

这是非常低效的，因为每次索引时它都会从列表的开头重新启动并遍历每个项目。这意味着您的复杂性实际上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.

all in a single traversal, which is O(N).

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

Now, going to the other implementation of Listwhich 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 random jumps to arbitrary positions.

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

回答by andersoj

The answer is implied here:

答案隐含在这里：

Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example)

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

A linked list doesn't have an inherent index; calling .get(x)will require the list implementation to find the first entry and call .next()x-1 times (for a O(n) or linear time access), where an array-backed list can just index into backingarray[x]in O(1) or constant time.

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

If you look at the JavaDoc for LinkedList, you'll see the comment

如果您查看JavaDoc forLinkedList，您将看到评论

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

对于双向链表，所有操作都按预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。

whereas JavaDoc for ArrayListhas the corresponding

而JavaDoc forArrayList有相应的

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

The size, isEmpty, get, set, iterator, and listIteratoroperations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedListimplementation.

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

的size，isEmpty，get，set，iterator，和listIterator操作在固定时间运行。add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实施的常数系数相比，常数系数较低。

A related question titled "Big-O Summary for Java Collections Framework"has an answer pointing to this resource, "Java Collections JDK6"which you might find helpful.

一个名为“Java 集合框架的 Big-O 摘要”的相关问题有一个指向此资源的答案，“Java 集合 JDK6”可能对您有帮助。

回答by Dhruv Gairola

While the accepted answer is most certainly correct, might I point out a minor flaw. Quoting Tudor :

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

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 random jumps to arbitrary positions.

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

This is not completely true. The truth is, that

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

With an ArrayList, a hand-written counted loop is about 3x faster

使用 ArrayList，手写计数循环大约快 3 倍

source: Designing for Performance, Google's Android doc

来源：性能设计，Google 的 Android 文档

Note that the handwritten loop refers to the indexed iteration. I suspect its because of the iterator which is used with enhanced for loops. It produces a minor performance in penalty in a structure which is backed by a contiguous array. I also suspect this might be true for the Vector class.

请注意，手写循环指的是索引迭代。我怀疑这是因为与增强的 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.

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

I merely want to point out that in the context of development in Android, both the traversals of ArrayLists are not necessarily equivalent. Just food for thought.

我只是想指出，在Android的开发环境中，ArrayLists的遍历并不一定是等价的。只是深思熟虑。

回答by alex

Iterating over a list with an offset for the lookup, such as i, is analogous to Shlemiel the painter's algorithm.

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

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!"

Shlemiel 找到了一份街头画家的工作，在路中间画虚线。第一天，他把一罐油漆带到路上，完成了 300 码的路。“那倒是不错！” 他的老板说，“你是个快手！” 并付给他一个戈比。

第二天 Shlemiel 只跑了 150 码。“嗯，这几乎没有昨天那么好，但你仍然是一个快速的工人。150 码是可敬的，”并付给他一个戈比。

第二天，Shlemiel 粉刷了 30 码的道路。“才三十！” 他的老板喊道。“这不可接受！第一天你做了十倍的工作！这是怎么回事？”

“我无能为力，”施莱米尔说。“每天我离油漆罐越来越远！”

Source.

来源。

This little story may make it easier to understand what is going on internally and why it is so inefficient.

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

回答by esej

To find the i-th element of a LinkedListthe implementation goes through all elements up to the i-th.

为了找到 a 的第 i 个元素，LinkedList实现会遍历所有元素，直到第 i 个元素。

So

所以

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