Java中的高效数组扩展

Question

在C/C++中,我们realloc将为现有集合有效地分配额外空间.我猜它在复杂性上是次线性的(甚至是常数).

有没有办法在Java中实现相同的目标？这是我看过的项目,

1. 数组调整大小是不可能的,
2. 将阵列复制到更大尺寸的阵列是复杂的线性.看着这两个System.arrayCopy以及Arrays.copyOf
3. ArrayList 必须与上面的第2点相同.

注意:我的要求是可能进一步扩展一个非常大的数组.

Answer 1

realloc在实践中可能是O(n),因为它有时/经常涉及记忆复制.从这个意义上讲,在Java中分配新数组与理论复杂性相当.

现在Java总是将新分配的内存归零,这可能会花费更长的时间,但OTOH GC具有疯狂快速的内存分配,因此它甚至可能比realloc某些情况下更快.我期望一种策略,即在Java中分配新数组的总体速度大致相当realloc.可能Java对于较小的数组更好,C/C++将具有大数组的优势,但是YMMV.您必须确定您的特定实施和工作量的基准.

整体而言:

• 不要担心,只需在Java中重新分配新数组
• 如果你这么做,请确保重新创建具有比你需要的更多空间的数组,这样你就不需要重新分配添加的每个元素(这就是Java ArrayList在内部所做的事情.

最后但重要的一点:除非你编写非常低级的代码,否则你可能不应该担心这个问题.只需使用已经存在的精美集合类之一(Java Collections,Google Collections,Trove等),让他们为您处理所有这些内容.