当需要更多空间时，将列表在 c# 中的空间加倍.在某些时候，将 1024 倍增至 2048 会变得效率低下吗? [英] Lists double their space in c# when they need more room. At some point does it become less efficient to double say 1024 to 2048?

问题描述

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

When numbers are smaller, it's quick to grow the size of an array list from 2 to 4 memory addresses but when it starts to increase the amount of space closer to the max amount of space allowed in an array list (close to the 2MB limit). Would changing how much space is allotted in those bigger areas be more efficient if it was only growing the size of the array by a fraction of the size it needs at some point? Obviously growing the size from 1mb to 2mb isn't really a big deal now-days HOWEVER, if you had 50,000 people running something per hour that did this doubling the size of an array, I'm curious if that would be a good enough reason to alter how this works. Not to mention cut down on un-needed memory space (in theory).

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

A small graphical representation of what I mean.. ArrayList a has 4 elements in it and that is it's current max size at the moment

||||

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

Now lets add another item to the arraylist, the internal code will double the size of the array even though we're only adding one thing to the array. The arraylist now becomes 8 elements large

||||||||

在这些大小级别，我怀疑这有什么不同，但是当您每次有人执行诸如将一些文件添加到数组列表或大约 1.25mb 的事情时分配 1mb 到 2mb 时，就会有 0.75mb 的未-需要分配的空间.

At these size levels, I doubt it makes any difference but when you're allocating 1mb up to 2mb everytime someone is doing something like adding some file into an arraylist or something that is around 1.25mb, there's .75mb of un-needed space allocated.

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

To give you more of an idea of the code that is currently ran in c# by the System.Collections.Generic class. The way it works now is it doubles the size of an array list (read array), every time a user tries to add something to an array that is too small. Doubling the size is a good solution and makes sense, until you're essentially growing it far bigger than you technically need it to be.

这是该课程特定部分的来源:

Here's the source for this particular part of the 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;
}

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

I'm going to guess that this is how memory management is handled in many programming languages so this has probably been considered many times before, just wondering if this is a kind of efficiency saver that could save system resources by a large amount on a massive scale.

推荐答案

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

As the size of the collection gets larger, so does the cost of creating a new buffer as you need to copy over all of the existing elements. The fact that the number of these copies that need to be done is indirectly proportional to the expense of each copy is exactly why the amortized cost of adding items to a List is O(1). If the size of the buffer increases linearly, then the amortized cost of adding an item to a List actually becomes O(n).

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

You save on memory, allowing the "wasted" memory to go from being O(n) to being O(1). As with virtually all performance/algorithm decisions, we're once again faced with the quintessential decision of exchanging memory for speed. We can save on memory and have slower adding speeds (because of more copying) or we can use more memory to get faster additions. Of course there is no one universally right answer. Some people really would prefer to have a slower addition speed in exchange for less wasted memory. The particular resource that is going to run out first is going to vary based on the program, the system that it's running on, and so forth. Those people in the situation where the memory is the scarcer resource may not be able to use List, which is designed to be as wildly applicable as possible, even though it can't be universally the best option.

这篇关于当需要更多空间时，将列表在 c# 中的空间加倍.在某些时候，将 1024 倍增至 2048 会变得效率低下吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！