代码之家 › 专栏 › 技术社区 › Brendan Long

调整数组大小时应添加多少?

optimization arrays java

Brendan Long · 技术社区 · 15 年前

我正在和另一个学生进行一个竞赛,以使我们的家庭作业的最快版本,我没有使用数组列表的性能原因(调整数组的大小我自己削减基准时间从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++;
}

我应该做什么 N ?

9 回复 | 直到 15 年前

notnoop 15 年前

建议在调整大小时将数组的大小增加一倍。双倍的规模导致摊销的线性时间成本。

幼稚的想法是有两个与调整大小值相关的成本:

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

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

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

更新:顺便说一下,显然是Java ArrayList 扩大(3/2)。这使得它的内存更加保守,但在复制方面要花费更多。为你的使用做基准不会有什么影响。

小修正:加倍将使成本调整线性摊销,但将确保您有一个摊销的固定时间插入。检查 CMU's lecture on Amortized Analysis .

seh Alexei 15 年前

3/2很可能被选为“一个划分清晰但小于 phi “。有 an epic thread on comp.lang.c++.moderated 回到2003年11月探索 φ 为第一个合适的分配器在重新分配期间重用以前分配的存储建立上限。

见 post #7 from Andrew Koenig 第一次提到 φ 的应用程序。

Carl Smotricz 15 年前

如果您大致知道将有多少个项,那么就将数组或arraylist预先分配到该大小,并且您将永远不必展开。无与伦比的性能!

如果不能做到这一点,实现良好的摊余成本的一个合理的方法就是保持一定比例的微利。100%或50%是常见的。

sdtom 15 年前

您应该将列表的大小调整为以前大小的倍数,而不是每次添加一个常量。

例如:

newSize = oldSize * 2;

不

newSize = oldSize + N;

Ben S 15 年前

如果内存不是问题,就从一个大数组开始。

Christian P. 15 年前

你的代码看起来和arraylist差不多——如果你知道你将要使用一个大的列表,你可以在创建列表时传递一个初始大小,并且完全避免调整大小。当然,这是假设您使用的是原始速度,而内存消耗并不是问题。

TofuBeer 15 年前

从其中一个答案的评论中:

问题是记忆不是问题,但我正在随意阅读大文件。

试试这个:

new ArrayList<Node>((int)file.length());

你也可以用你的数组来完成。在这两种情况下都不应该调整大小,因为数组将是文件的大小(假设文件不再是int…)。

Mark Bessey 15 年前

为了获得最佳性能,您需要尽可能少地调整大小。将初始大小设置为您通常需要的大小,而不是从n个元素开始。在这种情况下,为n选择的值无关紧要。

如果要创建大量大小不同的列表对象,那么您需要使用基于池的分配器,在退出之前不要释放内存。

为了完全消除复制操作,可以使用数组列表

crowne 15 年前

这是一个类比,很久以前我在大型机上工作时,我们使用了一个名为vsam的文件系统,它要求您指定初始文件大小和所需的空闲空间量。

每当空闲空间量降到所需阈值以下时,所需的空闲空间量将在后台分配,而程序将继续处理。

这将是有趣的,看看这是否可以在Java中使用一个单独的线程来分配额外的空间,并在主线程继续处理的时候将它附加到数组的末尾。