logo标签列表

当调整数组大小时，应该添加多少？

javaarraysoptimization
3

我正在与另一个学生比赛，以制作我们的家庭作业任务的最快版本，出于性能原因，我不使用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++;
}

简而言之：我应该制作什么 N？

2
“new” 是一个合法的变量名（在 add() 声明中）吗？ - Carl Smotricz
哎呀，我的意思是那应该是新节点（newNode）。 - Brendan Long
9个回答
7

3/2很可能被选择为“可以整除但小于phi的数”。在2003年11月，comp.lang.c++.moderated上有一个史诗般的帖子探讨了phi如何为首次适配器在重新分配期间重用先前分配的存储空间建立一个上限。

请参见Andrew Koenig的第7篇文章，其中首次提到了phi在此问题中的应用。

6
建议在调整大小时将数组的大小加倍。将大小加倍会导致摊销的线性时间成本。
天真的想法是，调整大小值有两个相关成本：
- 复制性能成本 - 从先前的数组复制元素到新数组的成本，以及 - 内存开销成本 - 分配但未使用的内存成本。
如果您每次添加一个元素来重新调整数组大小，则内存开销为零，但复制成本变为二次方。如果您分配了太多的插槽，则复制成本将是线性的，但内存开销过大。
加倍 leads to a linear amortized cost（即长时间内，复制成本与数组大小成线性关系），并且保证不会浪费超过一半的数组。
更新：顺便说一下，显然Java的ArrayList通过（3/2）扩展。这使它在内存上更加保守，但在复制方面成本稍高。进行基准测试以供使用不会有坏处。

小修正：加倍会使成本调整线性摊销，但会确保您具有摊销常数时间插入。请参阅CMU的摊销分析讲座。

我在我的代码中使用了动态扩容的思路，并进行了基准测试。新建一个大小为1000的ArrayList，与我使用初始大小为1000的代码相比，速度慢了大约100倍。 - Brendan Long
加倍操作阻止了之前分配的空间的使用，即使该空间仍然可用。乘数phi定义了允许此类重复使用的增长因子的上限。对于不受竞争影响的首次适应分配器，增长率为phi的情况只需要在每隔一个重新分配时分配更多的空间。 - seh
你希望增长因子小于黄金比例（phi）以便可以重复利用留下的空间。这就是为什么1.5被优选而不是2。 - deadalnix
3
如果您大致知道有多少项，那么请预先分配数组或ArrayList到该大小，这样您就永远不必扩展。无与伦比的性能！
如果做不到这一点，实现良好平摊成本的合理方法是按某个百分比增长。100％或50％很常见。
2

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

例如：

newSize = oldSize * 2;

不要。
newSize = oldSize + N;
2
每次需要调整大小时，将其大小加倍，除非您知道更多或更少的大小最合适。
如果内存不是问题，可以一开始就使用一个大数组。
问题在于内存不是问题，但我正在读取一个任意大的文件。 - Brendan Long
同时我要提交这个作业，所以将list = new Node[Integer.MAX_VALUE]可能会让老师不高兴。 - Brendan Long
1
那也很可能比系统拥有的内存更多。我会从一些更适中的东西开始，比如1024或2048。 - Ben S
2

您的代码似乎与ArrayList做的事情差不多 - 如果您知道将使用大型列表，可以在创建列表时传递初始大小，并避免完全调整大小。当然，这假设您追求原始速度并且内存消耗不是问题。

我用N = 1000测试了我的代码，与new ArrayList(1000)相比，我的代码快了大约100倍。不过这个主意不错，我之前没有考虑设置初始大小。 - Brendan Long
看起来很奇怪，但我怀疑 ArrayList 可能有一些健全性检查会减慢它的速度。 - Christian P.
@Brendan，你的基准测试结果看起来非常奇怪。查看ArrayList的源代码，至少在我的openjdk 1.6.0上，它做的正是你所做的事情；除了一些算术运算来计算新容量（与复制数组的成本相比可以忽略不计）。 - Kieron
这是我的测试脚本：http://pastebin.com/m536bb968 这是我的数组类：http://pastebin.com/m75f34b75在我的电脑上，ArrayList 大约需要 2.5 秒，而我的数组只需要 0.2 秒。我不知道为什么... 我正在使用 Sun JDK。 - Brendan Long
我也尝试将第二个更改为list = Arrays.copyOf(list, size * 3/2);，但没有任何变化。 - Brendan Long
哦，是 Object[] 的部分。如果你把我的代码改成 Object[] 列表，速度就会一样了。:( - Brendan Long
1

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

问题在于内存不是问题，但我正在读取一个任意大的文件。

试试这个：

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

您也可以使用数组完成此操作。这样无论哪种情况都不需要重新调整大小，因为数组的大小将与文件大小相同（假设文件长度不超过 int）。
0
为了获得最佳性能，您应该尽可能少地调整大小。将初始大小设置为通常所需的尽可能大，而不是从N个元素开始。在这种情况下，您选择的N值将不那么重要。
如果您要创建大量这些大小不同的列表对象，则应使用基于池的分配器，并在退出之前不释放内存。
为了完全消除复制操作，您可以使用数组列表。
0

给你一个类比，很久以前我在使用主机时，我们使用了一个叫做VSAM的文件系统，它需要你指定初始文件大小和所需的空闲空间。

当空闲空间的数量降低到所需的阈值以下时，后台会分配所需的空闲空间，而程序继续处理。

如果可以在Java中使用一个单独的线程来分配额外的空间，并将其“附加”到数组的末尾，同时主线程继续处理，那将是很有意思的。

我真的怀疑Java会给你那么多控制权。我能做的最好的事情就是创建一个新数组，并希望Java的数组复制会复制一段内存，而不仅仅是一个for循环.. :) - Brendan Long
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接