如何在不创建副本且不分配内存的情况下将 IList<T> 分割为 N 大小的段？

Question

我有一个非常大的集合，它实现了通用 IList<T> 接口并包含数千万个元素，我想使用 PLINQ 并行处理它们。我注意到并行的开销非常大，因为处理每个单独的元素都非常轻量级，所以我正在寻找通过将 IList<T> 分成小段来分块处理的方法。我的目标是最终拥有这样的东西：

IList<Person> source = GetAllPersons();

double averageAge = source
    .Segmentate(1000) // Hypothetical operator that segmentates the source
    .AsParallel()
    .Select(segment => segment.Select(person => (double)person.CalculateAge()).Sum())
    .Sum() / source.Count;

我可以使用 MoreLinq library, or any of the answers from many related questions 中的 Batch 运算符，但所有这些解决方案都在分配多个小数组（或列表），并将源代码复制到这些容器中，我不想要那个。就我而言，我还有一个额外的要求，即尽可能让垃圾收集器保持空闲状态。

我注意到 .NET 有 ArraySegment 类型，这似乎完全符合我的要求：

// Delimits a section of a one-dimensional array.
public readonly struct ArraySegment<T> : ICollection<T>, IEnumerable<T>,
    IEnumerable, IList<T>, IReadOnlyCollection<T>, IReadOnlyList<T>

我可以使用这种类型来实现无分配 Segmentate 运算符，如下所示：

/// <summary>Segmentates the source array into sized segments.</summary>
public static IEnumerable<ArraySegment<T>> Segmentate<T>(this T[] source, int size)
{
    for (int offset = 0; offset < source.Length; offset += size)
    {
        yield return new ArraySegment<T>(source, offset,
            Math.Min(size, source.Length - offset));
    }
}

但是我不能使用这种类型，因为我的源是 IList<T> 而不是数组。将它复制到一个数组并不是一个真正的选择，因为源经常发生变化。并且一直创建新的数组副本是违反我的要求的。

所以我正在搜索 ListSegment<T> 类型，但据我所知，它在 .NET 中不存在。我必须自己实施吗？如果是这样，怎么办？或者有没有其他方法可以在不引起分配的情况下分割 IList<T>？

澄清：我的源集合是不是 List<T>。它是实现 IList<T> 接口的自定义 class。

Answer 1

此答案假定您的具体 IList 类型为 List。您可以使用 GetRange function，它几乎可以满足您的需求：

A shallow copy of a collection of reference types, or a subset of that collection, contains only the references to the elements of the collection. The objects themselves are not copied. The references in the new list point to the same objects as the references in the original list.

即使ArraySegment<T>也会创建某种引用对象来存储数组段，所以你不能完全避免。

如果您想避免存储引用（又名浅拷贝），那么 Span 是合适的，但是您关于您的集合更改的评论与 this

冲突

Items should not be added or removed from the List while the Span is in use.

因此，您唯一的其他解决方案就是按照您提到的那样自己创建一个。

警告： 内置不存在这样的东西是有原因的。数组是固定大小的，所以获取一个段处理起来更安全。创建此类构造时，请注意意外后果和副作用。这就是 Span 警告您它不安全的原因。您只知道您的要求以及您的数据如何变化，因此您的集合包装器应该考虑到它们并相应地处理它们。

Answer 2

您需要为 IList<T> 实现一个 ArraySegment<T> 等价物。请参阅下面的实现。为获得最佳性能，请考虑改用 spans。

ListSegment 结构

public readonly struct ListSegment<T> : IList<T>
{
    public List<T> Items { get; }
    public int Offset { get; }
    public int Count { get; }

    public ListSegment(List<T> items, int offset, int count)
    {
        Items = items ?? throw new ArgumentNullException(nameof(items));
        Offset = offset;
        Count = count;

        if (items.Count < offset + count)
        {
            throw new ArgumentException("List segment out of range.", nameof(count));
        }
    }

    public void CopyTo(T[] array, int index)
    {
        if (Count > 0)
        {
            Items.CopyTo(Offset, array, index, Count);
        }
    }

    public bool Contains(T item) => IndexOf(item) != -1;

    public int IndexOf(T item)
    {
        for (var i = Offset; i < Offset + Count; i++)
        {
            if (Items[i].Equals(item))
            {
                return i;
            }
        }

        return -1;
    }

    private T ElementAt(int index)
    {
        if (Count > 0)
        {
            return Items[Offset + index];
        }

        throw new ArgumentOutOfRangeException(nameof(index));
    }

    public ListSegmentEnumerator GetEnumerator() => new ListSegmentEnumerator(this);

    #region IEnumerable<T> interface
    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    #endregion

    #region ICollection<T> interface
    bool ICollection<T>.IsReadOnly => true;

    void ICollection<T>.Add(T item) => throw new NotImplementedException();
    bool ICollection<T>.Remove(T item) => throw new NotImplementedException();
    void ICollection<T>.Clear() => throw new NotImplementedException();
    #endregion

    #region IList<T> interface
    void IList<T>.Insert(int index, T item) => throw new NotImplementedException();
    void IList<T>.RemoveAt(int index) => throw new NotImplementedException();
    T IList<T>.this[int index]
    {
        get => ElementAt(index);
        set => throw new NotImplementedException();
    }
    #endregion

    public struct ListSegmentEnumerator : IEnumerator<T>
    {
        private readonly List<T> items;
        private readonly int start;
        private readonly int end;
        private int current;

        public ListSegmentEnumerator(ListSegment<T> segment)
        {
            items = segment.Items;
            start = segment.Offset;
            end = start + segment.Count;
            current = start - 1;
        }

        public bool MoveNext()
        {
            if (current < end)
            {
                current++;

                return current < end;
            }
            return false;
        }

        public T Current => items[current];
        object IEnumerator.Current => Current;

        void IEnumerator.Reset() => current = start - 1;
        void IDisposable.Dispose() { }
    }
}

如何在不创建副本且不分配内存的情况下将 IList<T> 分割为 N 大小的段？

How to segmentate an IList<T> to segments of N size, without creating copies and without memory allocations?

c#

linq

performance

batching

plinq

ListSegment 结构