ArrayList与LinkedList的JDK8性能 [英] JDK8 performance of ArrayList compared to LinkedList

问题描述

我开始看到越来越多的基准测试，这些基准演示了ArrayList在下面的大"插入示例的性能方面如何压倒LinkedList: Gluelist

I am starting to see more and more benchmarks that demonstrate ArrayList crushing LinkedList in terms of performance for 'large' inserts example below: Gluelist

Adding(1M) Elements (5 Tests Avg.)

LinkedList: 174.8 milliseconds
ArrayList:  76.4 milliseconds
GlueList:   39.2 milliseconds

Adding(10M) Elements (5 Tests Avg.)

LinkedList: 8975.6 milliseconds
ArrayList:  4118.2 milliseconds
GlueList:   3320.1 milliseconds

我在带有JDK8.latest的RHEL 7.2上进行了类似的测试，并看到了相似的结果.我的印象是，即使在最坏的情况下，LinkedList插入也是O(1)，并且由于复制操作，ArrayList的取值> O(1)(我意识到我们可以讨论摊销成本，但这超出了范围).我的问题是这样的:考虑到当容量接近用尽时ArrayList强制执行复制操作，LinkedList的性能如何比ArrayList差?

I ran similar tests on a RHEL 7.2 with JDK8.latest and saw similar results. I am under the impression that a LinkedList insert is O(1) even in the worst case and an ArrayList takes > O(1) because of the copy operation (I realize that we can discuss amortized costs, but that is out of scope). My question is this: How is LinkedList performing worse than ArrayList given that ArrayList forces a copy operation when capacity is nearly reached?

推荐答案

它们具有相同的大O，但这并不能告诉您恒定的关系.它告诉您它们在理想的计算机上而不是真实的计算机上的行为.

They have the same big O but that doesn't tell you about the constant relationship. It tells you how they behave on an idealised machine, not a real machine.

LinkedList分配并使用更多的内存.它为每个节点创建一个24字节的对象，其中ArrayList通常每个引用使用4个字节，并且创建的对象要少得多.

LinkedList allocates and uses more memory. It creates a 24 byte object per node where as an ArrayList uses 4 bytes (usually) per reference and creates far less objects.

这篇关于ArrayList与LinkedList的JDK8性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！