145

我有一堂课,像这样:

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% 领带公差:

量表有利于SelectWhere,约 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% 的领带公差:

这超出了我的误差范围,但我仍然对结果感兴趣。因为它现在已经领先了 20 分SelectWhere

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线路向上爬升(预期)。然而,令我困惑的是为什么它不满足Selectat 50 或更早:事实上我期待早于 50,因为必须为Selectand创建一个额外的枚举器Where。我的意思是,这显示了 20 分的领先优势,但它没有解释原因。我想,这是我问题的重点。

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


正如评论中提到的@KingKong,您还可以使用Sum带有 lambda 的 's 重载。所以我的两个选项现在更改为:

第一的:

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

二十分的领先优势仍然存在,这意味着它与@Marcin 在评论中指出的Whereand组合无关。Select

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

4

8 回答 8

130

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

Where+Select创建一个跳过无效元素(不是)的迭代器,仅对有效项目yield执行 a 。+

因此,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 处相交。

于 2013-08-20T13:12:29.733 回答
33

这是导致时序差异的原因的深入解释。


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)的魔力。

这意味着, for ,循环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 的错。

所以,像往常一样,首先编写清晰和明智的代码,然后等到你分析完之后再担心微优化。

于 2013-08-20T19:12:10.977 回答
16

有趣的事情。你知道怎么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表示:moditems中的每1个无效:对于mod == 1每个item都无效,对于mod == 2奇数项无效等。 Collection包含10000000项目。

在此处输入图像描述

以及收集100000000项目的结果:

在此处输入图像描述

如您所见,所有值Select的结果都非常一致。但是,+不是。Summodwherewhereselect

于 2013-08-20T10:48:50.537 回答
6

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

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

于 2013-08-20T10:06:15.427 回答
5

运行以下示例,我清楚地知道,只有一次 Where+Select 可以胜过 Select 实际上是它丢弃了列表中大量潜在项目(在我的非正式测试中约为一半)。在下面的小示例中,当 Where 从 1000 万个项目中跳过大约 400 万个项目时,我从两个样本中得到的数字大致相同。我在 release 中运行,并重新排序了 where+select 与 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);
        }
于 2013-08-20T10:39:18.480 回答
4

如果您需要速度,那么只做一个简单的循环可能是您最好的选择。并且做得for往往比foreach(当然假设您的收藏是随机访问的)更好。

以下是我得到的 10% 元素无效的时间:

Where + Select + Sum:   257
Select + Sum:           253
foreach:                111
for:                    61

并且有 90% 的无效元素:

Where + Select + Sum:   177
Select + Sum:           247
foreach:                105
for:                    58

这是我的基准代码...

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

class Program {

