Как MultiPass GroupBy () может быть быстрее, чем один проход? - PullRequest
Новая
       24

Как MultiPass GroupBy () может быть быстрее, чем один проход?

2 голосов
/ 14 марта 2012

Я не могу понять, как GroupBy () работает быстрее для многопроходного ResultSelector, чем для однопроходной версии.

Учитывая этот класс: 

    public class DummyItem
    {
        public string Category { get; set; }
        public decimal V1 { get; set; }
        public decimal V2 { get; set; }
    }

Я создаю массив с100 000 записей с некоторыми случайными данными, а затем итерация следующего запроса:

ПОДХОД 1: несколько проходов для итогов по категориям 

var q = randomData.GroupBy(
   x => x.Category,
   (k, l) => new DummyItem
   {
      Category = k,
      V1 = l.Sum(x => x.V1), // Iterate the items for this category
      V2 = l.Sum(x => x.V2), // Iterate them again
    }
);

Кажется, что двойная обработка внутреннейперечислим, где он суммирует V1 и V2 для каждой категории.

Итак, я собрал следующую альтернативу, предполагая, что это обеспечит лучшую производительность за счет расчета итогов по категориям за один проход.

ПОДХОД 2. Один проход для итогов по категориям 

var q = randomData.GroupBy(
    x => x.Category, 
    (k, l) => l.Aggregate( // Iterate the inner list once per category
            new decimal[2], 
            (t,d) => 
            {
                t[0] += d.V1;
                t[1] += d.V2;
                return t;
            },
            t => new DummyItem{ Category = k, V1=t[0], V2=t[1] }
    )
);

Довольно типичные результаты: 

'Multiple pass': iterations=5 average=2,961 ms each
'Single pass': iterations=5 average=5,146 ms each

Невероятно, но подход 2 занимает вдвое больше времени, чем подход 1. Я провел множество тестов, меняющих количество свойств V *,количество отдельных категорий и других факторов.Хотя величина разницы в производительности варьируется, Подход 2 всегда существенно медленнее , чем Подход 1.

Я что-то упустил здесь из фундаментального?Как Подход 1 может быть быстрее, чем Подход 2?

(я чувствую, что приближается лицевая маска ...)

* ОБНОВЛЕНИЕ *

После ответа @ Jirka я подумал, что стоило бы удалить GroupBy () с картинки, чтобы посмотреть, работают ли простые агрегаты в большом списке, как ожидалось.Задача состояла в том, чтобы просто вычислить итоги для двух десятичных переменных в одном и том же списке из 100 000 случайных строк.

Результаты продолжили сюрпризы:

SUM: ForEach 

decimal t1 = 0M;
decimal t2 = 0M;
foreach(var item in randomData)
{
    t1 += item.V1;
    t2 += item.V2;
}

Базовая линия.Я считаю, что самый быстрый способ получить требуемый вывод.

СУММА: Multipass 

x = randomData.Sum(x => x.V1);
y = randomData.Sum(x => x.V2);

SUM: Singlepass 

var result = randomData.Aggregate(new DummyItem(), (t, x) => 
{ 
     t.V1 += x.V1; 
     t.V2 += x.V2; 
     return t; 
});

Результаты были следующими: 

'SUM: ForEach': iterations=10 average=1,793 ms each
'SUM: Multipass': iterations=10 average=2,030 ms each
'SUM: Singlepass': iterations=10 average=5,714 ms each

Удивительно, но это показывает, что проблема не имеет ничего общего с GroupBy.Поведение согласуется с агрегацией данных в целом.Мое предположение о том, что лучше проводить агрегацию данных за один проход, просто неверно (вероятно, похмелье от моих корней БД).

( facepalm )

Поскольку @Jirka указала на встраивание, очевидно происходящее для многопроходного подхода, это означает, что оно лишь незначительно медленнее, чем базовая линия ForEach.,Моя наивная попытка оптимизировать до однопроходного режима, работала почти в 3 раза медленнее!

Похоже, что при работе со списками в памяти все, что вы хотите сделать с элементами в списке, вероятно,быть гораздо большим фактором в производительности, чем затраты на итерацию.

1 Ответ

1 голос
/ 14 марта 2012

Агрегат должен создать в процессе 99 999 записей активации (для вызовов не встроенных методов).Это компенсирует преимущество одного прохода.

Думайте о количестве, сумме, среднем и т. Д. Как о оптимизированных особых случаях того, что Aggregate может делать в общем случае.

...