У меня есть класс, как это:

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, в качестве дополнительного переписчик должен был быть создан для Selectи Where. Я имею в виду, это показывает преимущество в 20 пунктов, но это не объясняет почему. Это, наверное, главное в моем вопросе.

Почему это ведет себя так? Должен ли я доверять этому? Если нет, я должен использовать другой или этот?

Как упоминалось в комментариях @KingKong, вы также можете использовать Sumперегрузку, которая принимает лямбду. Таким образом, мои два варианта теперь изменены на это:

Первый:

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 в комментариях.

_{Спасибо за чтение моей стены текста! Кроме того, если вам интересно, вот измененная версия, которая регистрирует CSV, который принимает Excel.}

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.

Вот подробное объяснение причин различий во времени.

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%. И большинство из них были связаны с плохой оптимизацией SQL в LINQ2EF , а не по вине LINQ.

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

Забавная вещь. Вы знаете, как это 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нет.

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

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

Запустив следующий пример, мне становится ясно, что единственный способ, где Where + Select может превзойти Select, - это когда фактически отбрасывается значительное количество (примерно половина в моих неофициальных тестах) потенциальных элементов в списке. В приведенном ниже небольшом примере я получаю примерно одинаковые числа из обоих образцов, когда Where пропускает примерно 4 миллиона пунктов из 10 миллионов. Я побежал в выпуске, и переупорядочил выполнение, где + выберите против выбора с теми же результатами.

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

Если вам нужна скорость, лучше всего сделать простой цикл. И дела, 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);

    }

}

Кстати, я согласен с предположением Стилгара : относительные скорости ваших двух дел варьируются в зависимости от процента недопустимых предметов, просто потому, что объем работы, которую Sumнеобходимо выполнить, зависит от случая «Где».

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

Учитывая приведенный ниже код, который должен приблизительно соответствовать тому, что делает 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;
    }
}

Я думаю, это интересно, что результат MarcinJuraszek отличается от результата It'sNotALie. В частности, результаты 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. Если процессор не имеет арифметического флага переполнения, то это также может быть дорогостоящим для проверки.

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

1. ( n+ m) * Invoke + m*checked+=
2. n* Вызвать + n*checked+=

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

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