我开始看到越来越多的基准测试表明,在“大型”插入的性能方面,ArrayList压垮了LinkedList。示例如下: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我在RHEL 7.2上用JDK8.latest运行了类似的测试,看到了类似的结果。我的印象是,即使在最坏的情况下,LinkedList插入也是O(1),并且由于复制操作,ArrayList占用> O(1) (我意识到我们可以讨论摊销成本,但这超出了范围)。我的问题是:在容量接近极限时,如果ArrayList强制执行拷贝操作,LinkedList的性能如何比ArrayList差?
发布于 2016-08-14 07:56:55
它们有相同的大O,但这并不能告诉你关于恒定关系的信息。它告诉你它们在理想化的机器上的行为,而不是真正的机器。
LinkedList分配和使用更多的内存。它为每个节点创建一个24字节的对象,而作为ArrayList,每个引用使用4个字节(通常),并且创建的对象要少得多。
发布于 2016-08-13 00:05:42
大O在这一点上对你没有真正的帮助。它告诉你增长的方向,但它不会给你绝对的数字。
ArrayList使用数组,并对本机System.arrayCopy()调用进行了高度优化。
LinkedLists必须为每个单独的节点创建一个包装器对象,并在其中存储指向下一个和前一个节点的指针。这需要时间。
ArrayList在插入时不会创建单个对象,除非它调整数组的大小,而这种情况并不经常发生。
发布于 2016-08-13 00:17:30
https://stackoverflow.com/questions/38922137
复制相似问题