代码之家 › 专栏 › 技术社区 › rick schott

列表<T>和ArrayList默认容量

memory-management algorithm performance .net c#

rick schott · 技术社区 · 15 年前

我一直在看.NET的列表和 ArrayList 使用实现 Reflector

当看着 添加(T项) 我偶然发现了这个。

public void Add(T item)
{
    if (this._size == this._items.Length)
    {
       this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size++] = item;
    this._version++;
}

因此,Recapacity看起来是这样的:

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

4 回复 | 直到 15 年前

jason 15 年前

关于在需要调整大小时加倍,原因如下。假设您要插入 n 将项目放入 List . 我们将调整列表的大小不超过 log n 时代。因此,插入 N 将项目放入 列表 O(n) 时间,所以插入是恒定的 amortized time . 此外,浪费的空间量的上限为 . 任何恒定比例增长的策略都会导致恒定的摊销插入时间和线性浪费空间。增长速度超过恒定比例增长可能会导致更快的插入,但会以浪费更多空间为代价。增长速度慢于恒定比例增长可能会减少空间浪费,但代价是插入速度较慢。

默认容量是这样的,这样就不会浪费太多内存(从时间/空间的角度来看,双倍调整大小的策略是好的,我们刚刚看到了这一点,所以从小容量开始并没有坏处)。

chris.w.mclean 15 年前

4是一个很好的默认值,因为大多数集合中只有少数项。递增是为了确保不会在每次添加项时进行内存分配。

请参阅Joel撰写的这篇关于内存使用以及为什么将所需资源分配两倍是个好主意的好文章。

http://www.joelonsoftware.com/printerFriendly/articles/fog0000000319.html

以下是相关报价:

假设您编写了一个智能strcat函数,自动重新分配目标缓冲区。它是否应该总是将其重新分配到所需的确切大小?我的老师兼导师斯坦·艾森斯塔(Stan Eisenstat)建议,当您调用realloc时,您应该始终将先前分配的内存大小增加一倍。这意味着您永远不必调用realloc超过lgn次,即使对于巨大的字符串,它也具有良好的性能特征,并且您永远不会浪费超过50%的内存。

另一方面,该列表<&燃气轮机;和字典<&燃气轮机;现在默认为10,但我敢打赌它们有相同的递增逻辑。

ChaosPandion 15 年前

我打赌这是为了让您可以创建小列表而无需多次分配。将大小加倍是为了简单,而不是使用复杂的缩放算法。

Robert Harvey 15 年前

似乎4是一个合理的折衷方案,它足够大,可以容纳经常出现的拥有4件或更少物品的场景,并且没有太多的浪费物品。

每增加一次分配,容量就会翻倍,从而确保它可以容纳两倍于容器中已存在的项目数量。这是一个类似于C++的向量容器的算法。