Enumerable.Single的实现有问题吗？

Question

Enumerable.Single的实现有问题吗？

33

我在反射器的Enumerable.cs文件中发现了这个实现。

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    //check parameters
    TSource local = default(TSource);
    long num = 0L;
    foreach (TSource local2 in source)
    {
        if (predicate(local2))
        {
            local = local2;
            num += 1L;
            //I think they should do something here like:
            //if (num >= 2L) throw Error.MoreThanOneMatch();
            //no necessary to continue
        }
    }
    //return different results by num's value
}

我认为如果有超过2个项目符合条件，他们应该打破循环，为什么他们总是遍历整个集合？以防反射器错误地拆解dll，我写了一个简单的测试：

class DataItem
{
   private int _num;
   public DataItem(int num)
   {
      _num = num;
   }
    
   public int Num
   {
      get{ Console.WriteLine("getting "+_num); return _num;}
   }
} 
var source = Enumerable.Range(1,10).Select( x => new DataItem(x));
var result = source.Single(x => x.Num < 5);

对于这个测试用例，我认为它会打印"getting 0, getting 1"然后抛出一个异常。但事实是，它保持着"getting 0... getting 10"并抛出了一个异常。他们为什么要以这种方式实现这个方法，是否有算法上的原因？

编辑：有些人认为这是由于谓词表达式的副作用，经过深思熟虑和一些测试用例，我得出结论，在这种情况下副作用并不重要。如果你不同意这个结论，请提供一个例子。

12年后，现在是2023年，我发现最新的.NET已经将实现方式改正了 :) https://github.com/dotnet/runtime/blob/main/src/libraries/System.Linq/src/System/Linq/Single.cs

- Cheng Chen

7

疯先生浏览了这个问题并给所有答案点了踩... - Cheng Chen

2

Enumerable.cs是System.Linq的一部分，它位于BCL的System.Core.dll中。这个库是根据宽松许可证发布的还是专有的？我相信（但不确定）它是专有的。请不要发布专有代码 - 阅读此内容的人无法为像Mono这样的项目做出贡献。 - Michael Shimmins

@Michael：将这段代码与问题一起发布不被认为是用于审核目的吗？因此，根据许可证它是合法的吗？但是，该代码未被复制并在软件中使用。我非常怀疑这是否是一个法律问题。如果真是这样，整个SO可能都会崩溃 :) - Peter Lillevold

1

@Michael：这不是基于MS-RSL许可证，而是基于二进制文件。即使它是基于MS-RSL许可证，也是无关紧要的：无论它有什么条款都是授权人的合同条款，而不是像Mono这样的第三方——他们甚至没有任何许可证，最有可能的情况是。考虑到范围、改写和选择以及微小的范围，很难说这是相关的。我严重怀疑Mono和Microsoft会因为一个明显、琐碎且非常简短的算法的非专利实现而在法庭上面对彼此，所以我们不要过分激动…… - Eamon Nerbonne

我甚至不确定这是否是专有的:) @Peter - 是的，我认为查看它作为参考没有任何问题，但是Mono的贡献者不允许查看它，因为很难不让它影响你在Mono中的实现。没有什么错的非贡献者看它（我想），只是建议人们不要在这里发布它，以便贡献者能够帮助他们。这不是一个很大的问题。(我不是律师，不知道这些是否正确)。 - Michael Shimmins

显示剩余14条评论

7个回答

7

更新：
我收到了一些非常好的反馈，让我重新思考了。因此，我将首先提供陈述我的“新”观点的答案；您仍然可以在下面找到我的原始答案。确保阅读之间的评论以了解我的第一个答案错过了什么。

新答案：

假设当Single检测到集合中没有或多个项目与谓词匹配时，应该抛出异常。

Single只有在遍历整个集合时才能成功而不抛出异常。它必须确保恰好有一个匹配项，因此必须检查集合中的所有项。

这意味着尽早抛出异常（即在找到第二个匹配项时立即抛出异常）实际上是一种优化，只有在Single的前提条件无法满足且它将抛出异常时才能从中受益。

正如用户CodeInChaos在下面的评论中清楚地指出的那样，这种优化并不是错误的，但是它是无意义的，因为通常会引入将使正确工作的代码受益的优化，而不是使故障代码受益的优化。

