Java 哪个 list<Object> 实现对于单次写入、读取和销毁速度最快？

Which list<Object> implementation will be the fastest for one pass write, read, then destroy?

提问by WolfmanDragon

What is the fastest list implementation (in java) in a scenario where the list will be created one element at a time then at a later point be read one element at a time? The reads will be done with an iterator and then the list will then be destroyed.
I know that the Big O notation for get is O(1) and add is O(1) for an ArrayList, while LinkedList is O(n) for get and O(1) for add. Does the iterator behave with the same Big O notation?

在一次创建一个元素然后在稍后读取一个元素的场景中，最快的列表实现（在 Java 中）是什么？读取将使用迭代器完成，然后列表将被销毁。
我知道 get 的 Big O 表示法是 O(1)，对于 ArrayList，add 是 O(1)，而 LinkedList 对于 get 是 O(n)，对于 add 是 O(1)。迭代器是否使用相同的 Big O 表示法？

采纳答案by erickson

It depends largely on whether you know the maximum size of each list up front.

这在很大程度上取决于您是否预先知道每个列表的最大大小。

If you do, use ArrayList; it will certainly be faster.

如果这样做，请使用ArrayList; 它肯定会更快。

Otherwise, you'll probably have to profile. While access to the ArrayListis O(1), creating it is not as simple, because of dynamic resizing.

否则，您可能需要进行配置文件。虽然访问ArrayList是 O(1)，但由于动态调整大小，创建它并不那么简单。

Another point to consider is that the space-time trade-off is not clear cut. Each Java object has quite a bit of overhead. While an ArrayListmay waste some space on surplus slots, each slot is only 4 bytes (or 8 on a 64-bit JVM). Each element of a LinkedListis probably about 50 bytes (perhaps 100 in a 64-bit JVM). So you have to have quite a few wasted slots in an ArrayListbefore a LinkedListactually wins its presumed space advantage. Locality of reference is also a factor, and ArrayListis preferable there too.

需要考虑的另一点是时空权衡并不明确。每个 Java 对象都有相当多的开销。虽然ArrayList可能会在多余的插槽上浪费一些空间，但每个插槽只有 4 个字节（或 64 位 JVM 上的 8 个）。a 的每个元素LinkedList大约有 50 个字节（在 64 位 JVM 中可能是 100 个）。因此，ArrayList在LinkedList实际赢得其假定的空间优势之前，您必须在 a 中浪费很多插槽。参考位置也是一个因素，ArrayList在那里也是可取的。

In practice, I almost always use ArrayList.

在实践中，我几乎总是使用ArrayList.

回答by Khoth

Iterating through a linked list is O(1) per element.

遍历链表的每个元素是 O(1)。

The Big O runtime for each option is the same. Probably the ArrayList will be faster because of better memory locality, but you'd have to measure it to know for sure. Pick whatever makes the code clearest.

每个选项的 Big O 运行时都是相同的。由于更好的内存局部性，ArrayList 可能会更快，但您必须对其进行测量才能确定。选择使代码最清晰的任何内容。

回答by KyleLanser

First Thoughts:

第一个想法：

• Refactor your code to not need the list.
• Simplify the data down to a scalar data type, then use: int[]
• Or even just use an array of whatever object you have: Object[]- John Gardner
• Initialize the list to the full size: new ArrayList(123);

• 重构您的代码以使其不需要列表。
• 将数据简化为标量数据类型，然后使用：int[]
• 或者甚至只是使用您拥有的任何对象的数组：Object[]- John Gardner
• 将列表初始化为完整大小：new ArrayList(123);

Of course, as everyone else is mentioning, do performance testing, prove your new solution is an improvement.

当然，正如其他人所提到的，做性能测试，证明你的新解决方案是一种改进。

回答by skaffman

I suggest benchmarking it. It's one thing reading the API, but until you try it for yourself, it'd academic.

我建议对其进行基准测试。阅读 API 是一回事，但除非您亲自尝试，否则它只是学术性的。

Should be fair easy to test, just make sure you do meaningful operations, or hotspot will out-smart you and optimise it all to a NO-OP :)

应该很容易测试，只要确保你做有意义的操作，或者热点会比你聪明，并将其全部优化为无操作:)

回答by Daniel Spiewak

