blocks|key|3099348|text|答案隐含在这里：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3099349|3099350|请注意，对于某些实现(例如，LinkedList类)，这些操作的执行时间可能与索引值成比例|blockquote|3099351|3099352|3099353|链表没有固有的索引；调用.get(x)需要列表实现找到第一个条目并调用.next()+x-1次(对于O(n)或线性时间访问)，其中基于数组的列表只能在O(1)或恒定时间内索引到backingarray[x]。|offset|length|style|CODE|3099354|如果您查看JavaDoc+for+LinkedList，您将看到以下注释|3099355|3099356|所有操作的执行与双向链表的预期一致。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的那个为准。|3099357|3099358|3099359|而JavaDoc+for+ArrayList具有对应的|3099360|3099361|+Resizable-+List接口的数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现list接口之外，该类还提供了一些方法来操作内部用于存储列表的数组的大小。(这个类大体上等同于Vector，只是它是不同步的。)|3099362|3099363|size、isEmpty、get、set、iterator和listIterator操作在固定时间内运行。add操作在分期固定时间内运行，即添加n个元素需要O(n)时间。所有其他操作都在线性时间内运行(粗略地说)。与LinkedList实现相比，常量因子较低。|3099364|3099365|一个related+question+titled+"Big-O+Summary+for+Java+Collections+Framework"有一个指向这个资源"Java+Collections+JDK6"的答案，你可能会发现它对你有帮助。|3099366|entityMap|0|LINK|mutability|MUTABLE|url|http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html|1|http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html|2|https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations|3|http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf^0|0|0|0|0|0|C|7|Z|7|2G|F|0|H|A|5|M|0|0|0|0|0|0|D|9|1|L|1|0|0|0|0|0|4|5|7|D|3|H|3|L|8|U|C|30|A|0|0|2|1Y|2|29|N|3|0^^$0|@$1|2|3|4|5|6|7|1J|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|1L|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|1M|8|@]|9|@]|A|$]]|$1|G|3|-4|5|6|7|1N|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|1O|8|@$J|1P|K|1Q|L|M]|$J|1R|K|1S|L|M]|$J|1T|K|1U|L|M]]|9|@]|A|$]]|$1|N|3|O|5|6|7|1V|8|@$J|1W|K|1X|L|M]]|9|@$J|1Y|K|1Z|1|20]]|A|$]]|$1|P|3|-4|5|6|7|21|8|@]|9|@]|A|$]]|$1|Q|3|R|5|E|7|22|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|23|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|24|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|25|8|@$J|26|K|27|L|M]]|9|@$J|28|K|29|1|2A]]|A|$]]|$1|W|3|-4|5|6|7|2B|8|@]|9|@]|A|$]]|$1|X|3|Y|5|E|7|2C|8|@]|9|@]|A|$]]|$1|Z|3|-4|5|6|7|2D|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|2E|8|@$J|2F|K|2G|L|M]|$J|2H|K|2I|L|M]|$J|2J|K|2K|L|M]|$J|2L|K|2M|L|M]|$J|2N|K|2O|L|M]|$J|2P|K|2Q|L|M]|$J|2R|K|2S|L|M]]|9|@]|A|$]]|$1|12|3|-4|5|6|7|2T|8|@]|9|@]|A|$]]|$1|13|3|14|5|6|7|2U|8|@]|9|@$J|2V|K|2W|1|2X]|$J|2Y|K|2Z|1|30]]|A|$]]|$1|15|3|-4|5|6|7|31|8|@]|9|@]|A|$]]]|16|$17|$5|18|19|1A|A|$1B|1C]]|1D|$5|18|19|1A|A|$1B|1E]]|1F|$5|18|19|1A|A|$1B|1G]]|1H|$5|18|19|1A|A|$1B|1I]]]]

The answer is implied here:
<blockquote>
Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example)
</blockquote>
A linked list doesn't have an inherent index; calling <code>.get(x)</code> will require the list implementation to find the first entry and call <code>.next()</code> x-1 times (for a O(n) or linear time access), where an array-backed list can just index into <code>backingarray[x]</code> in O(1) or constant time.
If you look at the <a href="http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html" rel="noreferrer">JavaDoc for <code>LinkedList</code></a>, you'll see the comment
<blockquote>
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.
</blockquote>
whereas <a href="http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html" rel="noreferrer">JavaDoc for <code>ArrayList</code></a> has the corresponding
<blockquote>
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 <code>size</code>, <code>isEmpty</code>, <code>get</code>, <code>set</code>, <code>iterator</code>, and <code>listIterator</code> operations 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 <code>LinkedList</code> implementation.
</blockquote>
A <a href="https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations">related question titled &quot;Big-O Summary for Java Collections Framework&quot;</a> has an answer pointing to this resource, <a href="http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf" rel="noreferrer">&quot;Java Collections JDK6&quot;</a> which you might find helpful.

