2

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

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

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

2) 使用一个临时列表，当我找到它们时将其添加到其中，然后用于List<T>.AddRange()将该列表中的项目添加到一个块中（例如，当我找到 1000 个匹配项时）。这导致需要在列表上请求锁定的频率降低，但如果 AddRange() 仅增加足够的容量以完全容纳新项目，那么列表最终将被重新调整大小更多次。

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

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

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

4

3 回答 3

7

只要作为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方法添加的集合的大小。

于 2013-09-02T12:21:19.683 回答
3

容量的增加方式与 相同Add。这在文档中没有明确提及，但查看源代码表明两者都在Add内部AddRange使用EnsureCapacity.

于 2013-09-02T12:23:54.383 回答
0

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;
        }
    }
}
于 2013-09-02T12:33:00.337 回答