C#中大型IEnumerable<T>双层遍历的性能优化问询

核心问题分析 #

你需要实现的双层遍历逻辑，核心是外层遍历每个元素时，内层从当前位置开始遍历剩余元素，同时要避免两种低效方案：

• 直接转ToArray()：额外增加一次O(n)的完整遍历，总操作数为O(n + n²/2)
• 用Skip(counter)：每次Skip都会从头迭代到目标位置，总操作数升至O(n²)

以下是两种高效的实现方案：

方案1：按需缓存的集合（推荐） #

通过一个List缓存已遍历的元素，外层遍历边读边缓存，内层直接从当前索引开始遍历缓存，同时按需加载剩余元素。既避免了提前全量转数组，也不会重复迭代。

var cache = new List<T>();
var enumerator = MyEnumerable.GetEnumerator();
int outerIndex = 0;

try
{
    while (true)
    {
        // 确保缓存包含当前外层索引的元素
        while (outerIndex >= cache.Count && enumerator.MoveNext())
        {
            cache.Add(enumerator.Current);
        }
        if (outerIndex >= cache.Count) break; // 遍历结束

        var currentElem = cache[outerIndex];
        // 内层遍历：从当前索引开始，按需加载剩余元素
        int innerIndex = outerIndex;
        while (true)
        {
            while (innerIndex >= cache.Count && enumerator.MoveNext())
            {
                cache.Add(enumerator.Current);
            }
            if (innerIndex >= cache.Count) break;
            
            Check(cache[innerIndex]);
            innerIndex++;
        }

        DoStuff(currentElem);
        outerIndex++;
    }
}
finally
{
    enumerator.Dispose();
}

性能说明 #

总操作数为O(n + n²/2)，和转数组方案一致，但如果遍历过程中提前终止（比如DoStuff触发break），不会加载全部元素，内存占用更优。

方案2：自定义可克隆迭代器 #

如果需要更灵活的迭代状态控制，可以实现支持克隆的迭代器，外层遍历到某个位置时，克隆当前迭代器作为内层遍历的起点。

public class ClonableEnumerable<T> : IEnumerable<T>
{
    private readonly IEnumerable<T> _source;

    public ClonableEnumerable(IEnumerable<T> source)
    {
        _source = source ?? throw new ArgumentNullException(nameof(source));
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ClonableEnumerator<T>(_source.GetEnumerator());
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    private class ClonableEnumerator<T> : IEnumerator<T>
    {
        private readonly IEnumerator<T> _original;
        private List<T> _cache;
        private int _position;

        public ClonableEnumerator(IEnumerator<T> original)
        {
            _original = original;
            _cache = new List<T>();
            _position = -1;
        }

        // 克隆当前迭代状态
        public ClonableEnumerator<T> Clone()
        {
            return new ClonableEnumerator<T>(_original)
            {
                _cache = new List<T>(_cache),
                _position = _position
            };
        }

        public T Current => _position >= 0 && _position < _cache.Count 
            ? _cache[_position] 
            : _original.Current;

        object IEnumerator.Current => Current;

        public bool MoveNext()
        {
            _position++;
            if (_position < _cache.Count) return true;
            
            if (_original.MoveNext())
            {
                _cache.Add(_original.Current);
                return true;
            }
            return false;
        }

        public void Reset()
        {
            _position = -1;
            _original.Reset();
            _cache.Clear();
        }

        public void Dispose() => _original.Dispose();
    }
}

使用方式 #

var clonable = new ClonableEnumerable<T>(MyEnumerable);
using var outerEnumerator = clonable.GetEnumerator();

while (outerEnumerator.MoveNext())
{
    var currentElem = outerEnumerator.Current;
    // 克隆当前迭代器作为内层遍历起点
    using var innerEnumerator = outerEnumerator.Clone();
    
    while (innerEnumerator.MoveNext())
    {
        Check(innerEnumerator.Current);
    }
    
    DoStuff(currentElem);
}

性能说明 #

同样保持O(n + n²/2)的总操作数，适合需要多次分叉迭代器的复杂场景。

为什么不推荐Skip方案？ #

Skip(k)内部会从头迭代到第k个元素，外层循环执行n次时，总迭代次数为1+2+...+n = O(n²)，对于大型集合来说性能损耗极大，完全不可取。

内容的提问来源于stack exchange，提问作者Hadron