因此，实际上Single可以尽早抛出异常；但是它不必这样做，因为几乎没有额外的好处。

旧答案：

我无法给出技术原因为什么该方法以其当前方式实现，因为我没有实现它。但是，我可以说明我的理解Single运算符的目的，并从那里得出我的个人结论，即它确实实现得很糟糕：

我对`Single`的理解：

Single的目的是什么，与例如First或Last有何不同？

使用Single运算符基本上表达了一个人的假设，即集合必须返回恰好一个项：

如果不指定谓词，则应意味着集合应包含恰好一个项。
如果指定谓词，则应意味着集合中恰好有一个项目满足该条件。（使用谓词应具有与items.Where(predicate).Single()相同的效果。）

这就是使Single与其他运算符（如First、Last或Take(1)）不同的原因。这些运算符都没有要求应该有恰好一个（匹配的）项。

Single何时应抛出异常？

基本上，当它发现你的假设是错误的时候; 也就是说，当底层集合没有产生恰好一个（匹配的）项时。也就是说，当有零个或多个项时。

何时应该使用Single？

当您的程序逻辑可以保证集合只产生一个项时，使用Single是合适的。如果抛出异常，则应该意味着您的程序逻辑包含错误。

如果您处理“不可靠”的集合，例如I/O输入，您应该在将其传递给Single之前先验证输入。 Single与异常catch块一起，不适用于确保集合只有一个匹配项。在调用Single之前，您应该已经确保只有一个匹配项。

结论：

以上是我对Single LINQ运算符的理解。如果您遵循并同意这种理解，您应该得出这样的结论：Single应该尽早抛出异常。没有理由等到（可能非常大的）集合结束，因为只要检测到集合中有第二个（匹配的）项，Single的前提条件就被违反了。

- stakx - no longer contributing

2

但是，由于抛出异常的情况是您的程序存在错误的情况，因此在这种情况下的性能并不重要。 - CodesInChaos

@Peter Lillevold: 在我看来，执行速度在这里并不像履行正确的合同那样重要。特别是因为我们很可能在谈论微观优化（在内部循环中添加一个if，而且if可以简单地检查布尔变量是否具有值false或true；这可以通过一个CIL操作码完成：brfalse也称为brzero）。 - stakx - no longer contributing

3

@stakx 我并不反对那种优化。我只是在说实际上它是无关紧要的。而且在你的无限序列中，即使没有异常情况，Single 也不会终止。这是无法被优化掉的。 - CodesInChaos

@Peter 关于额外检查的性能影响：这不是内部循环中的额外 if。这是一个代码块中的额外 if，最多只会执行两次。因此，性能影响为 O(1) 及非常小。 - CodesInChaos

2

@Artur: 我的意思不是这样的。提前退出当然是可能的：确实，它不能在找到一个匹配项后停止，但是当它找到第二个匹配项时，它肯定可以停止。例如，如果您有100个项目的序列，并且第1个和第6个项目都匹配，则您可以在第6个项目后停止而不是迭代剩余的94个项目。但是我现在会采取CodeInChaos'和PeterLillevold的立场，即提前退出只有在错误情况下才有益于优化。 - stakx - no longer contributing

显示剩余10条评论

4

考虑到这个实现，我们必须记住这是BCL：一般的代码，应该在各种情况下都能够工作得足够好。首先，看看这些场景：

迭代10个数字，其中第一个和第二个元素相等
迭代100万个数字，其中第一个和第三个元素相等

原始算法对于10个项目来说已经足够好了，但是100万个项目将会浪费大量的周期。因此，在这些情况下，我们知道序列中有两个或更多早期出现的元素时，所提出的优化将会产生良好的效果。 接着，看看这些场景：

迭代10个数字，其中第一个和最后一个元素相等
迭代100万个数字，其中第一个和最后一个元素相等

在这些情况下，算法仍需要检查列表中的每个项目。没有捷径。原始算法将表现良好，足以满足合同。改变算法，在每次迭代中引入一个“if”实际上会降低性能。对于10个项目来说，这将是微不足道的，但对于100万个项目来说，这将是一个巨大的打击。

