List<；T>；使用AddRange()时增加

本文关键字：AddRange 增加 gt lt List 使用 | 更新日期: 2023-09-27 18:29:50

我正在循环浏览一个潜在的巨大（数百万项）数据集（存储在磁盘上），并提取出我要添加到List<T>中的选定项。当我把一个项目添加到列表中时，我会在它周围加一个锁，因为还有其他线程访问该列表。

我正试图在两种可能的实现之间做出决定：

1） 每次我需要添加项目时锁定列表。

2） 使用一个临时列表，在找到项目时将其添加到其中，然后使用List<T>.AddRange()将该列表中的项目添加到一个区块中（例如，当我找到1000个匹配项时）。这导致需要较少地请求锁定列表，但如果AddRange（）只增加了足够的容量来准确地容纳新项目，那么列表最终将被多次重新调整大小。

我的问题是：据我所知，一次添加一个项目会导致每次达到容量时List<T>的内部容量翻一番，但我不知道List<T>.AddRange()的行为如何。我认为它只增加了足够的容量来容纳新的物品，但我找不到任何方法来证实这一点。对于Add（）和AddRange（），MSDN上关于如何增加容量的描述几乎相同，只是对于AddRange，它说如果新计数大于容量，则容量会增加，而不是如果计数已经与容量相同
对我来说，这读起来就像使用AddRange（）添加足够的项目以超过当前容量会导致容量增加，就像使用add（）超过当前容量一样。

那么，在一个大到足以超过当前容量的块中添加使用List<T>.AddRange()的项目会导致容量增加到仅足以容纳新项目，还是会导致容量翻倍？还是它做了一些我甚至没有考虑过的其他事情？

希望这在没有任何代码示例的情况下足够清楚，因为这是一个关于List<T>如何实现的一般问题，但如果没有，我将添加任何可以使我的问题更清楚的内容。如前所述，我已经阅读了MSDN文档，但找不到明确的答案。我在这里也搜索了类似的问题，但没有找到，但如果有我错过的，请给我指一下！

List<；T>；使用AddRange()时增加

只要作为AddRange参数传递的集合实现ICollection<T>，数组大小就会增加一次：

ICollection<T> collection2 = collection as ICollection<T>;
if (collection2 != null)
{
    int count = collection2.Count;
    if (count > 0)
    {
        this.EnsureCapacity(this._size + count);
    // (...)

否则，每个元素的标准枚举和Insert方法调用完成：

}
else
{
    using (IEnumerator<T> enumerator = collection.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            this.Insert(index++, enumerator.Current);
        }
    }
}

编辑

EnsureCapacity方法探讨：

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

它将数组大小增加了Max(old_size * 2, min)，因为它是用min = old_size + count调用的，所以AddRange调用后的最终数组大小将设置为Max(old_size * 2, old_size + count)——它将注意当前List<T>的大小和使用AddRange方法添加的集合的大小。

容量的增加方式与Add相同。文档中没有明确提到这一点，但查看源代码可以发现Add和AddRange内部都使用EnsureCapacity。

AddRange只会将大小增加到必要的数量。因此，在AddRange函数中，您可以找到类似以下代码的内容： 

if(capacity < count + items.Count)
{
  capacity = count + items.Count;
}

编辑：原来这些项目可能是一个接一个添加的。

但是，如果您使用的是非常大的数据集，并且读取性能很重要，那么最好使用二进制树。这将允许更快的搜索、添加、删除和部分锁定，使树的其余部分可用。树的最大问题是何时重新平衡。我在我的国际象棋游戏中使用了这个树，它在每次移动后都会重新平衡（因为那是需要删除的时候，而这个实现不安全）：

namespace Chess
{
    /// <summary>
    /// Implements using a binary search tree.
    /// Is thread-safe when adding, not when removing.
    /// </summary>
    public class BinaryTree
    {
        public MiniMax.Node info;
        public BinaryTree left, right;
        /// <summary>
        /// Collisions are handled by returning the existing node. Thread-safe
        /// Does not recalculate height, do that after all positions are added.
        /// </summary>
        /// <param name="info">Connector in a tree structure</param>
        /// <returns>Node the position was already store in, null if new node.</returns>
        public MiniMax.Node AddConnection(MiniMax.Node chessNode)
        {
            if (this.info == null)
            {
                lock (this)
                {
                    // Must check again, in case it was changed before lock.
                    if (this.info == null)
                    {
                        this.left = new BinaryTree();
                        this.right = new BinaryTree();
                        this.info = chessNode;
                        return null;
                    }
                }
            }
            int difference = this.info.position.CompareTo(chessNode.position);
            if (difference < 0) return this.left.AddConnection(chessNode);
            else if (difference > 0) return this.right.AddConnection(chessNode);
            else
            {
                this.info.IncreaseReferenceCount();
                return this.info;
            }
        }
        /// <summary>
        /// Construct a new Binary search tree from an array.
        /// </summary>
        /// <param name="elements">Array of elements, inorder.</param>
        /// <param name="min">First element of this branch.</param>
        /// <param name="max">Last element of this branch.</param>
        public void CreateFromArray(MiniMax.Node[] elements, int min, int max)
        {
            if (max >= min)
            {
                int mid = (min + max) >> 1;
                this.info = elements[mid];
                this.left = new BinaryTree();
                this.right = new BinaryTree();
                // The left and right each have one half of the array, exept the mid.
                this.left.CreateFromArray(elements, min, mid - 1);
                this.right.CreateFromArray(elements, mid + 1, max);
            }
        }
        public void CollectUnmarked(MiniMax.Node[] restructure, ref int index)
        {
            if (this.info != null)
            {
                this.left.CollectUnmarked(restructure, ref index);
                // Nodes marked for removal will not be added to the array.
                if (!this.info.Marked)
                    restructure[index++] = this.info;
                this.right.CollectUnmarked(restructure, ref index);
            }
        }
        public int Unmark()
        {
            if (this.info != null)
            {
                this.info.Marked = false;
                return this.left.Unmark() + this.right.Unmark() + 1;
            }
            else return 0;
        }
    }
}
相关文章：