当列表需要更多空间时，它们在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).如果仅在某个时候将阵列的大小增加所需大小的一小部分，更改在较大区域分配的空间会更有效吗?显然，现在将大小从1mb增加到2mb并不是什么大问题，但是，如果您每小时有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

||||||||

在这样的大小级别上，我怀疑这是否会有所不同，但是当您每次有人将1mb分配到2mb时，比如将一些文件添加到arraylist中或大约1.25mb时，就会有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屋！