linq Enumerable的错误实现,单个?

sr4lhrrt  于 2023-07-31  发布在  其他
关注(0)|答案(7)|浏览(87)

我在Enumerable.cs中通过reflector发现了这个实现。

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个以上的项目满足条件,他们应该打破循环,为什么他们总是循环通过整个集合?为了防止reflector错误地反汇编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”,然后抛出一个异常。但事实是,它一直在“得到0...得到10”并抛出异常。他们这样实现这个方法有什么算法上的原因吗?

EDIT有些人认为是因为 * predicate 表达式的副作用 *,经过深入思考和一些测试用例,我得出结论,副作用在这种情况下并不重要。如果你不同意这个结论,请举例说明。
12年后现在是2023年,我发现在最新的.NET中实现被更改为正确的方式:)https://github.com/dotnet/runtime/blob/main/src/libraries/System.Linq/src/System/Linq/Single.cs

3phpmpom

3phpmpom1#

是的,我确实觉得这有点奇怪,特别是因为重载不接受 predicate (即只对序列起作用)does 似乎具有快速抛出“优化”。
然而,在BCL的辩护中,我会说Single抛出的**InvalidOperation异常是一个boneheaded exception,通常不应该用于控制流。**对于这样的情况,库没有必要进行优化。
使用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相同,但带有额外的运行时Assert序列不包含多个匹配项。与其他Assert一样,失败,即当Single抛出时,应该用来表示程序中的bug(无论是在运行查询的方法中,还是在调用者传递给它的参数中)。
这给我们留下了两种情况:
1.该Assert认为:只有一个匹配。在本例中,我们希望Single使用整个序列 * 无论如何 * 来Assert我们的声明。“优化”没有任何好处。事实上,有人可能会说,OP提供的“优化”示例实现实际上会更慢,因为对循环的每次迭代都要进行检查。
1.Assert失败:存在零个或多个匹配项。在这种情况下,我们 * 确实 * 抛出比我们 * 可以 *,但这不是那么大的问题,因为异常是愚蠢的:表示必须修复的bug。
总而言之,如果“糟糕的实现”在生产中影响了您的性能,那么:
1.您错误地使用了Single
1.你的程序中有一个bug。一旦bug被修复,这个特定的性能问题就会消失。
编辑:澄清了我的观点。
编辑:这里是Single的一个 valid 用法,其中failure表示 calling 代码中的bug(错误参数):

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

anauzrmj

anauzrmj2#

*更新:

我的回答得到了一些很好的反馈,这让我重新思考。因此,我将首先提供一个答案,说明我的“新”观点;你仍然可以在下面找到我最初的答案。请务必阅读中间的评论,以了解我的第一个答案在哪里没有抓住要点。*

新答案:

让我们假设Single在不满足其前提条件时应该抛出异常;也就是说,当Single检测到集合中没有或有多个项与 predicate 匹配时。
Single只有在遍历整个集合时才能在不引发异常的情况下成功。它必须确保正好有一个匹配项,因此必须检查集合中的所有项。
这意味着提前抛出异常(一旦它找到第二个匹配项)本质上是一种优化,只有当Single的前提条件不能满足时,以及当它将抛出异常时,您才能从中受益。
正如用户CodeInChaos在下面的评论中清楚地说的那样,优化不会错,但它毫无意义,因为人们通常引入的优化将有利于正确工作的代码,而不是优化将有利于故障代码。
因此,实际上Single可以提前抛出异常;但它并不一定非要这样做,因为实际上并没有额外的好处。

老答案:

我不能给予一个技术上的理由 * 为什么 * 该方法是这样实现的,因为我没有实现它。但我可以陈述我对Single操作符的 * 目的 * 的理解,并由此得出我个人的结论,即它确实实现得很糟糕:

我对Single的理解:

Single的用途是什么,它与例如是First还是Last

使用Single运算子,基本上表示必须从集合中只传回一个项目的假设:

  • 如果不指定 predicate ,则意味着集合应该只包含一个项。
  • 如果您指定了述词,这应该表示集合中只有一个项目会满足该条件。(使用述词应该与items.Where(predicate).Single()具有相同的效果。)

这就是SingleFirstLastTake(1)等其他运算符的不同之处。这些运算符都没有要求应该有 * 正好 * 一个(匹配)项。

Single何时应抛出异常?

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

何时应使用Single

当您的程式逻辑可以保证集合会产生一个项目,而且只会产生一个项目时,使用Single是适当的。如果抛出了异常,那就意味着程序的逻辑中包含了bug。
如果处理“不可靠”的集合(如I/O输入),则应首先验证输入,然后再将其传递给SingleSingle与异常catch块一起 * 不 * 适用于确保集合中只有一个匹配项。在调用Single时,您应该 * 已经 * 确保只有一个匹配项。

结论:

上面陈述了我对Single LINQ操作符的理解。如果您遵循并同意这种理解,则应该得出结论:Single应该尽早抛出异常。没有理由等到集合(可能非常大)结束,因为一旦它在集合中检测到第二个(匹配的)项,就会违反Single的先决条件。

wa7juj8i

wa7juj8i3#