我认为，原始实现是正确的，因为它对于大多数情况来说已经足够好了。了解Single的实现很好，因为它使我们能够根据我们所知道的关于使用它的序列做出明智的决策。如果在一个特定的场景中性能测量显示Single正在导致瓶颈，那么我们可以实现自己的变体，在那个特定的场景中工作得更好。 更新：正如CodeInChaos和Eamon正确指出的那样，优化中引入的if测试确实没有对每个项执行，只在谓词匹配块内执行。在我的示例中，我完全忽视了所提出的更改不会影响实现整体性能的事实。

我同意引入优化可能会使所有场景受益。不过，很高兴看到最终决定是否实施优化是基于性能测量结果的。

- Peter Lillevold

@Eamon：非常有趣。也许是因为后者没有执行1亿个增量操作...再次强调，在每种特定情况下进行性能测量才能确定是否需要进行优化 :) - Peter Lillevold

@Peter，你没有给我点踩，但是让我给你点赞。（顺便说一句，我改变了我的答案。也许现在你会同意它？） - stakx - no longer contributing

虽然已经指出 if 只会在谓词匹配块中发生，但我也想指出，if 可能比当前的 n++ 更快。 - Timwi

无需测试找到的数字，而是保留有缺陷实现的“num”，只要在“MoveNext()”返回true时进入新循环，并在匹配时抛出异常。 - Jon Hanna

if 语句只需要在 num 被更改的迭代中执行。由于它最多只会在函数不应抛出异常的情况下执行一次，在所有需要执行两次以上的情况下都是有益的，我无法想象任何实际情况下它会造成任何可测量的减速。 - supercat

显示剩余5条评论

3

我认为这是一种过早优化的“缺陷”。

由于副作用，这种行为是不合理的

有些人认为由于副作用，应该预期整个列表被评估。毕竟，在正确的情况下（序列确实只有1个元素），它被完全枚举，并且为了与这种正常情况保持一致，在所有情况下枚举整个序列更好。

尽管这是一个合理的论据，但它违背了整个LINQ库中的通用实践：它们在任何地方都使用惰性评估。除非绝对必要，否则不是通用实践完全枚举序列；事实上，一些方法更喜欢使用IList.Count（如果可用）而不是任何迭代-即使该迭代可能具有副作用。

此外，没有谓词的.Single()没有展现这种行为：它尽可能快地终止。如果论点是.Single()应该尊重枚举的副作用，则你期望所有重载都可以等效地执行。

为什么速度不是问题

Peter Lillevold做出了有趣的观察，认为做...

foreach(var elem in elems)
    if(pred(elem)) {
        retval=elem;
        count++;
    }
if(count!=1)...

than

foreach(var elem in elems)
    if(pred(elem)) {
        retval=elem;
        count++;
        if(count>1) ...
    }
if(count==0)...

毕竟，第二个版本在检测到第一个冲突后立即退出迭代，需要在循环中进行额外的测试——在“正确”的情况下，这个测试纯粹是多余的。很漂亮的理论，对吧？

但是，数字并不支持这一点；例如，在我的机器上（可能会有所不同），Enumerable.Range(0,100000000).Where(x=>x==123).Single() 实际上比 Enumerable.Range(0,100000000).Single(x=>x==123) 更快！

这可能是这台机器上这个精确表达式的 JITter 怪癖——我并不认为 Where 后面跟着没有谓词的 Single 总是更快。

但无论如何，快速失败的解决方案很不可能显著变慢。毕竟，即使在正常情况下，我们也处理了一个廉价的分支：一个从未被采取过的分支，因此对分支预测器来说很容易。当然，只有在 pred 持有时才会遇到分支——在正常情况下，每次调用只会遇到一次。与委托调用 pred 及其实现、接口方法 .MoveNext() 和 .get_Current() 及其实现的成本相比，这个成本根本可以忽略不计。

与此同时，大多数序列和谓词实际上都会做一些自己的事情，所以很难注意到由一个可预测分支引起的性能下降，而与所有其他抽象惩罚相比，这个成本简直微不足道。

- Eamon Nerbonne

我同意你所写的内容。在非抛出情况下，那个额外的测试只会被执行一次，而不是在每次循环迭代中都执行。正如你所说，与委托调用相比，它的成本微不足道。如果你已经在循环内检查了该情况并用布尔值替换了 int 计数器，则循环后面的逻辑可以简化。因此，我认为额外的检查不会显著地减慢成功情况的速度，但在失败情况下提供了巨大的好处。所以我会使用早期退出。 - CodesInChaos

