Производительность LINQ - отложенное немедленное выполнение

Question

Я видел, что иногда производительность запросов LINQ to Objects может быть значительно улучшена, если их принудительно выполнять немедленно с помощью .ToArray(), но я не совсем понимаю, почему. Например, в приведенном ниже примере выполнение функции Deferred() намного медленнее, чем функция Immediate(), и экспоненциально растет со значением limit (возможно, оно было экспоненциальным в обеих функциях, но время выполнения с Immediate() было слишком мало для меня, чтобы сказать однозначно).

public void Deferred()
{
    var all = Range(limit);
    var even = from e in EvenRange(limit) where all.Contains(e) select e;
    var odd = from o in OddRange(limit) where !even.Contains(o) select o;

    var query = from q in odd select q;

    foreach(var i in query) { var j = i+1; }
}

public void Immediate()
{
    var all = Range(limit);
    var even = (from e in EvenRange(limit) where all.Contains(e) select e)
        .ToArray();
    var odd = (from o in OddRange(limit) where !even.Contains(o) select o)
        .ToArray();

    var query = (from q in odd select q).ToArray();

    foreach(var i in query) { var j = i+1; }
}

public static IEnumerable<int> OddRange(int stop)
{
    for (int i = 1; i < stop; i+=2) yield return i;
}

public static IEnumerable<int> EvenRange(int stop)
{
    for (int i = 2; i < stop; i+=2) yield return i;
}

public static IEnumerable<int> Range(int stop)
{
    for (int i = 0; i < stop; ++i) yield return i;
}

Что вызывает это замедление? Это просто дополнительный код, который генерирует компилятор и должен запускаться каждый раз, когда я обращаюсь к перечисляемому, или Deferred() также входит в некоторые дополнительные циклы, изменяя сложность запроса "Big O"?

Answer 1

Насколько я знаю, IEnumerable не кэширует результат, поэтому ваше предложение, включающее even.Contains (которое должно проверять все элементы even), вызывает полное повторное перечисление even, показывая таким образом поведение, которое вы заметили , Преобразование даже в массив или в список должно показывать хорошую производительность при перечислении нечетных. Другие языки .NET (например, F #) включают методы для кэширования результатов перечисления (если вам интересно, вы можете посмотреть на метод Fq Seq.cache)

Answer 2

Как объяснил emaster70, версия Deferred пересчитывает коллекцию even для каждого вызова even.Contains. Это делает его очень быстро ухудшаться при более высоких значениях limit.

Версия Immediate лучше, и если вы также сделаете коллекцию all незамедлительной, например:

var all = Range(limit).ToArray();

становится примерно в три раза быстрее.

Однако метод Contains для массива является операцией O (n), поэтому он также плохо масштабируется. Если условие является равенством, вы должны использовать объединение, а не искать каждое значение, используя Contains.

Если вам нужно выполнить поиск, вы должны использовать HashSet вместо массива, так как метод Contains для этого является операцией O (1).

Для limit из 10000 это в 100 раз быстрее, чем Immediate версия:

public void Joined() {
    var all = Range(limit);
    var even = from e in EvenRange(limit) join a in all on e equals a select e;
    var evenSet = new HashSet<int>(even);
    var odd = from o in OddRange(limit) where !evenSet.Contains(o) select o;

    var query = from q in odd select q;

    foreach (var i in query) { var j = i + 1; }
}

Answer 3

В этом коде

var all = Range(limit);    
var even = from e in EvenRange(limit) where all.Contains(e) select e;    
var odd = from o in OddRange(limit) where !even.Contains(o) select o;

, поскольку IEnumerables, построенные из блоков итераторов или запросов LINQ, ленивы, для вычисления каждого элемента «нечетного» требуется пересчет всей «четной» последовательности. В результате, большой код этого кода ужасен. Может быть полезно использовать очень маленький «предел» и поместить Console.WriteLine () внутри цикла в Range () и наблюдать за поведением.

Answer 4

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