为什么Where和Select表现优于Select？

Question

我有一个班级,像这样:

public class MyClass
{
    public int Value { get; set; }
    public bool IsValid { get; set; }
}

_{实际上它要大得多,但这会重现问题(怪异).}

我想得到Value实例有效的总和.到目前为止,我已经找到了两个解决方案.

第一个是:

int result = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();

然而,第二个是:

int result = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();

我想获得最有效的方法.起初,我认为第二个会更有效率.然后我的理论部分刚入"嗯,一个是O(N + M + M),另一种是O(N + N),第一个应该进行更多的残疾人更好,而第二个应该表现得更好少用".我以为他们会表现得相同.编辑:然后@Martin指出Where和Select结合在一起,所以实际应该是O(m + n).但是,如果你看下面,似乎这是没有关系的.

---

所以我把它做了测试.

_{(这是100多行,所以我认为最好将其作为Gist发布.)}
结果很有趣.

_{0%的领带公差:}

鳞片都在赞成Select和Where,约〜30分.

How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where + Select: 65
Select: 36


_{2%的领带容差:}

它是一样的,除了对于一些人,他们在2%之内.我会说这是最小的误差幅度.Select而Where现在只是一个〜20分的领先优势.

How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 6
Where + Select: 58
Select: 37


_{5%系带公差:}

这就是我所说的最大误差范围.它使它更好一点Select,但并不多.

How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 17
Where + Select: 53
Select: 31


_{具有10%的系带公差:}

这超出了我的误差范围,但我仍然对结果感兴趣.因为它现在已经有一段时间了,Select并且Where有二十分的领先优势.

How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 36
Where + Select: 44
Select: 21


_{具有25%的系带公差:}

这是方式,方法我的误差范围的,但我仍然有兴趣的结果,因为Select和Where 仍然(几乎)保持其20分的领先优势.看起来它只是在少数人中脱颖而出,而这就是它的领先优势.

How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where + Select: 16
Select: 0


---

现在,我猜了20分的领先优势从中间,他们俩都一定会得到传来围绕相同的性能.我可以尝试记录它,但这将是一大堆信息.我想,图表会更好.

这就是我做的.

它表明Select线路保持稳定(预期)并且Select + Where线路上升(预期).然而,让我感到困惑的是为什么它不满足Select于50或更早的时间:实际上我期待早于50,因为必须为Selectand和Where.创建一个额外的枚举器.我的意思是,这显示了20分的领先优势,但它没有解释原因.我想这是我的问题的主要观点.

为什么它会像这样？我应该相信吗？如果没有,我应该使用另一个还是这个？

---

正如@KingKong在评论中提到的那样,你也可以使用Sum带有lambda的超载.所以我的两个选项现在改为:

第一:

int result = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);

第二:

int result = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);

我打算让它缩短一点,但是:

How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where: 60
Sum: 41
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 8
Where: 55
Sum: 38
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 21
Where: 49
Sum: 31
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 39
Where: 41
Sum: 21
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where: 16
Sum: 0


第二十分的领先优势还是存在的,这意味着它没有与做Where和Select在评论中结合所指出的@Marcin.

_{感谢您阅读我的文字墙!此外,如果您有兴趣,这里是修改版本,记录Excel接受的CSV.}

Answer 1

Select在整个集合上迭代一次,并且对于每个项目,执行条件分支(检查有效性)和+操作.

Where+Select创建一个跳过无效元素的迭代器(不是yield它们),+仅在有效项上执行.

那么,a的成本Select是:

t(s) = n * ( cost(check valid) + cost(+) )

并为Where+Select:

t(ws) = n * ( cost(check valid) + p(valid) * (cost(yield) + cost(+)) )

哪里:

• p(valid) 是列表中的项有效的概率.
• cost(check valid) 是检查有效性的分支机构的成本
• cost(yield)是构造where迭代器的新状态的代价,它比Select版本使用的简单迭代器更复杂.

如您所见,对于给定的n,Select版本是常量,而Where+Select版本是带有p(valid)变量的线性等式.成本的实际值确定两条线的交点,并且由于cost(yield)它们可以不同cost(+),因此它们不一定在p(valid)= 0.5 处相交.

Answer 2

以下是对导致时序差异的原因的深入解释.

看起来像这样的Sum()功能IEnumerable<int>:

public static int Sum(this IEnumerable<int> source)
{
    int sum = 0;
    foreach(int item in source)
    {
        sum += item;
    }
    return sum;
}

在C#中,foreach只是.Net的迭代器版本的语法糖,(不要混淆).所以上面的代码实际上是翻译成这样的:IEnumerator<T> IEnumerable<T>

public static int Sum(this IEnumerable<int> source)
{
    int sum = 0;

    IEnumerator<int> iterator = source.GetEnumerator();
    while(iterator.MoveNext())
    {
        int item = iterator.Current;
        sum += item;
    }
    return sum;
}

请记住,您要比较的两行代码如下

int result1 = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);
int result2 = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);

现在这里是踢球者:

LINQ使用延迟执行.因此,尽管它可能出现的是result1在集合迭代两次,超过它,它实际上只迭代一次. 该Where()条件在实际应用Sum()中,调用内MoveNext() (这可能要归功于神奇的yield return).

这意味着,对于循环result1内部的代码while,

{
    int item = iterator.Current;
    sum += item;
}

只对每个项目执行一次mc.IsValid == true.相比之下,result2将为集合中的每个项执行该代码.这就是为什么result1通常更快.