blocks|key|225896|text|为了找到LinkedList的第i个元素，该实现遍历了直到第i个元素的所有元素。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|225897|所以|225898|for(int+i+=+0;+i+<+list.length+;+i%2B%2B+)+{
++++Object+something+=+list.get(i);+//Slow+for+LinkedList
}|code-block|syntax|javascript|225899|entityMap^0|4|A|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|R|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|S|8|@]|D|@]|E|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|N|$]]

To find the i-th element of a <code>LinkedList</code> the implementation goes through all elements up to the i-th.

So

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

blocks|key|231046|text|在链表中，每个元素都有一个指向下一个元素的指针：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|231047|head+->+item1+->+item2+->+item3+->+etc.|code-block|syntax|javascript|231048|要访问item3，您可以清楚地看到，您需要从头部遍历每个节点，直到到达item3，因为您不能直接跳转。|offset|length|style|CODE|231049|因此，如果我想打印每个元素的值，如果我这样写：|231050|for(int+i+=+0;+i+<+4;+i%2B%2B)+{
++++System.out.println(list.get(i));
}|231051|事情是这样的：|231052|head+->+print+head
head+->+item1+->+print+item1
head+->+item1+->+item2+->+print+item2
head+->+item1+->+item2+->+item3+print+item3|231053|这是非常低效的，因为每次你索引的时候，它都会从列表的开头重新开始，遍历每一项。这意味着你的复杂性是有效的O(N%5E2)，仅仅是为了遍历列表！|BOLD|231054|如果我这样做：|231055|for(String+s:+list)+{
++++System.out.println(s);
}|231056|然后会发生这样的事情：|231057|head+->+print+head+->+item1+->+print+item1+->+item2+->+print+item2+etc.|231058|所有操作都在一次遍历中完成，这就是O(N)。|231059|现在，转到List的另一个实现，也就是ArrayList，它由一个简单的数组支持。在这种情况下，上面的两次遍历都是等效的，因为数组是连续的，所以它允许随机跳转到任意位置。|231060|entityMap^0|0|0|3|5|0|0|0|0|0|2|5|1G|6|0|0|0|0|0|H|4|0|5|4|J|9|0^^$0|@$1|2|3|4|5|6|7|1B|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1C|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1D|8|@$I|1E|J|1F|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|1G|8|@]|9|@]|A|$]]|$1|O|3|P|5|D|7|1H|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|1I|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|1J|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|1K|8|@$I|1L|J|1M|K|W]|$I|1N|J|1O|K|L]]|9|@]|A|$]]|$1|X|3|Y|5|6|7|1P|8|@]|9|@]|A|$]]|$1|Z|3|10|5|D|7|1Q|8|@]|9|@]|A|$E|F]]|$1|11|3|12|5|6|7|1R|8|@]|9|@]|A|$]]|$1|13|3|14|5|D|7|1S|8|@]|9|@]|A|$E|F]]|$1|15|3|16|5|6|7|1T|8|@$I|1U|J|1V|K|L]]|9|@]|A|$]]|$1|17|3|18|5|6|7|1W|8|@$I|1X|J|1Y|K|L]|$I|1Z|J|20|K|L]]|9|@]|A|$]]|$1|19|3|-4|5|6|7|21|8|@]|9|@]|A|$]]]|1A|$]]

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

<pre><code>head -&gt; item1 -&gt; item2 -&gt; item3 -&gt; etc.
</code></pre>

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

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

<pre><code>for(int i = 0; i &lt; 4; i++) {
 System.out.println(list.get(i));
}
</code></pre>

what happens is this:

<pre><code>head -&gt; print head
head -&gt; item1 -&gt; print item1
head -&gt; item1 -&gt; item2 -&gt; print item2
head -&gt; item1 -&gt; item2 -&gt; item3 print item3
</code></pre>

This is horribly inefficient because 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 <code>O(N^2)</code> just to traverse the list!

If instead I did this:

<pre><code>for(String s: list) {
 System.out.println(s);
}
</code></pre>

then what happens is this:

<pre><code>head -&gt; print head -&gt; item1 -&gt; print item1 -&gt; item2 -&gt; print item2 etc.
</code></pre>

all in a single traversal, which is <code>O(N)</code>.

Now, going to the other implementation of <code>List</code> which is <code>ArrayList</code>, 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.