@CodeInChaos：是的。添加了一句话指出它只被命中一次。 - Eamon Nerbonne

很明显，由于.Where()不计算它的匹配项，而且比.Single()少一个比较和一个本地变量以及一次递增操作，所以.Where()比.Single()更快。因此，你可以获得.Where()内部循环周期更短的优势。 - Alan Turing

2

@Artur Where(pred).Single() 和 Single(pred) 在语义上是等价的，因此 Single(pred) 应该至少与 Where(pred).Single() 一样快，甚至可能更快。所以再次强调，你说的话没有任何意义。 - CodesInChaos

2

这对我来说非常清晰。

Single 适用于调用方知道枚举只包含一个匹配项的情况，因为在其他任何情况下都会抛出昂贵的异常。

对于此用例，采用谓词的重载必须遍历整个枚举。在每次循环中不需要额外的条件，这样做会稍微更快一些。

在我看来，当前实现是正确的：它针对预期的仅包含一个匹配元素的枚举使用案例进行了优化。

- Joe

1

在循环体的每次迭代中，没有任何额外的条件 - 只有谓词匹配的那些条件：即一次。 - Eamon Nerbonne

实际上，还有另一个原因，为什么 Single 的实现方式如我所描述：Single 旨在返回序列的单个匹配项，否则返回最后一个匹配项。如果您尽快中断查找，那么您怎么知道该特定匹配项是否真的是最后一个（直到您到达末尾）？ - Alan Turing

1

在我看来，那似乎是一个糟糕的实现。

只是为了说明问题的潜在严重性：

var oneMillion = Enumerable.Range(1, 1000000)
                           .Select(x => { Console.WriteLine(x); return x; });

int firstEven = oneMillion.Single(x => x % 2 == 0);

上面的代码将输出从1到1000000的所有整数，然后抛出一个异常。

这确实是一个令人费解的问题。

- Dan Tao

3

虽然我完全同意你的回答，但它基本上只是重复了OP在问题中已经陈述的内容（主要区别在于你使用了更大的整数集合）。 - stakx - no longer contributing

我不同意：没关系，因为BCL中已经存在了First或FirstOrDefault扩展方法。 - Alan Turing

@stakx：哈，是的，说得好。只是为了让你明白我的出发点：我有时会与开发人员互动，当他们被问到像原帖示例这样的问题时，会说：“是吗？那又怎么样？它浪费了5个不必要的项；有什么大不了的。”为什么他们不会立即想到推广呢，我也说不清楚。但是当我指出将其推广后的影响时，他们就会“理解”了。这个答案是针对那些开发人员的 ;) - Dan Tao

@Artur：我看到你在很多地方都在强调这一点。我必须承认我不太理解你的逻辑。OP建议在找到第二个匹配项后，Single应该抛出异常。而First方法只是在找到第一个匹配项后返回。这是两种方法之间主要指定的行为差异：一个会抛出异常，另一个则不会。在第二个匹配项被找到时抛出异常可以保持这种行为差异，同时提高Single方法的性能。 - Dan Tao

Single的设计用于返回序列中的单个匹配项，否则返回最后一个匹配项，如果您想尽快停止查找，那么您怎么知道该特定匹配项是否真的是最后一个（直到您到达末尾）？ - Alan Turing

@Artur: 你对Single的设计有所误解。它是为了返回单个匹配项，否则就会抛出异常-而不是返回最后一个匹配项。查看一下MSDN文档; 没有说到关于获取最后一个匹配项的事情。你是否可能将Single与Last混淆了？ - Dan Tao

0

在https://connect.microsoft.com/VisualStudio/feedback/details/810457/public-static-tsource-single-tsource-this-ienumerable-tsource-source-func-tsource-bool-predicate-doesnt-throw-immediately-on-second-matching-result#提交报告后，我才发现了这个问题。

副作用的论点不成立，因为：

具有副作用并不真正是函数式的，它们被称为 Func 是有原因的。
如果您确实想要副作用，那么声称整个序列都具有副作用的版本比声称立即抛出异常的版本更合理是没有意义的。
它与 First 或其他重载的 Single 的行为不匹配。
它至少与一些其他的 Single 实现不匹配，例如 Linq2SQL 使用 TOP 2 来确保只返回需要测试多个匹配项的两个匹配项。
我们可以构造一些情况，期望程序停止运行，但它却没有停止。
我们可以构造一些情况，会抛出 OverflowException，这不是文档化的行为，因此显然是一个错误。