(虽然,请注意,调用Where()条件MoveNext()仍然有一些小开销,所以如果大多数/所有项目mc.IsValid == true,result2实际上会更快!)

希望现在很清楚为什么result2通常会变慢.现在我想解释为什么我在评论中说这些LINQ性能比较无关紧要.

创建LINQ表达式很便宜.调用委托函数很便宜.在迭代器上分配和循环很便宜.但它甚至更便宜地没有做这些事情.因此,如果您发现LINQ语句是程序中的瓶颈,根据我的经验,在没有LINQ的情况下重写它将始终使其比任何各种LINQ方法更快.

因此,您的LINQ工作流应如下所示:

1. 到处使用LINQ.
2. 轮廓.
3. 如果分析器说LINQ是瓶颈的原因,那么在没有LINQ的情况下重写那段代码.

幸运的是,LINQ瓶颈很少见.哎呀,瓶颈很少见.我在过去几年写了数百个LINQ语句,最终取代了<1%.而大多数的那些是由于LINQ2EF的SQL优化不佳,而不是LINQ的错.

因此,像往常一样,首先编写清晰明了的代码,然后等到您分析后再担心微优化.

Answer 3

有趣的事情.你知道怎么Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)定义吗？它使用Select方法!

public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector)
{
    return source.Select(selector).Sum();
}

实际上,它应该几乎一样.我自己做了快速研究,结果如下:

Where -- mod: 1 result: 0, time: 371 ms
WhereSelect -- mod: 1  result: 0, time: 356 ms
Select -- mod: 1  result 0, time: 366 ms
Sum -- mod: 1  result: 0, time: 363 ms
-------------
Where -- mod: 2 result: 4999999, time: 469 ms
WhereSelect -- mod: 2  result: 4999999, time: 429 ms
Select -- mod: 2  result 4999999, time: 362 ms
Sum -- mod: 2  result: 4999999, time: 358 ms
-------------
Where -- mod: 3 result: 9999999, time: 441 ms
WhereSelect -- mod: 3  result: 9999999, time: 452 ms
Select -- mod: 3  result 9999999, time: 371 ms
Sum -- mod: 3  result: 9999999, time: 380 ms
-------------
Where -- mod: 4 result: 7500000, time: 571 ms
WhereSelect -- mod: 4  result: 7500000, time: 501 ms
Select -- mod: 4  result 7500000, time: 406 ms
Sum -- mod: 4  result: 7500000, time: 397 ms
-------------
Where -- mod: 5 result: 7999999, time: 490 ms
WhereSelect -- mod: 5  result: 7999999, time: 477 ms
Select -- mod: 5  result 7999999, time: 397 ms
Sum -- mod: 5  result: 7999999, time: 394 ms
-------------
Where -- mod: 6 result: 9999999, time: 488 ms
WhereSelect -- mod: 6  result: 9999999, time: 480 ms
Select -- mod: 6  result 9999999, time: 391 ms
Sum -- mod: 6  result: 9999999, time: 387 ms
-------------
Where -- mod: 7 result: 8571428, time: 489 ms
WhereSelect -- mod: 7  result: 8571428, time: 486 ms
Select -- mod: 7  result 8571428, time: 384 ms
Sum -- mod: 7  result: 8571428, time: 381 ms
-------------
Where -- mod: 8 result: 8749999, time: 494 ms
WhereSelect -- mod: 8  result: 8749999, time: 488 ms
Select -- mod: 8  result 8749999, time: 386 ms
Sum -- mod: 8  result: 8749999, time: 373 ms
-------------
Where -- mod: 9 result: 9999999, time: 497 ms
WhereSelect -- mod: 9  result: 9999999, time: 494 ms
Select -- mod: 9  result 9999999, time: 386 ms
Sum -- mod: 9  result: 9999999, time: 371 ms

对于以下实现:

result = source.Where(x => x.IsValid).Sum(x => x.Value);
result = source.Select(x => x.IsValid ? x.Value : 0).Sum();
result = source.Sum(x => x.IsValid ? x.Value : 0);
result = source.Where(x => x.IsValid).Select(x => x.Value).Sum();

mod表示:每1个mod项目无效:mod == 1每个项目无效,mod == 2奇数项目无效等.收集包含10000000项目.

和100000000项目收集的结果:

正如你所看到的,Select并且Sum结果是所有相当一致mod的值.然而where,where+ select不是.

Answer 4

我的猜测是Where的版本过滤掉0并且它们不是Sum的主题(即你没有执行添加).这当然是猜测,因为我无法解释执行额外的lambda表达式和调用多个方法如何优于简单添加0.

我的一个朋友建议,由于溢出检查,总和中的0可能会导致严重的性能损失.看看这将如何在未经检查的上下文中执行将是有趣的.

Answer 5

运行以下示例,我清楚地知道,唯一一次Where + Select可以胜过Select,实际上当它丢弃列表中潜在项目的大量(非正式测试中约一半)时.在下面的小例子中,当Where跳过10mil的大约4mil项目时,我从两个样本中得到大致相同的数字.我在发布中运行,并重新排序执行where + select vs select并获得相同的结果.

static void Main(string[] args)
        {
            int total = 10000000;
            Random r = new Random();
            var list = Enumerable.Range(0, total).Select(i => r.Next(0, 5)).ToList();
            for (int i = 0; i < 4000000; i++)
                list[i] = 10;

            var sw = new Stopwatch();
            sw.Start();

            int sum = 0;

            sum = list.Where(i => i < 10).Select(i => i).Sum();            

            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);

            sw.Reset();
            sw.Start();
            sum = list.Select(i => i).Sum();            

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);
        }