什么是最快的列表实现(在java中),在这种情况下,列表将一次创建一个元素,然后在以后的某个时刻读取一个元素？读取将使用迭代器完成,然后列表将被销毁.
我知道get的Big O表示法是O(1),并且对于ArrayList,add是O(1),而LinkedList对于get是O(n),对于add是O(1).迭代器是否具有相同的Big O表示法？
这在很大程度上取决于您是否知道每个列表的最大大小.
如果你这样做,请使用ArrayList; 它肯定会更快.
否则,您可能需要进行个人资料.虽然访问ArrayList是O(1),但创建它并不是那么简单,因为动态调整大小.
需要考虑的另一点是,时空权衡并不明确.每个Java对象都有相当多的开销.虽然ArrayList可能会在剩余插槽上浪费一些空间,但每个插槽只有4个字节(或64位JVM上的8个字节).a的每个元素LinkedList大约是50个字节(在64位JVM中可能是100个字节).因此,ArrayList在LinkedList实际赢得其假定的空间优势之前,您必须拥有相当多的浪费时段.参考地点也是一个因素,ArrayList也是优选的.
在实践中,我几乎总是使用ArrayList.
第一个想法:
重构您的代码以不需要列表.
将数据简化为标量数据类型,然后使用:int []
或者甚至只使用你拥有的任何对象的数组:Object [] - John Gardner
将列表初始化为完整大小:new ArrayList(123);
当然,正如其他人提到的那样,进行性能测试,证明您的新解决方案是一种改进.
迭代链表是每个元素O(1).
每个选项的Big O运行时都是相同的.由于更好的内存局部性,ArrayList可能会更快,但你必须测量它才能确定.挑选任何使代码最清晰的东西.
注意,LinkedList如果天真地完成,则遍历实例可以是O(n ^ 2).特别:
List
这在效率方面是绝对可怕的,因为每次迭代必须遍历列表i 两次.如果您使用LinkedList,请确保使用Iterator或Java 5的增强型for循环:
for (Object o : list) {
// ...
}
上面的代码是O(n),因为列表是在原地遍历的.
为了避免上述所有麻烦,只需使用即可ArrayList.它并不总是最佳选择(特别是对于空间效率),但它通常是一个安全的选择.
京公网安备 11010802040832号 | 京ICP备19059560号-6 