[Оптимизировать это]: медленный запрос LINQ to Objects - PullRequest
8 голосов
/ 08 февраля 2010

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

Первая попытка; декларативный стиль

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length)
{
    return source.Any()
        ? source.Take(length).Cons(source.Skip(length).Section(length))
        : Enumerable.Empty<IEnumerable<α>>();
}

Вторая попытка: императивный стиль возврата дохода

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length)
{
    var fst = source.Take(length);
    var rst = source.Skip(length);

    yield return fst;

    if (rst.Any())
        foreach (var section in rst.Section(length))
            yield return section;
}

На самом деле вторая попытка хуже, как с точки зрения читабельности, композиции, так и с точки зрения скорости.

Какие-нибудь подсказки относительно того, как оптимизировать это?

Ответы [ 8 ]

10 голосов
/ 08 февраля 2010

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

Например, последовательность из миллиона чисел может быть разбита на «секции», каждая из которых производит только 100 из них, и вы хотите, чтобы все это выполнялось лениво, т.е. не собирать 100 предметов в список до их изготовления.

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

Если вы пытаетесь создать чистую ленивую реализацию, вам следует рассмотреть следующие вопросы:

  • Вы хотите перебрать базовую коллекцию только один раз
  • Вы должны вернуть перечислимые элементы, которые повторно используют базовый перечислитель
  • Вам необходимо учитывать, что возвращаемый вами раздел не полностью перечислен (например, для кода вызова требовались только первые 50 из этих 100 элементов).

Редактировать : Прежде чем перейти к своему упрощенному решению, вот несколько предостережений по этому поводу:

  • Вы не можете сохранить каждый раздел на потом, т.е. вы не можете сделать: collection.Sequence(10).ToArray(), чтобы получить массив разделов.
  • Нельзя перечислять по каждому разделу более одного раза, поскольку при этом изменяется скрытая базовая структура данных.

В основном: Мое решение не общего назначения . Вы должны пойти с комментарием @ LBushkin о MoreLinq Batch, если вам это нужно, и я без колебаний поместил бы мой код в библиотеку классов, где он должен быть локальным необходимо или переименовано во что-то, что четко предупреждает вас о проблемах с ним.


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

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

namespace ConsoleApplication20
{
    class SectionEnumerable<T> : IEnumerable<T>
    {
        private readonly IEnumerator<T> _Enumerator;

        public SectionEnumerable(IEnumerator<T> enumerator, int sectionSize)
        {
            _Enumerator = enumerator;
            Left = sectionSize;
        }

