哪个列表<Object>实现最快,一次写入,读取,然后销毁？

Question

什么是最快的列表实现(在java中),在这种情况下,列表将一次创建一个元素,然后在以后的某个时刻读取一个元素？读取将使用迭代器完成,然后列表将被销毁.
我知道get的Big O表示法是O(1),并且对于ArrayList,add是O(1),而LinkedList对于get是O(n),对于add是O(1).迭代器是否具有相同的Big O表示法？

Answer 1

这在很大程度上取决于您是否知道每个列表的最大大小.

如果你这样做,请使用ArrayList; 它肯定会更快.

否则,您可能需要进行个人资料.虽然访问ArrayList是O(1),但创建它并不是那么简单,因为动态调整大小.

需要考虑的另一点是,时空权衡并不明确.每个Java对象都有相当多的开销.虽然ArrayList可能会在剩余插槽上浪费一些空间,但每个插槽只有4个字节(或64位JVM上的8个字节).a的每个元素LinkedList大约是50个字节(在64位JVM中可能是100个字节).因此,ArrayList在LinkedList实际赢得其假定的空间优势之前,您必须拥有相当多的浪费时段.参考地点也是一个因素,ArrayList也是优选的.

在实践中,我几乎总是使用ArrayList.

Answer 2

第一个想法:

• 重构您的代码以不需要列表.
• 将数据简化为标量数据类型,然后使用:int []
• 或者甚至只使用你拥有的任何对象的数组:Object [] - John Gardner
• 将列表初始化为完整大小:new ArrayList(123);

当然,正如其他人提到的那样,进行性能测试,证明您的新解决方案是一种改进.

Answer 3

迭代链表是每个元素O(1).

每个选项的Big O运行时都是相同的.由于更好的内存局部性,ArrayList可能会更快,但你必须测量它才能确定.挑选任何使代码最清晰的东西.

Answer 4

注意,LinkedList如果天真地完成,则遍历实例可以是O(n ^ 2).特别:

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

这在效率方面是绝对可怕的,因为每次迭代必须遍历列表i 两次.如果您使用LinkedList,请确保使用Iterator或Java 5的增强型for循环:

for (Object o : list) {
    // ...
}

上面的代码是O(n),因为列表是在原地遍历的.

为了避免上述所有麻烦,只需使用即可ArrayList.它并不总是最佳选择(特别是对于空间效率),但它通常是一个安全的选择.