最重要的是，如果我们处于一个预期序列只有一个匹配元素的条件下，但实际上不是这样，那么显然出了问题。除了检测到错误状态后唯一应该做的事情是清理（而此实现会延迟这个过程）并抛出异常的一般原则之外，序列具有多个匹配元素的情况将与序列总元素数超过预期的情况重叠 - 可能是因为序列存在导致其意外循环的错误。因此，在应该触发异常的一组可能的错误中，异常被最大程度地延迟。

编辑：

Peter Lillevold提到的重复测试可能是作者选择采取他们所做的方法的原因，作为非异常情况的优化。即使如此，这也是不必要的，即使Eamon Nerbonne表明它不会有太大改进。在初始循环中没有必要进行重复测试，因为我们可以在第一次匹配时更改我们正在测试的内容。

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
  if(source == null)
    throw new ArgumentNullException("source");
  if(predicate == null)
    throw new ArgumentNullException("predicate");
  using(IEnumerator<TSource> en = source.GetEnumerator())
  {
    while(en.MoveNext())
    {
      TSource cur = en.Current;
      if(predicate(cur))
      {
        while(en.MoveNext())
          if(predicate(en.Current))
            throw new InvalidOperationException("Sequence contains more than one matching element");
       return cur;
      }
    }
  }
  throw new InvalidOperationException("Sequence contains no matching element");
}

- Jon Hanna

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ani · Accepted Answer

是的，我确实觉得有点奇怪，特别是因为不带谓词（即仅对序列进行操作）的重载似乎已经具备了快速抛出异常的“优化”。

在BCL的辩护中，我想说Single抛出的InvalidOperation异常是一个不应该通常用于控制流的低级错误异常。对于这种情况，库中并不需要进行优化。

在那些可能出现零个或多个匹配项的代码中，使用Single是完全有效的，例如：

try
{
     var item = source.Single(predicate);
     DoSomething(item);
}

catch(InvalidOperationException)
{
     DoSomethingElseUnexceptional();    
}

应该重构成不使用异常进行控制流的代码，例如（仅为示例；可以更有效地实现）：

var firstTwo = source.Where(predicate).Take(2).ToArray();

if(firstTwo.Length == 1) 
{
    // Note that this won't fail. If it does, this code has a bug.
    DoSomething(firstTwo.Single()); 
}
else
{
    DoSomethingElseUnexceptional();
}

换句话说，我们应该仅在预期序列仅包含一个匹配项时使用 Single 。它应该与 First 表现相同，但具有额外的运行时断言，即序列不包含多个匹配项。像任何其他断言一样，失败，即 Single 抛出异常的情况，应用于表示程序中的错误（无论是在运行查询的方法中还是在调用者传递给它的参数中）。

这使我们面临两种情况：

断言成立：存在单个匹配项。在这种情况下，我们希望 Single 无论如何都要消耗整个序列来断言我们的声明。没有“优化”的好处。实际上，可以认为OP提供的“优化”示例实现将由于循环的每次迭代而进行检查，因此速度会更慢。
断言失败：存在零个或多个匹配项。在这种情况下，我们稍后会抛出异常，但这并不是很重要，因为异常是愚蠢的：它表明必须修复的错误。

总之，如果“低效的实现”在生产中影响了您的性能，则：

您错误地使用了 Single 。
您的程序中存在错误。一旦修复了错误，这个特定的性能问题就会消失。

编辑：澄清了我的观点。

编辑：这是Single的一个有效用法，其中失败表示调用代码中存在错误（错误的参数）：

public static User GetUserById(this IEnumerable<User> users, string id)
{
     if(users == null)
        throw new ArgumentNullException("users");

     // Perfectly fine if documented that a failure in the query
     // is treated as an exceptional circumstance. Caller's job 
     // to guarantee pre-condition.        
     return users.Single(user => user.Id == id);    
}

Enumerable.Single的实现有问题吗？

新答案：

旧答案：

我对Single的理解：

由于副作用，这种行为是不合理的

为什么速度不是问题

我对`Single`的理解：