    static void Main(string[] args) {

        const int count = 10000000;
        const int percentageInvalid = 90;

        var rnd = new Random();
        var myCollection = new List<MyClass>(count);
        for (int i = 0; i < count; ++i) {
            myCollection.Add(
                new MyClass {
                    Value = rnd.Next(0, 50),
                    IsValid = rnd.Next(0, 100) > percentageInvalid
                }
            );
        }

        var sw = new Stopwatch();
        sw.Restart();
        int result1 = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();
        sw.Stop();
        Console.WriteLine("Where + Select + Sum:\t{0}", sw.ElapsedMilliseconds);

        sw.Restart();
        int result2 = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();
        sw.Stop();
        Console.WriteLine("Select + Sum:\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result2);

        sw.Restart();
        int result3 = 0;
        foreach (var mc in myCollection) {
            if (mc.IsValid)
                result3 += mc.Value;
        }
        sw.Stop();
        Console.WriteLine("foreach:\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result3);

        sw.Restart();
        int result4 = 0;
        for (int i = 0; i < myCollection.Count; ++i) {
            var mc = myCollection[i];
            if (mc.IsValid)
                result4 += mc.Value;
        }
        sw.Stop();
        Console.WriteLine("for:\t\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result4);

    }

}

顺便说一句,我同意Stilgar 的猜测:你的两个案例的相对速度取决于无效项目的百分比,仅仅是因为Sum在“Where”案例中需要做的工作量会有所不同。

于 2013-08-20T11:11:32.977 回答
1

与其试图通过描述来解释,我将采用更数学的方法。

鉴于下面的代码应该近似于 LINQ 在内部执行的操作,相对成本如下:
仅选择:Nd + Na
Where+Select :Nd + Md + Ma

为了找出它们交叉的点,我们需要做一些代数:
Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)

这意味着,为了使拐点达到 50%,委托调用的成本必须与添加的成本大致相同。由于我们知道实际的拐点约为 60%,我们可以向后工作并确定 @It'sNotALie 的委托调用成本实际上约为添加成本的 2/3,这令人惊讶,但这就是他的数字说。

static void Main(string[] args)
{
    var set = Enumerable.Range(1, 10000000)
                        .Select(i => new MyClass {Value = i, IsValid = i%2 == 0})
                        .ToList();

    Func<MyClass, int> select = i => i.IsValid ? i.Value : 0;
    Console.WriteLine(
        Sum(                        // Cost: N additions
            Select(set, select)));  // Cost: N delegate
    // Total cost: N * (delegate + addition) = Nd + Na

    Func<MyClass, bool> where = i => i.IsValid;
    Func<MyClass, int> wSelect = i => i.Value;
    Console.WriteLine(
        Sum(                        // Cost: M additions
            Select(                 // Cost: M delegate
                Where(set, where),  // Cost: N delegate
                wSelect)));
    // Total cost: N * delegate + M * (delegate + addition) = Nd + Md + Ma
}

// Cost: N delegate calls
static IEnumerable<T> Where<T>(IEnumerable<T> set, Func<T, bool> predicate)
{
    foreach (var mc in set)
    {
        if (predicate(mc))
        {
            yield return mc;
        }
    }
}

// Cost: N delegate calls
static IEnumerable<int> Select<T>(IEnumerable<T> set, Func<T, int> selector)
{
    foreach (var mc in set)
    {
        yield return selector(mc);
    }
}

// Cost: N additions
static int Sum(IEnumerable<int> set)
{
    unchecked
    {
        var sum = 0;
        foreach (var i in set)
        {
            sum += i;
        }

        return sum;
    }
}
于 2013-08-27T20:23:37.807 回答
0

我认为有趣的是,MarcinJuraszek 的结果与 It'sNotALie 的不同。特别是,MarcinJuraszek 的结果开始时所有四个实现都在同一个地方,而 It'sNotALie 的结果在中间交叉。我将从源头解释这是如何工作的。

让我们假设有n全部元素和m有效元素。

Sum功能非常简单。它只是遍历枚举器: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)

为简单起见,我们假设集合是一个列表。SelectWhereSelect都将创建一个WhereSelectListIterator. 这意味着生成的实际迭代器是相同的。在这两种情况下,都有一个Sum循环遍历迭代器的WhereSelectListIterator. 迭代器最有趣的部分是MoveNext方法。

由于迭代器相同,因此循环相同。唯一的区别在于循环的主体。

这些 lambda 的主体具有非常相似的成本。where 子句返回一个字段值,三元谓词也返回一个字段值。select 子句返回一个字段值,三元运算符的两个分支返回一个字段值或一个常量。组合的 select 子句将分支作为三元运算符,但 WhereSelect 使用MoveNext.

然而,所有这些操作都相当便宜。迄今为止最昂贵的操作是分支,错误的预测将使我们付出代价。

这里另一个昂贵的操作是Invoke. 正如 Branko Dimitrijevic 所展示的,调用一个函数比添加一个值需要更长的时间。

同样权衡的是检查的累积Sum。如果处理器没有算术溢出标志,那么检查的成本也可能很高。

因此,有趣的成本是:

  1. ( n+ m) * 调用 + m*checked+=
  2. n* 调用 + n*checked+=

因此,如果 Invoke 的成本远高于检查累加的成本,那么情况 2 总是更好。如果它们差不多,那么当大约一半的元素有效时,我们将看到平衡。

看起来在 MarcinJuraszek 的系统上,checked+= 的成本可以忽略不计,但在 It'sNotALie 和 Branko Dimitrijevic 的系统上,checked+= 的成本很高。看起来它是 It'sNotALie 系统上最昂贵的,因为盈亏平衡点要高得多。看起来没有人从一个累积成本远高于调用的系统发布结果。

于 2013-08-20T21:42:45.987 回答