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

Question

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

Ren*_*ani 69 java collections performance

什么是Java中最快的集合？

我只需要添加和删除操作,顺序并不重要,等于元素不是问题,只不过添加和删除是非常重要的.

没有限制大小也很重要.

这些集合中将包含对象.

目前我正在使用ArrayDeque,因为我发现这是更快的Queue实现.

Answer 1

Col*_*inD 86

ArrayDeque是最好的.请参阅此基准,该博客文章来自此基准测试的结果.ArrayDeque没有节点分配的开销,也不会有LinkedList移除数组内容的开销ArrayList.在基准测试中,它执行大约3倍以及LinkedList大型队列,甚至比ArrayList空队列略好.为了获得最佳性能,您可能希望为其提供足够大的初始容量,以容纳一次可能容纳的元素数量,以避免许多调整大小.

之间ArrayList和LinkedList,似乎这取决于平均总要素队列将包含在任何给定的时间,并且LinkedList击败ArrayList起价约为10元.

我意识到这个问题已经过时了,但你的链接都已经死了.有没有替代网址？ (6认同)
由于我和@rath有同样的问题,我抓了原来的博客,发现原文:[https://publicobject.com/2010/07/07/caliper_confirms_reality_linked_list_vs_array_list/](https://publicobject.com/2010)/07/07/caliper_confirms_reality_linked_list_vs_array_list /).不幸的是,如果我试图查看基准测试结果,我会收到401 - 未经授权的错误. (4认同)
这是另一个实验,证实ArrayDeque比LinkedList快3倍:http://java-performance.info/linkedlist-performance/ (3认同)

Answer 2

Boz*_*zho 6

你可以使用java.util.LinkedList- 它是双重链接和cicrular,所以添加到一端并取另一端是O(1)

无论您选择哪种实现,请通过Queue界面引用它,以便在结果不符合您的情况时轻松更改它(当然,如果首先是队列,则需要排队)

更新:科林的回答显示了一个基准,结论ArrayDeque是更好.两者都有O(1)操作,但LinkedList创建新对象(节点),略有性能.由于两者都有O(1)我不认为选择它会是错误的LinkedList.

@EJP:`ArrayDeque` _is_ O(1)用于在前端/末端添加和删除(即用作队列或堆栈时),因为它是一个圆形数组,在这些情况下不会复制任何内容.此外,调整大小是偶尔的操作,通常可以通过适当的初始容量来避免."LinkedList"的额外对象创建(以及该对象的垃圾收集)的开销会影响队列中的每个添加/删除.我链接的基准测试表明它一直是`LinkedList`的3倍. (15认同)
`O(1) != O(1)`。“O()”只是复杂性的衡量标准，而不是执行时间的衡量标准。无论“n”如何，始终需要 5 年的操作都是“O(1)”，就像总是需要 5 毫秒的操作一样。我宁愿使用需要 5 毫秒的那个。如果“n”没有变得太大，即使每个元素需要 5 毫秒的操作（即“O(n)”）也会比 5 年的操作更好。 (3认同)
ArrayDeque 客观上更好。 (2认同)

归档时间：	14 年，7 月前
查看次数：	50792 次
最近记录：	9 年，5 月前