c# - 当需要更多空间时，列表会在 C# 中加倍空间。在某些时候，将 1024 加倍到 2048 会变得效率降低吗？

Question

当数字较小时，数组列表的大小很快从 2 个内存地址增加到 4 个内存地址，但当它开始增加空间量时，空间量接近数组列表中允许的最大空间量(接近2MB 限制)。如果只是将数组的大小增加到某个时候所需大小的一小部分，那么更改在这些较大区域中分配的空间量是否会更有效？显然，现在将大小从 1mb 增加到 2mb 并不是什么大问题但是，如果你有 50,000 人每小时运行一些东西，这会使数组的大小增加一倍，我很好奇这是否足够好改变其工作方式的原因。更不用说减少不需要的内存空间(理论上)。

我的意思的一个小图形表示..ArrayList a 中有 4 个元素，这是它目前的最大大小

||||

现在让我们向数组列表添加另一个项目，即使我们只向数组添加一项，内部代码也会使数组的大小加倍。arraylist 现在变成 8 个元素大

||||||||

在这些大小级别上，我怀疑它有什么不同，但是当你每次分配 1mb 到 2mb 时，每次有人做一些事情，比如将一些文件添加到 arraylist 或大约 1.25mb 的东西时，有 .75mb 的未-需要分配的空间。

让您更多地了解 System.Collections.Generic 类当前在 c# 中运行的代码。它现在的工作方式是每次用户尝试向太小的数组添加内容时，它都会将数组列表(读取数组)的大小加倍。将大小加倍是一个很好的解决方案并且很有意义，直到您实质上将其增长到远远超过技术上需要的规模。

这是该类(class)特定部分的来源:

private void EnsureCapacity(int min)
{
  if (this._items.Length >= min)
    return;
                                          // This is what I'm refering to
  int num = this._items.Length == 0 ? 4 : this._items.Length * 2;  
  if ((uint) num > 2146435071U)
    num = 2146435071;
  if (num < min)
    num = min;
  this.Capacity = num;
}

我猜想很多编程语言都是这样处理内存管理的，所以之前可能已经考虑过很多次了，只是想知道这是不是一种可以大量节省系统资源的效率节省器大规模。

Answer 1

随着集合的大小变大，创建新缓冲区的成本也会增加，因为您需要复制所有现有元素。需要完成的这些副本的数量与每个副本的费用成正比的事实正是将项目添加到 List 的摊销成本为 O 的原因(1).如果缓冲区的大小线性增加，则将项目添加到 List 的摊销成本实际上变为 O(n)。

您节省了内存，允许“浪费”的内存从 O(n) 变为 O(1)。与几乎所有性能/算法决策一样，我们再次面临以内存换取速度的典型决策。我们可以节省内存并降低添加速度(因为复制更多)，或者我们可以使用更多内存来加快添加速度。当然没有一个普遍正确的答案。有些人确实更愿意以较慢的添加速度来换取较少的内存浪​​费。将首先耗尽的特定资源将根据程序、运行它的系统等而有所不同。那些在内存是稀缺资源的情况下的人可能无法使用List，它被设计为尽可能广泛适用，即使它不能普遍 最好的选择。