Разбить коллекцию на `n` части с помощью LINQ?

Question

Есть ли хороший способ разделить коллекцию на n части с помощью LINQ? Не обязательно, конечно, равномерно.

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

Answer 1

Чистое linq и самое простое решение, как показано ниже.

static class LinqExtensions
{
    public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> list, int parts)
    {
        int i = 0;
        var splits = from item in list
                     group item by i++ % parts into part
                     select part.AsEnumerable();
        return splits;
    }
}

Answer 2

РЕДАКТИРОВАТЬ: Хорошо, похоже, я неправильно понял вопрос. Я читаю это как «куски длины n», а не «n кусочков». Doh! Учитывая удаление ответа ...

(Оригинальный ответ)

Я не верю, что есть встроенный способ разбиения, хотя я собираюсь написать один в своем наборе дополнений к LINQ to Objects. У Марка Гравелла есть реализация здесь , хотя я, вероятно, изменил бы ее, чтобы она возвращала представление только для чтения:

public static IEnumerable<IEnumerable<T>> Partition<T>
    (this IEnumerable<T> source, int size)
{
    T[] array = null;
    int count = 0;
    foreach (T item in source)
    {
        if (array == null)
        {
            array = new T[size];
        }
        array[count] = item;
        count++;
        if (count == size)
        {
            yield return new ReadOnlyCollection<T>(array);
            array = null;
            count = 0;
        }
    }
    if (array != null)
    {             
        Array.Resize(ref array, count);
        yield return new ReadOnlyCollection<T>(array);
    }
}

Answer 3

static class LinqExtensions
{
    public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> list, int parts)
    {
            return list.Select((item, index) => new {index, item})
                       .GroupBy(x => x.index % parts)
                       .Select(x => x.Select(y => y.item));
    }
}

Answer 4

Хорошо, я брошу свою шляпу в кольцо. Преимущества моего алгоритма:

1. Нет дорогостоящих операторов умножения, деления или модуля
2. Все операции O (1) (см. Примечание ниже)
3. Работает для источника IEnumerable <> (свойство Count не требуется)
4. Simple

код:

public static IEnumerable<IEnumerable<T>>
  Section<T>(this IEnumerable<T> source, int length)
{
  if (length <= 0)
    throw new ArgumentOutOfRangeException("length");

  var section = new List<T>(length);

  foreach (var item in source)
  {
    section.Add(item);

    if (section.Count == length)
    {
      yield return section.AsReadOnly();
      section = new List<T>(length);
    }
  }

  if (section.Count > 0)
    yield return section.AsReadOnly();
}

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

myEnum.Section(myEnum.Count() / number_of_sections + 1)

При использовании таким способом подход больше не равен O (1), поскольку операция Count () - O (N).

Answer 5

Это то же самое, что принятый ответ, но гораздо более простое представление:

public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> items, 
                                                   int numOfParts)
{
    int i = 0;
    return items.GroupBy(x => i++ % numOfParts);
}

Приведенный выше метод разбивает IEnumerable<T> на N кусков одинакового размера или близких к равным размерам.

public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> items, 
                                                       int partitionSize)
{
    int i = 0;
    return items.GroupBy(x => i++ / partitionSize).ToArray();
}

Приведенный выше метод разбивает IEnumerable<T> на куски желаемого фиксированного размера, причем общее количество кусков не имеет значения - вопрос не в этом.

Проблема с методом Split, помимо того, что он медленнее, заключается в том, что он скремблирует выходные данные в том смысле, что группировка будет выполняться на основе i-го кратного N для каждой позиции или другими словами не получайте куски в первоначальном порядке.

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

public static IEnumerable<IEnumerable<T>> Split<T>(this ICollection<T> items, 
                                                   int numberOfChunks)
{
    if (numberOfChunks <= 0 || numberOfChunks > items.Count)
        throw new ArgumentOutOfRangeException("numberOfChunks");

    int sizePerPacket = items.Count / numberOfChunks;
    int extra = items.Count % numberOfChunks;

    for (int i = 0; i < numberOfChunks - extra; i++)
        yield return items.Skip(i * sizePerPacket).Take(sizePerPacket);

    int alreadyReturnedCount = (numberOfChunks - extra) * sizePerPacket;
    int toReturnCount = extra == 0 ? 0 : (items.Count - numberOfChunks) / extra + 1;
    for (int i = 0; i < extra; i++)
        yield return items.Skip(alreadyReturnedCount + i * toReturnCount).Take(toReturnCount);
}

Эквивалентный метод для операции Partition здесь

Answer 6

Я часто использую функцию Разделения, которую я разместил ранее. Единственная плохая вещь об этом было то, что это не было полностью потоковым. Это не проблема, если вы работаете с несколькими элементами в вашей последовательности. Мне нужно было новое решение, когда я начал работать со 100 000+ элементами в моей последовательности.

Следующее решение намного сложнее (и больше кода!), Но очень эффективно.

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