在考虑这种实现时,我们必须记住这是BCL:一般的代码,应该在各种场景下都能很好地工作。
首先,考虑以下场景:
1.迭代超过10个数字,其中第一个和第二个元素相等
1.迭代超过1.000.000个数字,其中第一个和第三个元素相等
原始算法对于10个项目来说足够好,但1M会严重浪费周期。因此,在这些情况下 * 我们知道 * 在序列中有两个或更多的早期,建议的优化将具有良好的效果。
然后,看看这些场景:
1.迭代超过10个数字,其中第一个和最后一个元素相等
1.迭代超过1.000.000个数字,其中第一个和最后一个元素相等
在这些场景中,算法仍然需要检查列表中的每个项目。没有捷径。原来的算法会表现得很好 * 足够 *,它履行了契约。改变算法,在每次迭代中引入if实际上会降低性能。对于10个项目,它将是微不足道的,但1M将是一个大热门。
IMO,原来的实现是正确的,因为它对大多数场景都足够好。了解Single的实现是很好的,因为它使我们能够根据我们对使用它的序列的了解做出明智的决定。如果某个特定场景中的性能测量显示Single导致瓶颈,那么:然后我们可以实现我们自己的变体,在特定的场景中工作得更好。

更新:正如CodeInChaos和Eamon正确指出的,优化中引入的if测试确实不是对每个项目执行,只在 predicate 匹配块中执行。在我的例子中,我完全忽略了一个事实,即拟议的更改不会影响实施的整体性能。

我同意引入优化可能会对所有场景都有好处。但很高兴看到,最终,实施优化的决定是基于性能测量。

twh00eeo

twh00eeo4#

我认为这是一个过早的优化“bug”。

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

有些人认为,由于副作用,应该对整个列表进行评估。毕竟,在正确的情况下(序列确实只有1个元素),它是完全枚举的,为了与这种正常情况保持一致,最好在 all 情况下枚举整个序列。
虽然这是一个合理的论点,但它与LINQ库的普遍实践背道而驰:他们到处都在使用惰性评估。除了绝对必要的情况外,完整枚举序列不是一般的做法;实际上,当在任何迭代中可用时,有几种方法优选使用IList.Count-即使迭代可能有副作用。
此外,.Single()without predicate 不会表现出以下行为:尽快结束。如果参数是.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)...


毕竟,一旦检测到第一个冲突就退出迭代的第二个版本将需要循环中的额外测试--一个在“正确”中纯粹是镇流器的测试。不错的理论,对吧?
不过,这不是由数字决定的例如,在我的机器上(YMMV)Enumerable.Range(0,100000000).Where(x=>x==123).Single()实际上比Enumerable.Range(0,100000000).Single(x=>x==123)更快!
这可能是这台机器上这个精确表达式的一个JITter怪癖--我并不是说Where后面跟着无 predicate 的Single总是更快。
但无论如何,快速失效的解决方案不太可能明显慢下来。毕竟,即使在正常情况下,我们也在处理一个廉价的分支:一个“从未”采取的分支,因此在分支预测器上容易。当然;该分支仅在pred成立时才被遇到-在正常情况下是每次调用一次。与委托调用pred及其实现的成本,* 加上接口方法.MoveNext().get_Current()及其实现的成本相比,这个成本可以忽略不计。
与所有其他抽象惩罚相比,您几乎不可能注意到由一个可预测分支导致的性能下降-更不用说大多数序列和 predicate 实际上自己做一些事情了。

h22fl7wq

h22fl7wq5#

我看很清楚。
Single用于调用者知道枚举恰好包含一个匹配项的情况,因为在任何其他情况下都会抛出昂贵的异常。
对于这个用例,接受 predicate 的重载必须遍历整个枚举。如果在每个循环中没有附加条件,则会稍微快一点。
在我看来,目前的实施方式是正确的:它针对包含恰好一个匹配元素的枚举的预期用例而被优化。

qnzebej0

qnzebej06#

在我看来,这确实是一个糟糕的实施方式。
只是为了说明问题的潜在严重性:

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

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

字符串
上面的命令将在抛出异常之前输出从1到1000000的所有整数。
这是一个令人挠头的肯定。

xzv2uavs

xzv2uavs7#

我是在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#举报后才发现这个问题的
副作用的论点站不住脚,因为:
1.副作用并不真正起作用,它们被称为Func是有原因的。
1.如果您确实想要副作用,那么声称在整个序列中都有副作用的版本是可取的,这并不比声称立即抛出的版本更有意义。
1.它与FirstSingle的其他过载行为不匹配。
1.它至少与Single的一些其他实现不匹配,例如Linq 2SQL使用TOP 2来确保只返回两个用于测试多个匹配的匹配用例。
1.我们可以构造一个我们应该期望程序停止但它没有停止的情况。
1.我们可以构造抛出OverflowException的情况,这不是记录在案的行为,因此显然是一个bug。
最重要的是,如果我们处于这样一个条件,我们期望序列只有一个匹配元素,但我们没有,那么显然有些地方出了问题。除了检测到错误状态时你应该做的唯一事情是在抛出之前清理(这个实现延迟了清理)的一般原则之外,序列具有多个匹配元素的情况将与序列具有比预期更多元素的情况重叠-可能是因为序列有一个bug导致它意外循环。因此,正是在一组可能的bug中触发了异常,该异常被延迟得最多。
编辑:
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");
}

字符串

相关问题