Note that iterating through an instance of LinkedListcan be O(n^2) if done naively. Specifically:

请注意，LinkedList如果天真地完成，遍历 的实例可能是 O(n^2)。具体来说：

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

This is absolutely horrible in terms of efficiency due to the fact that the list must be traversed up to itwicefor each iteration. If you do use LinkedList, be sure to use either an Iteratoror Java 5's enhanced for-loop:

由于每次迭代必须遍历列表i两次，因此在效率方面这绝对是可怕的。如果您确实使用了LinkedList，请务必使用 anIterator或 Java 5 的增强for循环：

for (Object o : list) {
    // ...
}

The above code is O(n), since the list is traversed statefully in-place.

上面的代码是 O(n)，因为列表是在原地有状态地遍历的。

To avoid all of the above hassle, just use ArrayList. It's not always the best choice (particularly for space efficiency), but it's usually a safe bet.

为避免上述所有麻烦，只需使用ArrayList. 它并不总是最佳选择（尤其是对于空间效率而言），但通常是一个安全的选择。

回答by DJClayworth

You almost certainly want an ArrayList. Both adding and reading are "amortized constant time" (i.e. O(1)) as specified in the documentation (note that this is true even if the list has to increase it's size - it's designed like that see http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html). If you know roughly the number of objects you will be storing then even the ArrayList size increase is eliminated.

你几乎肯定想要一个ArrayList。添加和读取都是文档中指定的“摊销常数时间”（即 O(1)）（请注意，即使列表必须增加它的大小也是如此 - 它的设计就像看到http://java.sun .com/j2se/1.5.0/docs/api/java/util/ArrayList.html）。如果您大致知道将要存储的对象数量，那么即使 ArrayList 大小的增加也会被消除。

Adding to the end of a linked list is O(1), but the constant multiplier is larger than ArrayList (since you are usually creating a node object every time). Reading is virtually identical to the ArrayList if you are using an iterator.

添加到链表的末尾是 O(1)，但常数乘数大于 ArrayList（因为您通常每次都创建一个节点对象）。如果您使用迭代器，读取实际上与 ArrayList 相同。

It's a good rule to always use the simplest structure you can, unless there is a good reason not to. Here there is no such reason.

总是尽可能使用最简单的结构是一个很好的规则，除非有充分的理由不这样做。这里没有这样的理由。

The exact quote from the documentation for ArrayList is: "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 LinkedList implementation."

ArrayList 文档中的确切引用是：“添加操作在摊销常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。常数因子与 LinkedList 实现相比较低。”

回答by Kevin Lafayette

I have actually begun to think that any use of data structures with non-deterministic behavior, such as ArrayList or HashMap, should be avoided, so I would say only use ArrayList if you can bound its size; any unbounded list use LinkedList. That is because I mainly code systems with near real time requirements though.

我实际上已经开始认为应该避免使用任何具有非确定性行为的数据结构，例如 ArrayList 或 HashMap，所以我会说只有在可以限制其大小的情况下才使用 ArrayList；任何无界列表都使用 LinkedList。那是因为我主要编写具有近实时要求的系统。

The main problem is that any memory allocation (which could happen randomly with any add operation) could also cause a garbage collection, and any garbage collection can cause you to miss a target. The larger the allocation, the more likely this is to occur, and this is also compounded if you are using CMS collector. CMS is non-compacting, so finding space for a new linked list node is generally going to be easier than finding space for a new 10,000 element array.

主要问题是任何内存分配（任何添加操作都可能随机发生）也可能导致垃圾收集，而任何垃圾收集都可能导致您错过目标。分配越大，这种情况发生的可能性就越大，如果您使用 CMS 收集器，情况也会更加复杂。CMS 是非压缩的，因此为新的链表节点寻找空间通常比为新的 10,000 个元素数组寻找空间更容易。

The more rigorous your approach to coding, the closer you can come to real time with a stock JVM. But choosing only data structures with deterministic behavior is one of the first steps you would have to take.

您的编码方法越严格，您就可以越接近实时使用股票 JVM。但只选择具有确定性行为的数据结构是您必须采取的第一步。

回答by Ertu?rul ?etin

There is a new List implementation called GlueListwhich is faster than all classic List implementations.

有一个名为GlueList的新 List 实现，它比所有经典 List 实现都快。