3

List 是数组的包装器。当您将项目添加到列表中时，它会创建越来越大的隐藏数组（并且先前的数组被垃圾收集）。但是，如果您在某些时候处理大型列表，即使由于内存碎片而存在可用内存，您也会得到 OutOfMemoryException。我正在寻找一个 ICollection 实现，它可以与一组隐藏的数组一起使用，类似于MemoryTributary所做的。

更新。

我在这里找到了 BigArray 的实现：

http://blogs.msdn.com/b/joshwil/archive/2005/08/10/450202.aspx。

虽然它试图解决其他问题（创建一个 >2GB 大小的数组），但它也解决了我的问题。但是这个实现并不完整，甚至无法编译。所以如果我没有找到更好的，我会改进这个并使用它。

4

2 回答 2

1

如果您对最大大小有一个粗略的估计，则可以使用容量初始化列表。据我所知，这将避免发生大量垃圾收集（使用旧的较小数组），这也可能避免内存碎片。

于 2013-02-13T07:29:37.783 回答
0

我还没有找到任何好的实现。所以我写了我自己的 ChunkyList。通常 ChunkyList 是数组包装器列表。最初块的大小为 1，但每次需要扩展当前块时，它乘以 2（当它达到 MaxBlockSize 时，会创建下一个块）（行为类似于 List）。

这是一个通用的 ChunkyList：

public class ChunkyList<T> : IList<T>
{
    public ChunkyList()
    {
        MaxBlockSize = 65536;
    }

    public ChunkyList(int maxBlockSize)
    {
        MaxBlockSize = maxBlockSize;
    }

    private List<T[]> _blocks = new List<T[]>();

    public int Count { get; private set; }

    public int MaxBlockSize { get; private set; }

    public bool IsReadOnly
    {
        get { throw new NotImplementedException(); }
    }

    public IEnumerator<T> GetEnumerator()
    {
        var index = 0;
        foreach (var items in _blocks)
            foreach (var item in items)
            {
                yield return item;
                if (Count <= ++index)
                    break;
            }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void Add(T item)
    {
        var indexInsideBlock = GetIndexInsideBlock(Count);
        if (indexInsideBlock == 0)
            _blocks.Add(new T[1]);
        else
        {
            var lastBlockIndex = _blocks.Count - 1;
            var lastBlock = _blocks[lastBlockIndex];
            if(indexInsideBlock >= lastBlock.Length)
            {
                var newBlockSize = lastBlock.Length*2;
                if (newBlockSize >= MaxBlockSize)
                    newBlockSize = MaxBlockSize;

                _blocks[lastBlockIndex] = new T[newBlockSize];
                Array.Copy(lastBlock, _blocks[lastBlockIndex], lastBlock.Length);
            }
        }

        _blocks[GetBlockIndex(Count)][indexInsideBlock] = item;

        Count++;
    }

    public void AddRange(IEnumerable<T> items)
    {
        foreach (var item in items)
            Add(item);
    }

    public void Clear()
    {
        throw new NotImplementedException();
    }

    public bool Contains(T item)
    {
        throw new NotImplementedException();
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    public bool Remove(T item)
    {
        throw new NotImplementedException();
    }

    public int IndexOf(T item)
    {
        throw new NotImplementedException();
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException();
    }

    public void RemoveAt(int index)
    {
        throw new NotImplementedException();
    }

    public T this[int index]
    {
        get
        {
            if (index >= Count)
                throw new ArgumentOutOfRangeException("index");

            var blockIndex = GetBlockIndex(index);
            var block = _blocks[blockIndex];

            return block[GetIndexInsideBlock(index)];
        }
        set { throw new NotImplementedException(); }
    }

    private int GetBlockIndex(int index)
    {
        return index / MaxBlockSize;
    }

    private long GetIndexInsideBlock(int index)
    {
        return index % MaxBlockSize;
    }
}

以下是证明此实现有效的测试：

 [TestClass]
    public class ChunkyListTests
    {
        [TestMethod]
         public void GetEnumerator_NoItems()
         {
             var chunkyList = new ChunkyList<float>();

             var wasInsideForeach = false;
             foreach (var item in chunkyList)
                 wasInsideForeach = true;

             Assert.IsFalse(wasInsideForeach);
         }

        [TestMethod]
        public void GetEnumerator_MaxBlockSizeOfThreeWithThreeItems()
        {
            var chunkyList = new ChunkyList<float> (3) { 1, 2, 3 };

            var wasInsideForeach = false;
            var iteratedItems = new List<float>();
            foreach (var item in chunkyList)
            {
                wasInsideForeach = true;
                iteratedItems.Add(item);
            }

            Assert.IsTrue(wasInsideForeach);
            CollectionAssert.AreEqual(new List<float> { 1, 2, 3 }, iteratedItems);
        }

        [TestMethod]
        public void GetEnumerator_MaxBlockSizeOfTwoWithThreeItems()
        {
            var chunkyList = new ChunkyList<float>(2) {1,2,3};
            var wasInsideForeach = false;
            var iteratedItems = new List<float>();

            foreach (var item in chunkyList)
            {
                wasInsideForeach = true;
                iteratedItems.Add(item);
            }

            Assert.IsTrue(wasInsideForeach);
            CollectionAssert.AreEqual(new List<float>() { 1, 2, 3 }, iteratedItems);
            Assert.AreEqual(chunkyList.MaxBlockSize, 2);
        }
    }

PS 我只实现了我的代码中使用的那些 IList 方法。因此，欢迎您改进此实现。

于 2013-02-14T18:16:00.180 回答