其中列出了<Object> 执行将以最快的一个通读，写，然后摧毁？

StackOverflow https://stackoverflow.com/questions/135314

  •  02-07-2019
  •  | 
  •  

题

什么是最快的清单的实施(在java)在方案中的列表将是创建一种元素在一段时间，然后在稍后的一点是读取一种元素在一段时间?读取会完成了一个迭代和随后的清单将随后被销毁。
我知道，大O表示法得到的是O(1)和增加是O(1)针对列表，同时链表是O(n)对于获得和O(1)为增加。不迭代的行为与同一大O符号?

有帮助吗？

解决方案

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

如果这样做，请使用 ArrayList ;它肯定会更快。

否则，您可能需要进行个人资料。虽然访问 ArrayList 是O（1），但由于动态调整大小，创建它并不是那么简单。

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

实际上，我几乎总是使用 ArrayList 。

其他提示

第一个想法：

  • "重构"你的代码，不需要列表。
  • 简化数据的下一个标的数据类型，然后使用： int[]
  • 甚至只是使用一系列的任何对象，你有： 目[] -约翰*加德纳
  • 初始化列表的全尺寸: 新。(123);

当然，正如其他人提到的，做性能检测，证明新的解决方案是一个进步。

遍历链表是每个元素的O（1）。

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

注意，如果天真地完成，迭代遍历 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的增强 -loop：

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

上面的代码是O（n），因为列表是在原地遍历的。

要避免上述所有麻烦，只需使用 ArrayList 即可。它并不总是最佳选择（特别是对于空间效率），但它通常是一个安全的选择。

我建议对它进行基准测试。阅读API是一回事，但在你亲自尝试之前，它就是学术性的。

应该公平易于测试，只需确保您进行有意义的操作，否则热点将超越智能并将其优化为NO-OP：）

你几乎可以肯定想要一个 。.都加入和阅读有"摊销固定的时间"(即O(1))中规定的文件(注意，这是真实的，即使如果列出已经增加它的大小-这是设计成像看到 http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html ).如果你知道大致数量的对象，你将能保存那么即使。尺寸增加以消除。

添加以结束的一个链表是O(1)，但是恒定的乘数大于对列表(因为你通常是创造一个节目，每次)。阅读是几乎完全相同的。如果您使用的是一个迭代器。

这是一个很好的规则总是使用最简单的结构可以，除非有一个很好的理由。这里有没有这样的理由。

的确切引用的文件。是："所添加的操作运行中的摊销固定的时间，也就是增加n元素需要O(n)的时间。所有其他操作运行在线性时间(大约发言).恒因素相比较低，对于链表执行。"

有一个名为 GlueList 的新List实现，它比所有经典的List实现更快。

我实际上已经开始认为应该避免使用具有非确定性行为的数据结构，例如ArrayList或HashMap，所以我想说如果你可以绑定它的大小，只使用ArrayList;任何无界列表都使用LinkedList。那是因为我主要编码具有接近实时要求的系统。

主要问题是任何内存分配（任何添加操作都可能随机发生）也可能导致垃圾回收，任何垃圾回收都可能导致您错过目标。分配越大，发生的可能性越大，如果使用CMS收集器，这也会更加复杂。 CMS是非压缩的，因此为新的链表节点寻找空间通常比为新的10,000个元素阵列寻找空间更容易。

您的编码方法越严格，您就可以越接近实时库存JVM。但是，只选择具有确定性行为的数据结构是您必须采取的第一步。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top