当列表在c#中需要更多空间时，它们的空间会翻倍.在某种程度上，如果将1024加倍到2048，效率会降低吗?

本文关键字：空间 1024 如果 在某种程度上 2048 效率 列表 | 更新日期: 2023-09-27 18:13:47

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

一个小的图形表示我的意思…数组列表a中有4个元素这是它目前的最大大小

||||

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

||||||||

在这些大小级别，我怀疑它有什么区别，但是当你分配1mb到2mb时，每次有人做一些事情，比如向数组列表中添加一些文件或1.25mb左右的东西，有0.75 mb的不需要的空间分配。

让你对System.Collections.Generic类当前在c#中运行的代码有更多的了解。它现在的工作方式是，每当用户试图向太小的数组添加内容时，它就会将数组列表(读取数组)的大小加倍。将规模扩大一倍是一个很好的解决方案，而且是有意义的，除非你的规模远远超过了技术上的需要。

下面是该类特定部分的源代码:

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;
}

我猜这就是许多编程语言中处理内存管理的方式，所以这可能已经被考虑过很多次了，只是想知道这是否是一种效率节省器，可以大规模地节省系统资源。

当列表在c#中需要更多空间时，它们的空间会翻倍.在某种程度上，如果将1024加倍到2048，效率会降低吗?

随着集合的大小越来越大，创建新缓冲区的成本也越来越大，因为您需要复制所有现有的元素。需要完成的这些复制的数量与每次复制的费用间接成正比，这正是为什么向List添加项目的平摊成本为O(1)的原因。如果缓冲区的大小线性增加，那么向List添加项目的平摊成本实际上变成了O(n)。

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

动态数组(如List<T>)的指数增长因子背后的思想是:

  1. 浪费的空间量总是仅仅与数组中的数据量成正比。因此，你永远不会浪费超过你正确使用的资源。

  2. 即使进行了多次重新分配，在创建大小为N的数组时所花费的总潜在复制时间为O(N)，对于单个元素则为O(1)。

  3. 访问时间在0(1)处非常快，且系数很小。

这使得List<T>非常适合于数组，例如，数据库对象引用的内存表，这种数组需要几乎即时访问，但数组元素本身很小。

相反，动态数组的线性增长会导致n平方内存浪费。这种情况发生在以下情况:

  1. 你向数组中添加一些东西，将其扩展到N大小的大N，释放先前大小为N- k的内存块(可能相当大)对于小k。

  2. 分配一些对象。内存管理器将一些内存放入刚刚腾出的大内存块中，为什么不呢?

  3. 您向数组中添加其他内容，将其扩展到N+K的大小，因为之前释放的内存块现在被稀疏占用，内存管理器没有足够大的连续空闲内存块，必须从操作系统请求更多的虚拟内存。

  4. 因此，尽管所创建对象的测量大小呈线性增长，但所提交的虚拟内存却呈二次增长。

这不是理论上的可能性。实际上，我必须修复一个n平方的内存泄漏，因为有人手动编写了一个线性增长的动态整数数组。解决方法是抛弃手工代码，使用为此目的创建的几何增长数组库。

话虽如此，我也看到了在32位进程中List<T>(以及Dictionary<TKey,TValue>中类似增长的内存缓冲区)的指数重新分配的问题，当所需的总内存需要增长超过128 MB时。在这种情况下，列表或字典将经常无法分配256 MB 连续范围的内存，即使有足够多的虚拟地址空间。然后，应用程序将向用户报告内存不足错误。在我的例子中，客户抱怨这一点，因为任务管理器报告VM使用从未超过1.5GB。如果我是Microsoft，我会将'List'(以及Dictionary中类似的内存缓冲区)的增长限制为总虚拟地址空间的1%。

相关文章：