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屋！