Enumerable.Single的错误实现?

我通过reflection器在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 } 

我认为如果有两个以上的项目符合条件,他们应该打破循环,为什么他们总是循环整个集合? 如果reflection器不正确地拆卸DLL,我写一个简单的testing:

 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); 

对于这个testing用例,我认为它会打印“变0,变1”,然后抛出一个exception。 但事实是,它保持“得到0 … 10”,并引发exception。 有没有任何algorithm的原因,他们实现这种方法?

编辑你们有些人认为这是因为谓语expression的副作用 ,经过深思熟虑和一些testing用例,我得出的结论是副作用在这种情况下并不重要 。 请提供一个例子,如果你不同意这个结论。

是的,我发现它有点奇怪,尤其是因为没有使用谓词的过载(即仅在序列上工作)似乎具有快速优化的优势。


然而,在BCL的防御中,我会说Single抛出InvalidOperationexception是一个通常不应该用于控制stream的头文件exception 。 图书馆没有必要对这种情况进行优化。

使用Single代码,其中零或多个匹配是完全有效的可能性,例如:

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

应该重构为使用控制streamexception的代码,例如(只有一个样本;这可以更有效地实现):

 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抛出的情况)应该用来表示程序中的错误 (无论是运行查询的方法还是调用者传递给它的参数)。

这给我们留下了两个例子:

  1. 断言认为:有一场比赛。 在这种情况下,我们希望Single消耗整个序列来声明我们的声明。 “优化”没有任何好处。 实际上,有人可能会认为由OP提供的“优化”的示例实现实际上会因为循环的每次迭代检查而变慢。
  2. 断言失败:有零个或多个匹配。 在这种情况下,我们比我们做得更晚,但是这并不是什么大事,因为这个例外是头重脚轻的: 它代表了一个必须修正的错误。

总而言之,如果“糟糕的实施”在生产中performance糟糕,或者:

  1. 您正在使用Single不正确。
  2. 程序中有一个错误。 一旦错误得到解决,这个特殊的性能问题就会消失。

编辑:澄清我的观点。

编辑:这里有一个单一的有效的使用,其中失败指示调用代码中的错误(错误的参数):

 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); } 

更新:
我的回答得到了很好的反馈,这让我重新思考。 因此,我首先要提出说明我的“新”观点的答案; 你仍然可以在下面find我原来的答案。 确保阅读中间的评论,以了解我的第一个答案忽略了重点。

新答案:

假设Single在不满足前提条件时抛出exception, 也就是说,当“ Single检测到“none”时,或者集合中的多个项目与谓词相匹配。

Single只能通过遍历整个集合而不抛出exception而成功。 它必须确保只有一个匹配的项目,所以它将不得不检查集合中的所有项目。

这意味着提前抛出一个exception(只要find第二个匹配项)就是一个优化,只有当Single的前提条件不能被满足并且抛出一个exception的时候才会受益。

正如用户CodeInChaos在下面的注释中清楚地表明的那样,优化不会是错误的,但是它是没有意义的,因为通常会引入优化,这将有利于正确工作的代码,而不是对代码失效有利的优化。

因此, Single可以提前抛出exception是正确的。 但并不是必须的,因为几乎没有任何附加的好处。


老答案:

我不能给出技术上的原因, 为什么这个方法是以这种方式实现的,因为我没有实现它。 但是我可以说明我对Single运营商的目的的理解,从那里得出我个人的结论,那就是确实执行得不好:

我对Single理解:

Single的目的是什么,它与FirstLast有什么不同?