namespace LuvDaSun.Linq
{
    public static class EnumerableExtensions
    {
        public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> enumerable, int partitionSize)
        {
            /*
            return enumerable
                .Select((item, index) => new { Item = item, Index = index, })
                .GroupBy(item => item.Index / partitionSize)
                .Select(group => group.Select(item => item.Item)                )
                ;
            */

            return new PartitioningEnumerable<T>(enumerable, partitionSize);
        }

    }


    class PartitioningEnumerable<T> : IEnumerable<IEnumerable<T>>
    {
        IEnumerable<T> _enumerable;
        int _partitionSize;
        public PartitioningEnumerable(IEnumerable<T> enumerable, int partitionSize)
        {
            _enumerable = enumerable;
            _partitionSize = partitionSize;
        }

        public IEnumerator<IEnumerable<T>> GetEnumerator()
        {
            return new PartitioningEnumerator<T>(_enumerable.GetEnumerator(), _partitionSize);
        }

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


    class PartitioningEnumerator<T> : IEnumerator<IEnumerable<T>>
    {
        IEnumerator<T> _enumerator;
        int _partitionSize;
        public PartitioningEnumerator(IEnumerator<T> enumerator, int partitionSize)
        {
            _enumerator = enumerator;
            _partitionSize = partitionSize;
        }

        public void Dispose()
        {
            _enumerator.Dispose();
        }

        IEnumerable<T> _current;
        public IEnumerable<T> Current
        {
            get { return _current; }
        }
        object IEnumerator.Current
        {
            get { return _current; }
        }

        public void Reset()
        {
            _current = null;
            _enumerator.Reset();
        }

        public bool MoveNext()
        {
            bool result;

            if (_enumerator.MoveNext())
            {
                _current = new PartitionEnumerable<T>(_enumerator, _partitionSize);
                result = true;
            }
            else
            {
                _current = null;
                result = false;
            }

            return result;
        }

    }



    class PartitionEnumerable<T> : IEnumerable<T>
    {
        IEnumerator<T> _enumerator;
        int _partitionSize;
        public PartitionEnumerable(IEnumerator<T> enumerator, int partitionSize)
        {
            _enumerator = enumerator;
            _partitionSize = partitionSize;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new PartitionEnumerator<T>(_enumerator, _partitionSize);
        }

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


    class PartitionEnumerator<T> : IEnumerator<T>
    {
        IEnumerator<T> _enumerator;
        int _partitionSize;
        int _count;
        public PartitionEnumerator(IEnumerator<T> enumerator, int partitionSize)
        {
            _enumerator = enumerator;
            _partitionSize = partitionSize;
        }

        public void Dispose()
        {
        }

        public T Current
        {
            get { return _enumerator.Current; }
        }
        object IEnumerator.Current
        {
            get { return _enumerator.Current; }
        }
        public void Reset()
        {
            if (_count > 0) throw new InvalidOperationException();
        }

        public bool MoveNext()
        {
            bool result;

            if (_count < _partitionSize)
            {
                if (_count > 0)
                {
                    result = _enumerator.MoveNext();
                }
                else
                {
                    result = true;
                }
                _count++;
            }
            else
            {
                result = false;
            }

            return result;
        }

    }
}

Наслаждайтесь!

Answer 7

Интересная тема. Чтобы получить потоковую версию Split / Partition, можно использовать перечислители и получать последовательности из перечислителя, используя методы расширения. Преобразование императивного кода в функциональный код с использованием yield действительно является очень мощным методом.

Сначала расширение перечислителя, которое превращает количество элементов в ленивую последовательность:

public static IEnumerable<T> TakeFromCurrent<T>(this IEnumerator<T> enumerator, int count)
{
    while (count > 0)
    {
        yield return enumerator.Current;
        if (--count > 0 && !enumerator.MoveNext()) yield break;
    }
}

А затем перечислимое расширение, которое разделяет последовательность:

public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> seq, int partitionSize)
{
    var enumerator = seq.GetEnumerator();

    while (enumerator.MoveNext())
    {
        yield return enumerator.TakeFromCurrent(partitionSize);
    }
}

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

Наслаждайтесь!

Answer 8

Я использую это:

public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> instance, int partitionSize)
{
    return instance
        .Select((value, index) => new { Index = index, Value = value })
        .GroupBy(i => i.Index / partitionSize)
        .Select(i => i.Select(i2 => i2.Value));
}

Answer 9

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

static public IList<T[]> GetChunks<T>(this IEnumerable<T> source, int batchsize)
{
    IList<T[]> result = null;
    if (source != null && batchsize > 0)
    {
        var list = source as List<T> ?? source.ToList();
        if (list.Count > 0)
        {
            result = new List<T[]>();
            for (var index = 0; index < list.Count; index += batchsize)
            {
                var rangesize = Math.Min(batchsize, list.Count - index);
                result.Add(list.GetRange(index, rangesize).ToArray());
            }
        }
    }
    return result ?? Enumerable.Empty<T[]>().ToList();
}

static public void TestGetChunks()
{
    var ids = Enumerable.Range(1, 163).Select(i => i.ToString());
    foreach (var chunk in ids.GetChunks(20))
    {
        Console.WriteLine("[{0}]", String.Join(",", chunk));
    }
}

Я видел несколько ответов по этому семейству вопросов, в которых используются GetRange и Math.Min. Но я считаю, что в целом это более полное решение с точки зрения проверки ошибок и эффективности.

Answer 10

Это эффективное использование памяти, максимально откладывает выполнение (на пакет) и работает за линейное время O (n)

    public static IEnumerable<IEnumerable<T>> InBatchesOf<T>(this IEnumerable<T> items, int batchSize)
    {
        List<T> batch = new List<T>(batchSize);
        foreach (var item in items)
        {
            batch.Add(item);

            if (batch.Count >= batchSize)
            {
                yield return batch;
                batch = new List<T>();
            }
        }

        if (batch.Count != 0)
        {
            //can't be batch size or would've yielded above
            batch.TrimExcess();
            yield return batch;
        }
    }