Почему операции LINQ могут быть быстрее, чем обычный цикл?

Question

Мы с другом были немного озадачены во время сегодняшней дискуссии по программированию.В качестве примера мы создали фиктивную проблему наличия List<int> из n случайных целых чисел (обычно 1.000.000) и хотели создать функцию, которая возвращала бы набор всех целых чисел, которых было больше одного.Довольно простые вещи.Мы создали один оператор LINQ для решения этой проблемы и простой алгоритм, основанный на сортировке вставок.

Теперь, когда мы проверили скорость выполнения кода (используя System.Diagnostics.StopWatch), результаты оказались неясными.Мало того, что код LINQ превзошел простую сортировку, он работал быстрее, чем один foreach / for, который выполнял только один цикл в списке и не имел операций внутри (который,на стороне, я думал, что компилятор должен был обнаружить и удалить все вместе.)

Если мы сгенерировали новые List<int> случайных чисел в том же выполнении программы и снова запустили код LINQ,производительность увеличится на порядки (как правило, в тысячи раз).Производительность пустых циклов была, конечно, одинаковой.

Итак, что здесь происходит?Использует ли LINQ параллелизм, чтобы превзойти нормальные циклы?Как эти результаты вообще возможны?LINQ использует быструю сортировку, которая выполняется при n * log (n), который по определению уже медленнее, чем n.

А что происходит при скачке производительности во втором запуске?

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

Answer 1

Несомненно, вы на самом деле не выполнили запрос, вы просто определили его. LINQ создает дерево выражений, которое фактически не оценивается, пока вы не выполните операцию, требующую повторения перечисления. Попробуйте добавить операцию ToList() или Count() в запрос LINQ, чтобы запрос был оценен.

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

var dataset = ...

var watch = Stopwatch.StartNew();

var query = dataset.Where( d => dataset.Count( i => i == d ) > 1 );

watch.Stop();  // timer stops here

foreach (var item in query) // query is actually evaluated here
{
   ... print out the item...
}

Answer 2

Если вы не скомпилировали с включенным «Оптимизировать код», вы, вероятно, увидите это поведение. (Это, безусловно, объясняет, почему пустой цикл не был удален.)

Код, лежащий в основе LINQ, однако, является частью уже скомпилированного кода, который, несомненно, будет оптимизирован (с помощью JIT, NGen или аналогичного).

Answer 3

Я бы предположил, что LINQ работает быстрее, чем «нормальный цикл», когда ваш алгоритм не идеален (или у вас есть проблемы в коде). Таким образом, LINQ будет быстрее сортировать, чем вы, если вы не напишите эффективный алгоритм сортировки и т. Д.

LINQ обычно «так быстро» или «достаточно близок» к скорости обычного цикла и может быть быстрее (и проще) для кодирования / отладки / чтения. В этом его преимущество, а не скорость выполнения.

Если он работает быстрее, чем пустой цикл, вы делаете что-то не так. Скорее всего, как предлагается в комментариях, вы не рассматриваете отложенное выполнение, а оператор LINQ фактически не выполняется.