调整阵列大小时我应该添加多少？

Question

我正在和另一个学生竞争制作最快的家庭作业版本,而且由于性能原因,我没有使用ArrayList(我自己将基准时间从56秒缩短到4),但我是想知道我每次需要时应该调整阵列大小.具体来说,我的代码的相关部分是这样的:

private Node[] list;
private int size; // The number of items in the list
private static final int N; // How much to resize the list by every time

public MyClass(){
  list = new Node[N];
}

public void add(Node newNode){
  if(size == list.length){
    list = Arrays.copyOf(list, size + N);
  }
  list[size] = newNode;
  size++;
}

TL; DR:我应该做什么N？

Answer 1

建议在调整大小时将数组的大小加倍.将尺寸加倍会导致线性时间成本摊销.

天真的想法是调整大小值有两个成本:

• 复制性能成本 - 将元素从先前阵列复制到新阵列的成本,以及
• 内存开销成本 - 未使用的分配内存的成本.

如果要通过一次添加一个元素来重新调整数组大小,则内存开销为零,但复制成本变为二次方.如果你要分配太多的插槽,复制成本将是线性的,但内存开销太大.

加倍导致线性摊销成本(即很长一段时间,复制的成本与阵列的大小成线性关系),并且保证不会浪费超过一半的阵列.

更新:顺便说一句,显然Java ArrayList扩展了(3/2).这使得内存保守一点,但在复制方面要花费更多.基准测试对您的使用不会有害.

MINOR校正:加倍会使成本大小调整线性摊销,但会确保您有一个摊销的常数时间插入.查看CMU关于摊销分析的讲座.

Answer 2

3/2很可能被选为"干净利落,但比phi少"的东西.2003年11月发生了一个史诗般的线程,comp.lang.c++.moderated探讨phi如何在重新分配第一个适配分配器的过程中重新使用先前分配的存储.

请参阅Andrew Koenig的第7篇文章,首次提到phi应用于此问题.