使用Single运算符基本上expression了一个假设,即必须从集合中返回一个项目:

  • 如果不指定谓词,则意味着该集合预计只包含一个项目。

  • 如果您确实指定了一个谓词,那么它应该意味着该集合中只有一个项目可以满足该条件。 (使用谓词应该与items.Where(predicate).Single()具有相同的效果。

这使得Single与其他运算符(如FirstLastTake(1)有所不同。 这些经营者都没有要求应该有一个(匹配)项目。

何时应该抛出exception?

基本上,当它发现你的假设是错误的; 即当底层集合不能完全产生一个(匹配)项目时。 也就是说,当有零个或多个项目时。

什么时候应该Single使用?

当你的程序的逻辑可以保证集合只能产生一个项目,而只有一个项目时,使用Single是适当的。 如果抛出一个exception,这应该意味着你的程序的逻辑包含一个bug。

如果处理“不可靠的”集合(如I / Oinput),则应在将其传递给Single之前先validationinput。 Single ,与一个exceptioncatch块一起, 适合确保集合只有一个匹配的项目。 当你调用Single ,你应该已经确保只有一个匹配的项目。

结论:

上面说明了我对Single LINQ操作符的理解。 如果你遵循并同意这个理解,你应该得出结论, Single应该尽早抛出exception 。 没有理由等到(可能非常大)集合结束时,因为一旦检测到集合中的第二个(匹配)项目,就违反了Single的前提条件。

在考虑这个实现时,我们必须记住,这是BCL:一般代码在各种情况下都应该足够好用。

首先,采取这些情况:

  1. 迭代10个数字,其中第一个和第二个元素是相等的
  2. 迭代超过1000000个数字,其中第一个和第三个元素是相等的

原来的algorithm可以很好的处理10个项目,但是1M将严重浪费周期。 所以在这些情况下,我们知道序列中有两个或两个以上的时候,所提出的优化会有很好的效果。

然后,看看这些情况:

  1. 迭代10个数字,第一个和最后一个元素相等
  2. 迭代超过1,000,000个数字,第一个和最后一个元素相等

在这些情况下,algorithm仍然需要检查列表中的每个项目。 没有捷径。 原来的algorithm会performance得不错,履行合同。 改变algorithm,在每次迭代中引入if会实际上降低性能。 10个项目可以忽略不计,但1M将是一个很大的打击。

国际海事组织,原来的实施是正确的,因为它对大多数情况下足够好。 了解Single的实现是好的,因为它使我们能够根据我们所知道的序列做出明智的决定。 如果在一个特定场景中的性能测量显示Single导致瓶颈,那么我们可以实现我们自己的变体,该变体在该特定情况下效果更好。

更新:正如CodeInChaos和Eamon已经正确指出的那样,优化中引入的iftesting实际上并不在每个项目上执行,只在谓词匹配块内执行。 在我的例子中,我完全忽略了这样一个事实:所提出的改变不会影响执行的总体performance。

我同意引入优化可能会有利于所有情况。 然而,最终看到实施优化的决定是在性能测量的基础上进行的。

我认为这是一个不成熟的优化“错误”。

为什么这是不合理的行为,由于副作用

有人认为,由于副作用,应该预计整个名单进行评估。 毕竟,在正确的情况下(序列确实只有1个元素)完全枚举,为了与这种正常情况保持一致,在所有情况下枚举整个序列更好。

虽然这是一个合理的论点,但是它在整个LINQ库中面临着一般实践:它们使用到处都是懒惰的评估。 除非绝对必要,否则不一定要全面列举序列。 实际上,有几种方法更喜欢在任何迭代中使用IList.Count ,即使这种迭代可能有副作用。

此外, .Single() 没有谓词不会显示出这种行为:尽快终止。 如果参数是.Single()应该尊重枚举的副作用,那么您会期望所有的重载都等价地这样做。

为什么速度的情况下不成立

彼得·利勒沃德(Peter Lillevold)提出了一个有趣的观察,认为可能会更快

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

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

毕竟,第二个版本,一旦第一个冲突被检测到就会退出迭代,将需要在循环中进行额外的testing – 一个在“正确”的testing是纯粹的压载。 整洁的理论,对吧?

除此之外,这并不是数字; 例如在我的机器上(YMMV) Enumerable.Range(0,100000000).Where(x=>x==123).Single()实际上比Enumerable.Range(0,100000000).Single(x=>x==123) Enumerable.Range(0,100000000).Single(x=>x==123)

在这台机器上,这可能是一个精确的expression方式 – 我并不是断言Where无谓的Single总是更快。

但无论如何,快速解决scheme的速度都不会太慢。 毕竟,即使在正常情况下,我们正在处理一个便宜的分支:一个从未被采用的分支,因此在分支预测器上很容易。 而且当然; 分支进一步只有遇到pred时才会遇到 – 在正常情况下每次调用一次。 与.get_Current()调用pred及其实现的代价相比,这个代价是微不足道的, 再加上接口方法的成本.MoveNext().get_Current()及其实现。

与所有其他抽象惩罚相比,你会注意到由一个可预测的分支引起的性能下降是不太可能的 – 更不用说大多数序列和谓词实际上自己做了一些事情。

对我来说似乎很清楚。

Single用于调用者知道该枚举恰好包含一个匹配的情况,因为在任何其他情况下抛出一个昂贵的exception。

对于这个用例,使用谓词的重载必须迭代整个枚举。 在没有每个循环的附加条件的情况下这样做会稍微快一点。

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

这在我看来似乎是一个不好的实现。

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

 var oneMillion = Enumerable.Range(1, 1000000) .Select(x => { Console.WriteLine(x); return x; }); int firstEven = oneMillion.Single(x => x % 2 == 0); 

在抛出exception之前,上面将输出从1到1000000的所有整数。

这确实是一个头痛的人。

我在https://connect.microsoft.com/VisualStudio/feedback/details/810457/public-static-tsource-single-tsource-this-ienumerable-tsource-source-func-tsource-提交报告后才发现这个问题&#x3002; 布尔谓犯规抛出,立即-ON-第二匹配结果#

副作用论证不成立,因为:

  1. 有副作用是不是真的function,他们被称为Func的原因。
  2. 如果您确实需要副作用,那么声明在整个序列中具有副作用的版本比对立即引发的版本声称是可取的是没有意义的。
  3. 它不匹配First的行为或Single的其他重载。
  4. 它至less不匹配Single其他一些实现,例如Linq2SQL使用TOP 2来确保只有两个匹配的情况需要testing多个匹配。
  5. 我们可以构build一个应该期望程序停止的案例,但是它不会停止。
  6. 我们可以构造抛出OverflowException情况,这是没有logging的行为,因此显然是一个错误。

最重要的是,如果我们处于预期序列只有一个匹配元素的状态,但是我们没有,那么显然出现了错误。 除了在检测错误状态时唯一应该做的事情是在抛出之前清理(并且这个实现延迟)的一般原则之外,具有多于一个匹配元素的序列的情况将与一个序列的总数比预期的要多 – 可能是因为该序列有一个导致它意外循环的错误。 所以正是在一个可能引发exception的bug集合中,exception最为延迟。

编辑:

Peter Lillevold提到重复testing可能是作者select采取他们所做的方法的一个原因,作为非例外情况的优化。 如果是这样的话,那么就算是不必要了,即使从埃蒙·恩博恩(Eamon Nerbonne)那里拿出来也不会有太大的改善 在初始循环中不需要重复testing,因为我们可以在第一次匹配时更改我们正在testing的内容:

 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"); }