LINQ Почему "Enumerable = Enumerable.Skip(N)" медленно?

У меня возникла проблема с выполнением запроса LINQ, поэтому я создал небольшой упрощенный пример, чтобы продемонстрировать проблему ниже. Код принимает случайный список небольших целых чисел и возвращает список, разбитый на несколько меньших списков, каждый из которых составляет 10 или меньше.

Проблема заключается в том, что (как я это написал) код занимает экспоненциально больше с N. Это только проблема O (N). При N = 2500 код занимает 10 секунд для запуска на моем компьютере.

Я бы очень сильно оценил, если кто-то может объяснить, что происходит. Спасибо, Марк.

int N = 250;
Random r = new Random();
var work = Enumerable.Range(1,N).Select(x => r.Next(0, 6)).ToList();
var chunks = new List<List<int>>();

// work.Dump("All the work.");  // LINQPad Print
var workEnumerable = work.AsEnumerable();

Stopwatch sw = Stopwatch.StartNew();
while(workEnumerable.Any())  // or .FirstorDefault() != null
{
    int soFar = 0;
    var chunk = workEnumerable.TakeWhile( x => 
                          {
                              soFar += x;               
                              return  (soFar <= 10);
                          }).ToList();
    chunks.Add(chunk);          // Commented out makes no difference.
    workEnumerable = workEnumerable.Skip(chunk.Count); // <== SUSPECT
}
sw.Stop();

// chunks.Dump("Work Chunks.");   // LINQPad Print
sw.Elapsed.Dump("Time elapsed.");

Ответ 1

Что .Skip() делает, создает новый IEnumerable, который пересекает исходный код и только начинает давать результаты после первых N элементов. Вы связываете, кто знает, сколько из них после друг друга. Каждый раз, когда вы вызываете .Any(), вам нужно снова перебрать все ранее пропущенные элементы.

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

Ответ 2

Вы эффективно сохраняете цепочку Skip() на том же перечислимом. В списке из 250 последний фрагмент будет создан из ленивого перечисления с классами перечислителя ~ 25 'Skip' на передней панели.

Вы бы обнаружили, что все становится намного быстрее, уже если вы сделали

workEnumerable = workEnumerable.Skip(chunk.Count).ToList();

Однако, я думаю, весь подход может быть изменен.

Как насчет использования стандартного LINQ для достижения того же:

Посмотрите на live http://ideone.com/JIzpml

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    private readonly static Random r = new Random();

    public static void Main(string[] args)
    {
        int N = 250;
        var work = Enumerable.Range(1,N).Select(x => r.Next(0, 6)).ToList();

        var chunks = work.Select((o,i) => new { Index=i, Obj=o })
            .GroupBy(e => e.Index / 10)
            .Select(group => group.Select(e => e.Obj).ToList())
            .ToList();

        foreach(var chunk in chunks)
            Console.WriteLine("Chunk: {0}", string.Join(", ", chunk.Select(i => i.ToString()).ToArray()));
    }
}

Ответ 3

Метод Skip() и другие, подобные ему, в основном создают объект-заполнитель, реализующий IEnumerable, который ссылается на его родительский счетчик и содержит логику для выполнения пропуска. Таким образом, пропуски в циклах не являются перфомансами, потому что вместо того, чтобы выбрасывать элементы перечислимого типа, как вы думаете, они добавляют новый уровень логики, который лениво выполняется, когда вам действительно нужен первый элемент после всех тех, ve пропущен.

Вы можете обойти это, вызвав ToList() или ToArray(). Это заставляет "нетерпеливо" оценивать метод Skip() и действительно избавляется от элементов, которые вы пропускаете из новой коллекции, которую вы будете перечислять. Это связано с увеличением стоимости памяти и требует, чтобы все элементы были известны (поэтому, если вы используете это на IEnumerable, который представляет бесконечную серию, удачи).

Второй вариант - не использовать Linq и вместо этого использовать реализацию IEnumerable, чтобы получить и управлять IEnumerator. Затем вместо Skip() просто наберите MoveNext() необходимое количество раз.