为什么Enumerable.Single()会迭代所有元素,即使已找到多个项目？

Question

在分析我们的一个应用程序时,我们在一些代码中发现了一个神秘的减速,我们正在调用Enumerable.Single(source, predicate)一个大型集合,它有多个项目与集合开头附近的谓词相匹配.

调查显示,执行情况Enumerable.Single()如下:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) 
{
        TSource result = default(TSource);
        long count = 0;
        // Note how this always iterates through ALL the elements:
        foreach (TSource element in source) { 
            if (predicate(element)) {
                result = element;
                checked { count++; }
            }
        }
        switch (count) {
            case 0: throw Error.NoMatch();
            case 1: return result;
        }
        throw Error.MoreThanOneMatch();
    }

该实现将遍历序列的每个元素,即使多个元素已经与谓词匹配.

以下实现似乎会产生相同的结果:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    TSource result = default(TSource);
    long count = 0;
    foreach (TSource element in source) {
        if (predicate(element)) {
            if (count == 1) // Exit loop immediately if more than one match found.
                throw Error.MoreThanOneMatch();

            result = element;
            count++; // "checked" is no longer needed.
        }
    }

    if (count == 0)
        throw Error.NoMatch();

    return result;
}

有谁知道为什么实际的实现不使用这种明显的优化？有什么我想念的吗？(我无法想象这样一个明显的优化会被忽视,因此必须有一些具体的理由.)

(注意:我意识到这个问题可能会吸引那些意见的答案;我希望得到答案,提供迭代所有元素的具体理由.如果答案实际上是"因为设计师不认为这样的优化是必要的",那么这个问题是无法回答的,我想我应该删除它...)

---

为了进行比较,请查看Single()其中没有谓词的实现:

public static TSource Single<TSource>(this IEnumerable<TSource> source) 
{
    IList<TSource> list = source as IList<TSource>;
    if (list != null) {
        switch (list.Count) {
            case 0: throw Error.NoElements();
            case 1: return list[0];
        }
    }
    else {
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            if (!e.MoveNext()) throw Error.NoElements();
            TSource result = e.Current;
            if (!e.MoveNext()) return result;
        }
    }
    throw Error.MoreThanOneElement();
}

在这种情况下,他们已经努力为其添加优化IList.

Answer 1

你似乎并不是唯一一个这样想的人.在.NET核心实现有一个优化的版本:

using (IEnumerator<TSource> e = source.GetEnumerator())
{
    while (e.MoveNext())
    {
        TSource result = e.Current;
        if (predicate(result))
        {
            while (e.MoveNext())
            {
                if (predicate(e.Current))
                {
                    throw Error.MoreThanOneMatch();
                }
            }

            return result;
        }
    }
}

所以回答你的问题:除了不考虑优化这个用例的开发人员之外,似乎没有"好"的理由.

Answer 2

优化应用于.NET Core

现在的代码是:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (predicate == null)
    {
        throw Error.ArgumentNull(nameof(predicate));
    }

    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        while (e.MoveNext())
        {
            TSource result = e.Current;
            if (predicate(result))
            {
                while (e.MoveNext())
                {
                    if (predicate(e.Current))
                    {
                        throw Error.MoreThanOneMatch();
                    }
                }

                return result;
            }
        }
    }

    throw Error.NoMatch();
}

只要有可能,代码甚至会检查目标是否是一个,IList<T>这样可以避免迭代:

public static TSource Single<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (source is IList<TSource> list)
    {
        switch (list.Count)
        {
            case 0:
                throw Error.NoElements();
            case 1:
                return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> e = source.GetEnumerator())
        {
            if (!e.MoveNext())
            {
                throw Error.NoElements();
            }

            TSource result = e.Current;
            if (!e.MoveNext())
            {
                return result;
            }
        }
    }

    throw Error.MoreThanOneElement();
}

UPDATE

检查git blame输出显示迭代优化已在2016年应用!

该IList<>优化加入1年前,大概为核心的2.1最优化的一部分

Answer 3

正如其他答案所指出的那样,已经应用了优化,但我想提出一个假设,即他们原来是这样想的,因为他们无法保证谓词函数没有边效果.

我不确定是否真的会出现这种行为会被使用/有用的情况,但需要牢记这一点.