        public IEnumerator<T> GetEnumerator()
        {
            while (Left > 0)
            {
                Left--;
                yield return _Enumerator.Current;
                if (Left > 0)
                    if (!_Enumerator.MoveNext())
                        break;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public int Left { get; private set; }
    }

    static class SequenceExtensions
    {
        public static IEnumerable<IEnumerable<T>> Section<T>(this IEnumerable<T> collection, int sectionSize)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (sectionSize < 1)
                throw new ArgumentOutOfRangeException("sectionSize");

            using (IEnumerator<T> enumerator = collection.GetEnumerator())
            {
                while (enumerator.MoveNext())
                {
                    SectionEnumerable<T> enumerable = new SectionEnumerable<T>(enumerator, sectionSize);
                    yield return enumerable;
                    for (int index = 0; index < enumerable.Left; index++)
                        if (!enumerator.MoveNext())
                            yield break;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var sequence = Enumerable.Range(0, 100);
            var sections = sequence.Section(10);
            foreach (var section in sections)
            {
                Console.WriteLine(
                    String.Join(", ",
                    section.Take(5).ToArray().Select(i => i.ToString()).ToArray()));
            }
            Console.ReadLine();
        }
    }
}

Выход:

0, 1, 2, 3, 4
10, 11, 12, 13, 14
20, 21, 22, 23, 24
30, 31, 32, 33, 34
40, 41, 42, 43, 44
50, 51, 52, 53, 54
60, 61, 62, 63, 64
70, 71, 72, 73, 74
80, 81, 82, 83, 84
90, 91, 92, 93, 94

Вещи, которые вы должны тестировать:

  • Пустой входной набор не содержит разделов
  • Коллекция, имеющая только правильное количество элементов, производит только один раздел
  • Коллекция, содержащая множество элементов размера раздела (т. Е. 10, 20, 30 и т. Д. Количество элементов с размером раздела 5 или 10), не создает пустой раздел после всех ожидаемые
  • То, что на самом деле лениво, если вы перечислите по первому 10-элементному разделу, но только по первым 5 из второго раздела, только первые 15 элементов базовой коллекции будут перечислены по
9 голосов
/ 08 февраля 2010

Я подозреваю, что проблема, с которой вы столкнулись, связана с тем фактом, что перечисление конечного результата - это, по крайней мере, операция O (n ^ 2), возможно, хуже; Я еще не решил все это в моей голове.

Почему это? Хорошо, предположим, у вас есть [1, 2, 3, 4, 5, 6], и вы разбили это на то, что вы считаете {{1, 2}, {3, 4}, {5, 6}}

Это не то, что вы сделали. Вы фактически разделили это на {возьмите первые два, возьмите первые два и отбросьте их, а затем возьмите следующие два, возьмите первые два и отбросьте, а затем возьмите следующие два и отбросьте их, а затем возьмите третий два}

Обратите внимание, как каждый шаг на пути пересчитывает результат? Это потому, что массив может меняться между вызовами перечисления. LINQ был разработан, чтобы всегда получать свежие результаты; вы пишете запрос, который означает «пропустить первые четыре и повторить следующие два», это именно то, что вы получите - запрос, который выполняет этот код при его перечислении.

Является ли исходная последовательность достаточно маленькой и достаточно быстрой, чтобы вы могли прочитать все это в памяти и разбить все сразу, вместо того, чтобы пытаться сделать это лениво? Альтернативно, индексируется ли последовательность? Если все, что вы получаете, это прямой доступ к последовательности, и она слишком велика или медленна для одновременного чтения в память, то здесь вы не сможете сделать много. Но если у вас есть одно или оба из этих свойств, вы можете сделать это как минимум линейным.

4 голосов
/ 08 февраля 2010

Везде, где возможно, я пытаюсь перебирать источник только один раз внутри оператора. Если источник является чем-то вроде результата оператора Reverse(), вызов Any, Take и Skip может привести к очень неприятной производительности.

Не совсем понятно, что пытается сделать ваш оператор, но если вы можете сделать это, не читая источник несколько раз, это вполне может помочь - хотя это будет очень сильно зависеть от того, что вводят.

3 голосов
/ 08 февраля 2010

Вот еще один подход, не использующий linq, который был намного быстрее, чем ваш второй метод:

 public static IEnumerable<IEnumerable<a>> Section<a>(this IEnumerable<a> source, int length)
        {


            var enumerator = source.GetEnumerator();
            var continueLoop = true;
            do
            {
                var list = new List<a>();
                var index = 0;
                for (int i = 0; i < length; i++)
                {
                    if (enumerator.MoveNext())
                    {
                        list.Add(enumerator.Current);
                        index++;
                    }
                    else
                    {
                        continueLoop = false;
                        break;
                    }
                }
                if (list.Count > 0)
                {
                    yield return list;
                }
            } while (continueLoop);


        }
1 голос
/ 08 февраля 2010

Это быстрее?Так и должно быть, потому что требуется только одна итерация по исходной последовательности.

public static IEnumerable<IEnumerable<T>> Section<T>(
    this IEnumerable<T> source, int length)
{
    return source
        .Select((x, i) => new { Value = x, Group = i / length })
        .GroupBy(x => x.Group, y => y.Value);
}
0 голосов
/ 03 марта 2010

Как насчет метода расширения

public static class IEnumerableExtensions
{
    public static IEnumerable<List<T>> InSetsOf<T>(this IEnumerable<T> source, int max)
    {
        List<T> toReturn = new List<T>();
        foreach(var item in source)
        {
                toReturn.Add(item);
                if (toReturn.Count == max)
                {
                        yield return toReturn;
                        toReturn = new List<T>();
                }
        }
        if (toReturn.Any())
        {
                yield return toReturn;
        }
    }
}

некоторые тесты:

[TestFixture]
public class When_asked_to_return_items_in_sets
{
    [Test]
    public void Should_return_the_correct_number_of_sets_if_the_input_contains_a_multiple_of_the_setSize()
    {
        List<string> input = "abcdefghij".Select(x => x.ToString()).ToList();
        var result = input.InSetsOf(5);
        result.Count().ShouldBeEqualTo(2);
        result.First().Count.ShouldBeEqualTo(5);
        result.Last().Count.ShouldBeEqualTo(5);
    }

    [Test]
    public void Should_separate_the_input_into_sets_of_size_requested()
    {
        List<string> input = "abcdefghijklm".Select(x => x.ToString()).ToList();
        var result = input.InSetsOf(5);
        result.Count().ShouldBeEqualTo(3);
        result.First().Count.ShouldBeEqualTo(5);
        result.Last().Count.ShouldBeEqualTo(3);
    }
}        
0 голосов
/ 19 февраля 2010

Нужно ли вам по какой-то причине сохранять исходный источник во время вашего прогресса? Если нет, то почему бы вам не использовать рекурсию и не использовать стиль hd :: tl, чтобы потянуть голову, передать tl в рекурсивный вызов, и при любом рекурсии четного числа объединить две имеющиеся у вас части в секцию?

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

0 голосов
/ 19 февраля 2010

У меня была идея сегодня; проверить это

public static IEnumerable<α> Take<α>(this IEnumerator<α> iterator, int count)
{
    for (var i = 0; i < count && iterator.MoveNext(); i++)
        yield return iterator.Current;
}

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerator<α> iterator, int length)
{
    var sct = Enumerable.Empty<α>();
    do
    {
        sct = iterator.Take(length).ToArray();
        if (sct.Any())
            yield return sct;
    }
    while (sct.Any());
}

Это все еще не супер-элегантно, но, по крайней мере, реализация очень короткая и удобочитаемая.

Может быть довольно интересно исследовать операторы запросов через IEnumerator.

А для удобства

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length)
{
    using (var iterator = source.GetEnumerator())
        foreach (var e in iterator.Section(length))
            yield return e;
}
...