什么是具有队列基本功能的最快 Java 集合？

Question

什么是具有队列基本功能的最快 Java 集合？

javaperformancecollections

91

Java中最快的集合是什么？

我只需要添加和删除操作，顺序不重要，相等的元素不是问题，除添加和删除之外没有其他重要内容。

无大小限制也很重要。

这些集合将包含对象。

目前我正在使用ArrayDeque，因为我发现这是最快的队列实现。

- Renato Dinhani

14

如果顺序不重要，那么你并不需要寻找一个队列。 - BoltClock

4

“过早优化是万恶之源。” - mre

67

选择正确的集合不是过早优化。 - Bozho

这是第二个项目的网络爬虫，因此速度在这里是一个重要的项目。 - Renato Dinhani

8

BoltClock，对于Java中的大写Q队列，那是不正确的。它只是指“具有头元素的可变集合”。请重新阅读java.util.Queue。 - Kevin Bourrillion

显示剩余3条评论

3个回答

7

您可以使用java.util.LinkedList - 它是双向循环链表，因此在一端添加和在另一端取出的时间复杂度都是O(1)。

无论选择哪种实现方式，请通过Queue接口引用它，以便在需要时轻松更改（如果当然，队列是您首先需要的）。

更新：Colin的答案展示了一个基准测试，得出ArrayDeque更好的结论。两者都有O(1)操作，但LinkedList会创建新对象（节点），这会稍微影响性能。由于两者都有O(1)，我认为选择LinkedList也不会有太大问题。

- Bozho

2

ArrayDeque 是客观上更好的选择。 - ColinD

1

@ColinD @Bozho，ArrayDeque 中的数组调整大小也是需要考虑算法复杂度的关键。任何涉及数组的操作都是 O(N) 的时间复杂度，而任何涉及链表的操作都是 O(1) 的时间复杂度。 - user207421

20

@EJP: ArrayDeque 在作为队列或栈使用时，在添加和删除前/后端时是 O(1) 的，因为它是一个循环数组，在这些情况下不会复制任何内容。此外，重新调整大小是一种偶尔需要进行的操作，通常可以通过适当的初始容量来避免。LinkedList 每次在队列中进行添加/删除操作时都需要额外创建一个对象（以及该对象的垃圾回收）。我提供的基准测试结果表明，ArrayDeque 的速度始终比 LinkedList 快 3 倍左右。 - ColinD

3

O(1) != O(1)。O() 仅是复杂度的一种度量方式，而非执行时间。一个始终需要 5 年时间的操作无论 n 的大小如何都是 O(1)，而一个始终需要 5 毫秒的操作也是 O(1)。我宁愿使用只需 5 毫秒的操作。即使一个操作每个元素需要 5 毫秒（即 O(n)），如果 n 不太大，它也会比需要 5 年的操作更好。 - Erick G. Hagstrom

@ErickG.Hagstrom 没有人质疑这一点。我的更新表明，在某种情况下，O(1)更快。但鉴于操作之间的相对相似性，O-符号是速度的指示，尽管它确实表示复杂性。 - Bozho

显示剩余5条评论

0

ConcurrentLinkedDeque 是多线程队列的最佳选择。

- Geker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ColinD · Accepted Answer

ArrayDeque是最好的选择。参见这个基准测试，它来自于这篇博客文章，介绍了关于这个问题的基准测试结果。相比于LinkedList需要分配新节点的开销以及ArrayList在删除元素时要移动数组内容的开销，ArrayDeque没有这些额外的开销。在基准测试中，对于大队列，它的性能是LinkedList的3倍，甚至在空队列上表现略好于ArrayList。为了获得最佳性能，您可能需要给它一个足够大的初始容量，以便能够在每次添加元素时避免重复调整大小。

在ArrayList和LinkedList之间，似乎取决于队列在任何给定时间包含的平均总元素数量，并且LinkedList在大约10个元素时就开始超过ArrayList。