Экономия памяти в GroupBy

Question

Запуск LINQ to Objects * Метод 1001 * для многих элементов (гигабайт) может занимать много памяти.Если IEnumerable<T> уже упорядочен по ключу, мы могли бы написать GroupBy, который не занимал бы столько памяти.

Где я могу найти библиотеку, в которой есть такой метод?

Answer 1

Там нет ничего в рамках, чтобы сделать это.Если вам не нужен фактический IGrouping<,>, вы можете использовать это:

static IEnumerable<IList<TElement>> GroupByChanges<TElement, TKey>
    (this IEnumerable<TElement> source,
     Func<TElement, TKey> projection)
{
    // TODO: Argument validation, splitting this into two methods
    // to achieve eager validation.
    // TODO: Allow a custom comparer to be used, possibly even
    // an IComparer<T> instead of an IEqualityComparer<T>
    IEqualityComparer<TKey> comparer = EqualityComparer<TKey>.Default;

    using (IEnumerator<TElement> iterator = source.GetEnumerator())
    {
        if (!iterator.MoveNext())
        {
            yield break;
        }
        TKey currentKey = projection(iterator.Current);
        IList<TElement> currentList = new List<TElement> { iterator.Current };
        while (iterator.MoveNext())
        {
            TKey key = projection(iterator.Current);
            if (!comparer.Equals(currentKey, key))
            {
                yield return currentList;
                currentList = new List<TElement>();
            }
            currentList.Add(iterator.Current);
        }
        yield return currentList;
    }
}

Если вам нужна полная реализация IGrouping<,>, это будет немного сложнее - но вы всегда можете взять мой Реализация Edulinq .

Реализация GroupByChanges изменилась бы очень мало - просто измените назначения currentList, чтобы передать ключ конструктору Grouping:

Grouping<TKey, TElement> currentGroup = new Grouping<TKey, TElement>(currentKey)
    { iterator.Current };

Answer 2

Вы можете легко реализовать это самостоятельно:

public static class Extensions
{

    public static IEnumerable<IGrouping<TKey, TSource>> GroupByAlreadyOrdered<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
    {
        return source.GroupByAlreadyOrdered(keySelector, null);
    }

    public static IEnumerable<IGrouping<TKey, TSource>> GroupByAlreadyOrdered<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
    {
        TKey currentKey = default(TKey);
        bool first = true;
        List<TSource> currentGroup = null;
        comparer = comparer ?? EqualityComparer<TKey>.Default;

        foreach (var item in source)
        {
            TKey key = keySelector(item);
            if (first || !comparer.Equals(key, currentKey))
            {
                if (currentGroup != null && currentGroup.Any())
                {
                    yield return new Grouping<TKey, TSource>(currentKey, currentGroup);
                }
                currentGroup = new List<TSource>();
            }

            currentGroup.Add(item);
            first = false;
            currentKey = key;
        }
        // Last group
        if (currentGroup != null && currentGroup.Any())
        {
            yield return new Grouping<TKey, TSource>(currentKey, currentGroup);
        }
    }

    private class Grouping<TKey, TElement> : IGrouping<TKey, TElement>
    {
        private readonly TKey _key;
        private readonly IEnumerable<TElement> _elements;

        public Grouping(TKey key, IEnumerable<TElement> elements)
        {
            _key = key;
            _elements = elements;
        }

        public TKey Key
        {
            get { return _key; }
        }

        public IEnumerator<TElement> GetEnumerator()
        {
            return _elements.GetEnumerator();
        }

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

}

Answer 3

Ваша проблема очень специфична. Маловероятно, что вы найдете библиотеку, которая уже делает это. Если ваши предметы упорядочены по ключу, который вы используете для группировки, это почти тривиальная задача - «сгруппировать» этот список самостоятельно.

Answer 4

Как Томас, но немного быстрее

public static IEnumerable<IGrouping<TKey, TSource>> FastGroupBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector)
{
    using (var enumerator = source.GetEnumerator())
    {
        if (enumerator.MoveNext())
        {
            Grouping<TKey, TSource> grouping;
            List<TSource> list = new List<TSource>();
            TKey key = keySelector(enumerator.Current);
            list.Add(enumerator.Current);
            while (enumerator.MoveNext())
            {
                var currentKey = keySelector(enumerator.Current);
                if (key.Equals(currentKey))
                {
                    list.Add(enumerator.Current);
                    continue;
                }

                grouping = new Grouping<TKey, TSource>(key, list);
                yield return grouping;

                key = currentKey;
                list = new List<TSource>();
                list.Add(enumerator.Current);
            }

            grouping = new Grouping<TKey, TSource>(key, list);
            yield return grouping;
        }
    }
}