Ответ 1

Select повторяется один раз по всему набору и для каждого элемента выполняет условную ветвь (проверка на достоверность) и операцию +.

Where+Select создает итератор, который пропускает недопустимые элементы (не yield их), выполняя + только для допустимых элементов.

Итак, стоимость для 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.

Ответ 2

Вот подробное объяснение того, что вызывает разницу во времени.

Функция Sum() для IEnumerable<int> выглядит следующим образом:

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

В С#, 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 должен выглядеть следующим образом:

• Используйте LINQ везде.
• Профиль.
• Если профайлер говорит, что LINQ является причиной узкого места, перепишите этот фрагмент кода без LINQ.

К счастью, узкие места LINQ встречаются редко. Черт, узкие места редки. За последние несколько лет я написал сотни операторов LINQ и в итоге заменил < 1%. И большинство из них было связано с LINQ2EF с низкой оптимизацией SQL, а не с ошибкой LINQ.

Итак, как всегда, сначала напишите четкий и понятный код и подождите, пока вы не профилируете, чтобы беспокоиться о микро-оптимизации.

Ответ 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 означает: каждый элемент из mod недопустим: для mod == 1 каждый элемент недействителен, для mod == 2 нечетные элементы недопустимы и т.д. Коллекция содержит 10000000 элементы.

И результаты для коллекции с 100000000 элементами:

Как вы можете видеть, результаты Select и Sum вполне согласованы во всех значениях mod. Однако where и where + Select не являются.

Ответ 4

Я предполагаю, что версия с Where отфильтровывает 0s, и они не являются субъектом Sum (т.е. вы не выполняете добавление). Это, конечно, предположение, поскольку я не могу объяснить, как выполнение дополнительного лямбда-выражения и вызов нескольких методов превосходит простое добавление 0.

Один мой друг предположил, что тот факт, что 0 в сумме может привести к серьезному снижению производительности из-за проверки переполнения. Было бы интересно посмотреть, как это будет выполняться в неконтролируемом контексте.

Ответ 5

Выполняя следующий пример, мне становится ясно, что единственный раз, когда Where + Select может превзойти Select, на самом деле, когда он отбрасывает хорошую сумму (примерно половину моих неофициальных тестов) потенциальных элементов в списке. В небольшом примере ниже я получаю примерно одинаковые цифры из обоих образцов, когда "Где" пропускает около 4 мил предметов из 10 мил. Я побежал в релизе и переупорядочил выполнение где + 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);
        }

Ответ 6

Если вам нужна скорость, просто сделать простой цикл - это, вероятно, ваш лучший выбор. И выполнение 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 guess: относительные скорости ваших двух случаев варьируются в зависимости от процента недействительных элементов, просто потому, что количество заданий Sum необходимо делать изменения в случае "Где".

Ответ 7

Мне кажется интересным, что результат MarcinJuraszek отличается от It'sNotALie's. В частности, результаты MarcinJuraszek начинаются со всех четырех реализаций в одном и том же месте, в то время как результаты It'sNotALie пересекаются вокруг середины. Я объясню, как это работает из источника.

Предположим, что существуют n полные элементы и m действительные элементы.

Функция Sum довольно проста. Он просто перебирает счетчик: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)

Для простоты предположим, что коллекция представляет собой список. Оба Select и WhereSelect создадут WhereSelectListIterator. Это означает, что генерируемые фактические итераторы одинаковы. В обоих случаях существует Sum, который пересекает итератор, WhereSelectListIterator. Наиболее интересной частью итератора является метод MoveNext.

Так как итераторы одинаковы, петли одинаковы. Единственное различие заключается в теле петель.

Тело этих лямбдов имеет очень сходную стоимость. Предложение where возвращает значение поля, а тернарный предикат также возвращает значение поля. Предложение select возвращает значение поля, а две ветки тернарного оператора возвращают либо значение поля, либо константу. Объединенное предложение select имеет ветвь как тернарный оператор, но WhereSelect использует ветвь в MoveNext.

Однако все эти операции довольно дешевы. Самой дорогостоящей операцией пока является отрасль, где нам будет стоить неправильный прогноз.

Еще одна дорогостоящая операция - Invoke. Вызов функции занимает немного больше времени, чем добавление значения, как показал Бранко Димитриевич.

Также взвешивание - это проверенное накопление в Sum. Если у процессора нет флага арифметического переполнения, тогда это может быть дорогостоящим и для проверки.

Следовательно, интересные затраты: является:

• (n + m) * Вызов + m * checked+=
• n * Вызов + n * checked+=

Таким образом, если стоимость Invoke намного выше стоимости проверенного накопления, тогда случай 2 всегда лучше. Если они примерно равны, тогда мы увидим баланс, когда будет действительна половина элементов.

Похоже на систему MarcinJuraszek, проверенная + = имеет незначительную стоимость, но на системах It'sNotALie и Branko Dimitrijevic, проверенных + = имеет значительные затраты. Похоже, это самая дорогая в системе It'sNotALie, так как точка безубыточности намного выше. Не похоже, что кто-то отправил результаты из системы, где накопление стоит намного больше, чем Invoke.

Ответ 8

Вместо того, чтобы пытаться объяснить через описание, я собираюсь сделать более математический подход.

Учитывая приведенный ниже код, который должен приближать то, что LINQ делает внутренне, относительные затраты заключаются в следующем:
Выберите только: Nd + Na
Где + Выбрать: 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;
    }
}