blocks|key|3099549|text|虽然公认的答案肯定是正确的，但我可以指出一个小缺陷。引用都铎的话：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3099550|现在，转到List的另一个实现，也就是ArrayList，它由一个简单的数组支持。在这种情况下，上面的两次遍历都是等价的，因为数组是连续的，所以它允许随机跳转到任意位置。|3099551|3099552|这并不完全正确。事实是，|3099553|使用ArrayList的|3099554|，一个手写的计数循环大约快3倍|blockquote|3099555|3099556|3099557|source:+Designing+for+Performance,+Google's+Android+doc|offset|length|3099558|请注意，手写循环引用索引迭代。我怀疑这是因为迭代器与增强的for循环一起使用。它在由连续数组支持的结构中产生较小的性能损失。我也怀疑Vector类可能是这样的。|3099559|我的规则是，尽可能使用增强的for循环，如果你真的关心性能，只对ArrayLists或Vectors使用索引迭代。在大多数情况下，您甚至可以忽略这一点-编译器可能会在后台对此进行优化。|3099560|我只想指出，在安卓开发的上下文中，ArrayLists的两次遍历都是，并不一定等同于。只是发人深省而已。|style|BOLD|3099561|entityMap|0|LINK|mutability|MUTABLE|url|http://developer.android.com/guide/practices/design/performance.html#foreach^0|0|0|0|0|0|0|0|0|0|1J|0|0|0|0|Y|8|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|19|8|@]|9|@]|A|$]]|$1|E|3|F|5|6|7|1A|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|1B|8|@]|9|@]|A|$]]|$1|I|3|J|5|K|7|1C|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|1E|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1F|8|@]|9|@$P|1G|Q|1H|1|1I]]|A|$]]|$1|R|3|S|5|6|7|1J|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1K|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1L|8|@$P|1M|Q|1N|X|Y]]|9|@]|A|$]]|$1|Z|3|-4|5|6|7|1O|8|@]|9|@]|A|$]]]|10|$11|$5|12|13|14|A|$15|16]]]]

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

<blockquote>
 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.
</blockquote>

This is not completely true. The truth is, that 

<blockquote>
 With an ArrayList, a hand-written counted loop is about 3x faster
</blockquote>

<a href="http://developer.android.com/guide/practices/design/performance.html#foreach" rel="noreferrer">source: Designing for Performance, Google's Android doc</a>

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. 

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.

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.

blocks|key|3099594|text|使用偏移量遍历列表以进行查找，例如i，类似于画家Shlemiel的算法。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3099595|3099596|+Shlemiel找到了一份街道油漆工的工作，他在路中间画虚线。第一天，他带着一罐油漆上路，完成了300码的路程。“这真是太好了！”他的老板说：“你干得真快！”然后付给他一个科比。|blockquote|3099597|3099598|第二天，施莱米尔只完成了150码。“嗯，这远没有昨天那么好，但你仍然是一个速度很快的工人。150码是值得尊敬的，”他付给他一个科比。|3099599|第二天，施莱米尔画了30码的路。“只有30个！”他的老板喊道。“这是不能接受的！第一天你就做了十倍的工作！这是怎么回事？”|3099600|“我忍不住，”施莱米尔说。“我一天比一天离油漆罐越来越远！”|3099601|3099602|Source。|3099603|这个小故事可能会让我们更容易理解内部发生的事情，以及为什么它如此低效。|3099604|entityMap|0|LINK|mutability|MUTABLE|url|http://www.joelonsoftware.com/articles/fog0000000319.html^0|H|1|0|0|0|0|0|0|0|0|0|6|0|0|0^^$0|@$1|2|3|4|5|6|7|13|8|@$9|14|A|15|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|16|8|@]|D|@]|E|$]]|$1|G|3|H|5|I|7|17|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|18|8|@]|D|@]|E|$]]|$1|K|3|L|5|6|7|19|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|1A|8|@]|D|@]|E|$]]|$1|O|3|P|5|6|7|1B|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|1C|8|@]|D|@]|E|$]]|$1|R|3|S|5|6|7|1D|8|@]|D|@$9|1E|A|1F|1|1G]]|E|$]]|$1|T|3|U|5|6|7|1H|8|@]|D|@]|E|$]]|$1|V|3|-4|5|6|7|1I|8|@]|D|@]|E|$]]]|W|$X|$5|Y|Z|10|E|$11|12]]]]

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

<blockquote>
 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!"
</blockquote>

<a href="http://www.joelonsoftware.com/articles/fog0000000319.html" rel="noreferrer">Source</a>.

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

Reading the <a href="http://docs.oracle.com/javase/7/docs/api/java/util/List.html" rel="noreferrer">Java documentation for the ADT List</a> it says:

<blockquote>
 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.
</blockquote>

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

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

编译器

Java

阅读时，它会说： List接口提供了四种对列表元素进行位置(索引)访问的方法。列表(像Java数组)是从零开始的。请注意，对于某些实现(例如，LinkedList类)，这些操作的执行时间可能与索引值成比例。因此，如果调用者不知道实现，那么迭代列表中的元素通常比索引列表中的元素更可取。这到底是什么意思？我不明白所得出的结...

问为什么遍历列表会比索引更快呢？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么遍历列表会比索引更快呢？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么遍历列表会比索引更快呢？
EN