Разделить список на подсписки с помощью LINQ

377

Есть ли способ, которым я могу разделить List<SomeObject>на несколько отдельных списков SomeObject, используя индекс элемента в качестве разделителя каждого разделения?

Позвольте мне привести пример:

У меня есть List<SomeObject>и мне нужно List<List<SomeObject>>или List<SomeObject>[], чтобы каждый из этих результирующих списков содержал группу из 3 элементов исходного списка (последовательно).

например.:

  • Оригинальный список: [a, g, e, w, p, s, q, f, x, y, i, m, c]

  • Результирующие списки: [a, g, e], [w, p, s], [q, f, x], [y, i, m], [c]

Мне также нужно, чтобы размер результирующих списков был параметром этой функции.

Фелипе Лима
источник

Ответы:

378

Попробуйте следующий код.

public static IList<IList<T>> Split<T>(IList<T> source)
{
    return  source
        .Select((x, i) => new { Index = i, Value = x })
        .GroupBy(x => x.Index / 3)
        .Select(x => x.Select(v => v.Value).ToList())
        .ToList();
}

Идея состоит в том, чтобы сначала сгруппировать элементы по индексам. Разделив на три, вы сгруппируете их в группы по 3. Затем преобразуйте каждую группу в список, а из IEnumerableof - Listв a Listof Lists.

JaredPar
источник
21
GroupBy делает неявную сортировку. Это может убить производительность. Нам нужно что-то вроде обратного SelectMany.
yfeldblum
5
@ Справедливость, GroupBy может быть реализована путем хеширования. Как вы знаете, реализация GroupBy "может убить производительность"?
Эми Б
5
GroupBy не возвращает ничего, пока не будут перечислены все элементы. Вот почему это медленно. Списки, которые нужны OP, являются смежными, поэтому лучший метод мог бы получить первый подсписок, [a,g,e]прежде чем перечислять еще какой-либо исходный список.
полковник Паник
9
Возьмите крайний пример бесконечного IEnumerable. GroupBy(x=>f(x)).First()никогда не уступит группе. OP спросил о списках, но если мы напишем для работы с IEnumerable, сделав всего одну итерацию, мы получим преимущество в производительности.
полковник Паник
8
@Nick Order не сохранился на вашем пути, хотя. Это по-прежнему полезно знать, но вы бы сгруппировали их в (0,3,6,9, ...), (1,4,7,10, ...), (2,5,8 , 11, ...). Если порядок не имеет значения, тогда это хорошо, но в этом случае это звучит так, как будто это имеет значение.
Reafexus
325

Этот вопрос немного старый, но я только что написал это, и я думаю, что он немного более элегантен, чем другие предлагаемые решения:

/// <summary>
/// Break a list of items into chunks of a specific size
/// </summary>
public static IEnumerable<IEnumerable<T>> Chunk<T>(this IEnumerable<T> source, int chunksize)
{
    while (source.Any())
    {
        yield return source.Take(chunksize);
        source = source.Skip(chunksize);
    }
}
CaseyB
источник
14
Люблю это решение. Я бы рекомендовал добавить эту проверку if (chunksize <= 0) throw new ArgumentException("Chunk size must be greater than zero.", "chunksize");
исправности,
10
Мне нравится это, но это не супер эффективно
Сэм Шафран
51
Мне нравится этот, но эффективность времени есть O(n²). Вы можете перебрать список и получить O(n)время.
наступлением
8
@hIpPy, как это п ^ 2? Выглядит линейно для меня
Вивек Махарадж
13
@vivekmaharajh sourceзаменяется завернутым IEnumerableкаждый раз. Таким образом, взятие элементов sourceпроходит через слои Skips
Лассе Эспехолт
99

В целом, подход, предложенный CaseyB, работает нормально, на самом деле, если вы проходите мимо, List<T>его сложно обвинить , возможно, я бы изменил его на:

public static IEnumerable<IEnumerable<T>> ChunkTrivialBetter<T>(this IEnumerable<T> source, int chunksize)
{
   var pos = 0; 
   while (source.Skip(pos).Any())
   {
      yield return source.Skip(pos).Take(chunksize);
      pos += chunksize;
   }
}

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

foreach (var item in Enumerable.Range(1, int.MaxValue).Chunk(8).Skip(100000).First())
{
   Console.WriteLine(item);
}
// wait forever 

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

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

Чтобы проиллюстрировать это, попробуйте запустить:

foreach (var item in Enumerable.Range(1, int.MaxValue)
               .Select(x => x + new string('x', 100000))
               .Clump(10000).Skip(100).First())
{
   Console.Write('.');
}
// OutOfMemoryException

Наконец, любая реализация должна быть способна обрабатывать итеративные итерации блоков, например:

Enumerable.Range(1,3).Chunk(2).Reverse().ToArray()
// should return [3],[1,2]

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

Для решения всех этих проблем вы можете использовать следующее:

namespace ChunkedEnumerator
{
    public static class Extensions 
    {
        class ChunkedEnumerable<T> : IEnumerable<T>
        {
            class ChildEnumerator : IEnumerator<T>
            {
                ChunkedEnumerable<T> parent;
                int position;
                bool done = false;
                T current;


                public ChildEnumerator(ChunkedEnumerable<T> parent)
                {
                    this.parent = parent;
                    position = -1;
                    parent.wrapper.AddRef();
                }

                public T Current
                {
                    get
                    {
                        if (position == -1 || done)
                        {
                            throw new InvalidOperationException();
                        }
                        return current;

                    }
                }

                public void Dispose()
                {
                    if (!done)
                    {
                        done = true;
                        parent.wrapper.RemoveRef();
                    }
                }

                object System.Collections.IEnumerator.Current
                {
                    get { return Current; }
                }

                public bool MoveNext()
                {
                    position++;

                    if (position + 1 > parent.chunkSize)
                    {
                        done = true;
                    }

                    if (!done)
                    {
                        done = !parent.wrapper.Get(position + parent.start, out current);
                    }

                    return !done;

                }

                public void Reset()
                {
                    // per http://msdn.microsoft.com/en-us/library/system.collections.ienumerator.reset.aspx
                    throw new NotSupportedException();
                }
            }

            EnumeratorWrapper<T> wrapper;
            int chunkSize;
            int start;

            public ChunkedEnumerable(EnumeratorWrapper<T> wrapper, int chunkSize, int start)
            {
                this.wrapper = wrapper;
                this.chunkSize = chunkSize;
                this.start = start;
            }

            public IEnumerator<T> GetEnumerator()
            {
                return new ChildEnumerator(this);
            }

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

        }

        class EnumeratorWrapper<T>
        {
            public EnumeratorWrapper (IEnumerable<T> source)
            {
                SourceEumerable = source;
            }
            IEnumerable<T> SourceEumerable {get; set;}

            Enumeration currentEnumeration;

            class Enumeration
            {
                public IEnumerator<T> Source { get; set; }
                public int Position { get; set; }
                public bool AtEnd { get; set; }
            }

            public bool Get(int pos, out T item) 
            {

                if (currentEnumeration != null && currentEnumeration.Position > pos)
                {
                    currentEnumeration.Source.Dispose();
                    currentEnumeration = null;
                }

                if (currentEnumeration == null)
                {
                    currentEnumeration = new Enumeration { Position = -1, Source = SourceEumerable.GetEnumerator(), AtEnd = false };
                }

                item = default(T);
                if (currentEnumeration.AtEnd)
                {
                    return false;
                }

                while(currentEnumeration.Position < pos) 
                {
                    currentEnumeration.AtEnd = !currentEnumeration.Source.MoveNext();
                    currentEnumeration.Position++;

                    if (currentEnumeration.AtEnd) 
                    {
                        return false;
                    }

                }

                item = currentEnumeration.Source.Current;

                return true;
            }

            int refs = 0;

            // needed for dispose semantics 
            public void AddRef()
            {
                refs++;
            }

            public void RemoveRef()
            {
                refs--;
                if (refs == 0 && currentEnumeration != null)
                {
                    var copy = currentEnumeration;
                    currentEnumeration = null;
                    copy.Source.Dispose();
                }
            }
        }

        public static IEnumerable<IEnumerable<T>> Chunk<T>(this IEnumerable<T> source, int chunksize)
        {
            if (chunksize < 1) throw new InvalidOperationException();

            var wrapper =  new EnumeratorWrapper<T>(source);

            int currentPos = 0;
            T ignore;
            try
            {
                wrapper.AddRef();
                while (wrapper.Get(currentPos, out ignore))
                {
                    yield return new ChunkedEnumerable<T>(wrapper, chunksize, currentPos);
                    currentPos += chunksize;
                }
            }
            finally
            {
                wrapper.RemoveRef();
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int i = 10;
            foreach (var group in Enumerable.Range(1, int.MaxValue).Skip(10000000).Chunk(3))
            {
                foreach (var n in group)
                {
                    Console.Write(n);
                    Console.Write(" ");
                }
                Console.WriteLine();
                if (i-- == 0) break;
            }


            var stuffs = Enumerable.Range(1, 10).Chunk(2).ToArray();

            foreach (var idx in new [] {3,2,1})
            {
                Console.Write("idx " + idx + " ");
                foreach (var n in stuffs[idx])
                {
                    Console.Write(n);
                    Console.Write(" ");
                }
                Console.WriteLine();
            }

            /*

10000001 10000002 10000003
10000004 10000005 10000006
10000007 10000008 10000009
10000010 10000011 10000012
10000013 10000014 10000015
10000016 10000017 10000018
10000019 10000020 10000021
10000022 10000023 10000024
10000025 10000026 10000027
10000028 10000029 10000030
10000031 10000032 10000033
idx 3 7 8
idx 2 5 6
idx 1 3 4
             */

            Console.ReadKey();


        }

    }
}

Существует также ряд оптимизаций, которые вы могли бы ввести для итераций по порядку, выходящих за рамки порядка, который выходит за рамки данной области.

Какой метод вы должны выбрать? Это полностью зависит от проблемы, которую вы пытаетесь решить. Если вас не интересует первый недостаток, простой ответ невероятно привлекателен.

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

Сэм Шафран
источник
Будет ли ошибка Enumerable.Range (0, 100) .Chunk (3) .Reverse (). ToArray () ошибочной или Enumerable.Range (0, 100) .ToArray (). Chunk (3) .Reverse () .ToArray () выбрасывает исключение?
Кэмерон МакФарланд
@SamSaffron Я обновил свой ответ и чрезвычайно упростил код, так как, по моему мнению, это является значительным вариантом использования (и признаю предостережения).
casperOne
Как насчет чанкинга IQueryable <>? Я предполагаю, что подход Take / Skip будет оптимальным, если мы хотим делегировать максимум операций провайдеру
Guillaume86
@ Guillaume86 Я согласен, если у вас есть IList или IQueryable, вы можете использовать все виды ярлыков, которые сделали бы это намного быстрее (Linq делает это внутренне для всех видов других методов)
Сэм Саффрон
1
Это, безусловно, лучший ответ на эффективность. У меня возникла проблема с использованием SqlBulkCopy с IEnumerable, который запускает дополнительные процессы в каждом столбце, поэтому он должен проходить эффективно только за один проход. Это позволит мне разбить IEnumerable на куски управляемого размера. (Для тех, кто интересуется, я включил потоковый режим SqlBulkCopy, который, кажется, не работает).
Brain2000
64

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

Скорее, я думаю, что вы должны создать свой собственный итератор, вот так:

public static IEnumerable<IEnumerable<T>> GetEnumerableOfEnumerables<T>(
  IEnumerable<T> enumerable, int groupSize)
{
   // The list to return.
   List<T> list = new List<T>(groupSize);

   // Cycle through all of the items.
   foreach (T item in enumerable)
   {
     // Add the item.
     list.Add(item);

     // If the list has the number of elements, return that.
     if (list.Count == groupSize)
     {
       // Return the list.
       yield return list;

       // Set the list to a new list.
       list = new List<T>(groupSize);
     }
   }

   // Return the remainder if there is any,
   if (list.Count != 0)
   {
     // Return the list.
     yield return list;
   }
}

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


В свете ответа Сэма я почувствовал, что есть более простой способ сделать это без:

  • Итерация по списку снова (что я не делал изначально)
  • Материализация элементов в группах перед выпуском фрагмента (для больших фрагментов могут возникнуть проблемы с памятью)
  • Весь код, который выложил Сэм

Тем не менее, вот еще один проход, который я записал в методе расширения для IEnumerable<T>вызова Chunk:

public static IEnumerable<IEnumerable<T>> Chunk<T>(this IEnumerable<T> source, 
    int chunkSize)
{
    // Validate parameters.
    if (source == null) throw new ArgumentNullException("source");
    if (chunkSize <= 0) throw new ArgumentOutOfRangeException("chunkSize",
        "The chunkSize parameter must be a positive value.");

    // Call the internal implementation.
    return source.ChunkInternal(chunkSize);
}

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

Переходя к ChunkInternal:

private static IEnumerable<IEnumerable<T>> ChunkInternal<T>(
    this IEnumerable<T> source, int chunkSize)
{
    // Validate parameters.
    Debug.Assert(source != null);
    Debug.Assert(chunkSize > 0);

    // Get the enumerator.  Dispose of when done.
    using (IEnumerator<T> enumerator = source.GetEnumerator())
    do
    {
        // Move to the next element.  If there's nothing left
        // then get out.
        if (!enumerator.MoveNext()) yield break;

        // Return the chunked sequence.
        yield return ChunkSequence(enumerator, chunkSize);
    } while (true);
}

В основном, он получает IEnumerator<T> и вручную перебирает каждый элемент. Он проверяет, есть ли какие-либо элементы, которые должны быть перечислены в настоящее время. После перечисления каждого чанка, если не осталось ни одного элемента, он вспыхивает.

Как только он обнаруживает, что в последовательности есть элементы, он делегирует ответственность за внутреннюю IEnumerable<T>реализацию ChunkSequence:

private static IEnumerable<T> ChunkSequence<T>(IEnumerator<T> enumerator, 
    int chunkSize)
{
    // Validate parameters.
    Debug.Assert(enumerator != null);
    Debug.Assert(chunkSize > 0);

    // The count.
    int count = 0;

    // There is at least one item.  Yield and then continue.
    do
    {
        // Yield the item.
        yield return enumerator.Current;
    } while (++count < chunkSize && enumerator.MoveNext());
}

Так как MoveNextон уже был вызван для IEnumerator<T>переданного в ChunkSequence, он возвращает элемент, возвращаемый, Currentа затем увеличивает счетчик, не заботясь о том, чтобы возвращать больше, чем chunkSizeэлементы, и переходя к следующему элементу в последовательности после каждой итерации (но замыкается, если число количество полученных предметов превышает размер куска).

Если элементов больше не осталось, то InternalChunkметод сделает еще один проход во внешнем цикле, но при MoveNextвызове во второй раз он все равно вернет false, согласно документации (выделено мое):

Если MoveNext проходит через конец коллекции, перечислитель располагается после последнего элемента в коллекции, а MoveNext возвращает значение false. Когда перечислитель находится в этой позиции, последующие вызовы MoveNext также возвращают false, пока не будет вызван Reset.

В этот момент цикл разорвется, и последовательность последовательностей прекратится.

Это простой тест:

static void Main()
{
    string s = "agewpsqfxyimc";

    int count = 0;

    // Group by three.
    foreach (IEnumerable<char> g in s.Chunk(3))
    {
        // Print out the group.
        Console.Write("Group: {0} - ", ++count);

        // Print the items.
        foreach (char c in g)
        {
            // Print the item.
            Console.Write(c + ", ");
        }

        // Finish the line.
        Console.WriteLine();
    }
}

Вывод:

Group: 1 - a, g, e,
Group: 2 - w, p, s,
Group: 3 - q, f, x,
Group: 4 - y, i, m,
Group: 5 - c,

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

Кроме того, он будет делать странные вещи, если вы играете с орденом, так же, как Сэм однажды .

casperOne
источник
Я думаю, что это лучшее решение ... единственная проблема в том, что список не имеет длины ... он имеет количество. Но это легко изменить. Мы можем сделать это лучше, даже не создавая списки, а возвращая перечисляемые элементы, содержащие ссылки на основной список с комбинацией смещения / длины. Итак, если размер группы велик, мы не теряем память. Прокомментируйте, если хотите, чтобы я это написал.
Амир
@ Амир, я бы хотел, чтобы это было написано
Самандмур
Это хорошо и быстро - Кэмерон выложил очень похожий вариант после вашего, только предостережение в том, что он буферизует куски, это может привести к нехватке памяти, если куски и размеры элементов велики. Смотрите мой ответ для альтернативного, хотя и гораздо более привлекательного ответа.
Сэм Шафран
@SamSaffron Да, если у вас есть большое количество элементов List<T>, у вас, очевидно, будут проблемы с памятью из-за буферизации. Оглядываясь назад, я должен был отметить это в ответе, но в то время казалось, что основное внимание уделялось слишком многим итерациям. Тем не менее, ваше решение действительно волосатое. Я не проверял это, но теперь мне интересно, есть ли менее волосатое решение.
casperOne
@casperOne да ... Google дал мне эту страницу, когда я искал способ разделить перечислимые значения, для моего конкретного случая использования я разделяю безумно большой список записей, которые возвращаются из БД, если я материализую их в список, который он может взорвать (на самом деле у dapper есть буфер: опция false только для этого варианта использования)
Сэм Саффрон
48

Хорошо, вот мой взгляд на это:

  • полностью ленивый: работает над бесконечным перечислимым
  • нет промежуточного копирования / буферизации
  • O (n) время выполнения
  • работает также, когда внутренние последовательности потребляются только частично

public static IEnumerable<IEnumerable<T>> Chunks<T>(this IEnumerable<T> enumerable,
                                                    int chunkSize)
{
    if (chunkSize < 1) throw new ArgumentException("chunkSize must be positive");

    using (var e = enumerable.GetEnumerator())
    while (e.MoveNext())
    {
        var remaining = chunkSize;    // elements remaining in the current chunk
        var innerMoveNext = new Func<bool>(() => --remaining > 0 && e.MoveNext());

        yield return e.GetChunk(innerMoveNext);
        while (innerMoveNext()) {/* discard elements skipped by inner iterator */}
    }
}

private static IEnumerable<T> GetChunk<T>(this IEnumerator<T> e,
                                          Func<bool> innerMoveNext)
{
    do yield return e.Current;
    while (innerMoveNext());
}

Пример использования

var src = new [] {1, 2, 3, 4, 5, 6}; 

var c3 = src.Chunks(3);      // {{1, 2, 3}, {4, 5, 6}}; 
var c4 = src.Chunks(4);      // {{1, 2, 3, 4}, {5, 6}}; 

var sum   = c3.Select(c => c.Sum());    // {6, 15}
var count = c3.Count();                 // 2
var take2 = c3.Select(c => c.Take(2));  // {{1, 2}, {4, 5}}

Пояснения

Код работает путем вложения двух yieldоснованных итераторов.

Внешний итератор должен отслеживать, сколько элементов было эффективно использовано внутренним (порционным) итератором. Это делается путем закрытия remainingс innerMoveNext(). Неиспользованные элементы чанка отбрасываются до того, как внешний итератор выдаст следующий чанк. Это необходимо, потому что в противном случае вы получите противоречивые результаты, когда внутренние перечисляемые значения не (полностью) потребляются (например c3.Count(), возвращают 6).

Примечание . Ответ был обновлен для устранения недостатков, указанных @aolszowka.

3dGrabber
источник
2
Очень хорошо. Мое «правильное» решение было намного сложнее, чем это. Это ответ № 1 ИМХО.
CaseyB
Это страдает от неожиданного (с точки зрения API) поведения при вызове ToArray (), это также не является потокобезопасным.
aolszowka
@aolszowka: не могли бы вы уточнить?
3dGrabber
@ 3dGrabber Возможно, это было то, как я пересмотрел ваш код (извините, он слишком длинный, чтобы его здесь проделывать, в основном вместо метода расширения, который я передал в sourceEnumerator). Тестовый пример, который я использовал, был чем-то подобным: int [] arrayToSort = new int [] {9, 7, 2, 6, 3, 4, 8, 5, 1, 10, 11, 12, 13}; var source = Chunkify <int> (arrayToSort, 3) .ToArray (); В результате в Source указывается, что было 13 блоков (количество элементов). Это имело смысл для меня, поскольку, если вы не запросите внутренние перечисления, Enumerator не был увеличен.
aolszowka
1
@aolszowka: очень важные пункты. Я добавил предупреждение и раздел об использовании. Код предполагает, что вы перебираете внутреннее перечислимое. С вашим решением вы лишитесь лени. Я думаю, что должно быть возможно получить лучшее из обоих миров с пользовательским кэширующим IEnumerator. Если я найду решение, я
выложу
18

полностью ленивый, не считая и не копируя:

public static class EnumerableExtensions
{

  public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> source, int len)
  {
     if (len == 0)
        throw new ArgumentNullException();

     var enumer = source.GetEnumerator();
     while (enumer.MoveNext())
     {
        yield return Take(enumer.Current, enumer, len);
     }
  }

  private static IEnumerable<T> Take<T>(T head, IEnumerator<T> tail, int len)
  {
     while (true)
     {
        yield return head;
        if (--len == 0)
           break;
        if (tail.MoveNext())
           head = tail.Current;
        else
           break;
     }
  }
}
xtofs
источник
Это решение настолько элегантно, что мне жаль, что я не могу поднять этот ответ более одного раза.
Mark
3
Я не думаю, что это когда-нибудь потерпит неудачу, точно. Но это, безусловно, может иметь странное поведение. Если у вас было 100 наименований, и вы разбили партии по 10, и вы перечислили все партии, не перечислив ни одной из этих партий, у вас
получилось
1
Как упомянул @CaseyB, это страдает от того же сбойного 3dGrabber, на который здесь ссылается stackoverflow.com/a/20953521/1037948 , но это быстро!
drzaus
1
Это прекрасное решение. Делает именно то, что обещает.
Род Хартцелл
Безусловно самое элегантное и конкретное решение. Единственное, вы должны добавить проверку на отрицательные числа и заменить ArgumentNullException на ArgumentException
Romain Vergnory
13

Я думаю, что следующее предложение будет самым быстрым. Я жертвую ленивостью источника Enumerable из-за возможности использовать Array.Copy и заранее знаю продолжительность каждого из моих подсписков.

public static IEnumerable<T[]> Chunk<T>(this IEnumerable<T> items, int size)
{
    T[] array = items as T[] ?? items.ToArray();
    for (int i = 0; i < array.Length; i+=size)
    {
        T[] chunk = new T[Math.Min(size, array.Length - i)];
        Array.Copy(array, i, chunk, 0, chunk.Length);
        yield return chunk;
    }
}
Марк-Андре Бертран
источник
Не только самый быстрый, он также правильно обрабатывает перечисляемые операции над результатом, т.е. items.Chunk (5) .Reverse (). SelectMany (x => x)
тоже
9

Мы можем улучшить решение @ JaredPar для ленивой оценки. Мы используем GroupAdjacentByметод, который выдает группы последовательных элементов с одинаковым ключом:

sequence
.Select((x, i) => new { Value = x, Index = i })
.GroupAdjacentBy(x=>x.Index/3)
.Select(g=>g.Select(x=>x.Value))

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

Полковник паника
источник
8

Я написал метод расширения Clump несколько лет назад. Прекрасно работает, и это самая быстрая реализация здесь. :П

/// <summary>
/// Clumps items into same size lots.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source">The source list of items.</param>
/// <param name="size">The maximum size of the clumps to make.</param>
/// <returns>A list of list of items, where each list of items is no bigger than the size given.</returns>
public static IEnumerable<IEnumerable<T>> Clump<T>(this IEnumerable<T> source, int size)
{
    if (source == null)
        throw new ArgumentNullException("source");
    if (size < 1)
        throw new ArgumentOutOfRangeException("size", "size must be greater than 0");

    return ClumpIterator<T>(source, size);
}

private static IEnumerable<IEnumerable<T>> ClumpIterator<T>(IEnumerable<T> source, int size)
{
    Debug.Assert(source != null, "source is null.");

    T[] items = new T[size];
    int count = 0;
    foreach (var item in source)
    {
        items[count] = item;
        count++;

        if (count == size)
        {
            yield return items;
            items = new T[size];
            count = 0;
        }
    }
    if (count > 0)
    {
        if (count == size)
            yield return items;
        else
        {
            T[] tempItems = new T[count];
            Array.Copy(items, tempItems, count);
            yield return tempItems;
        }
    }
}
Кэмерон МакФарланд
источник
это должно сработать, но оно буферизует 100% кусков, я пытался этого избежать ... но получается невероятно волосатым.
Сэм Шафран
@SamSaffron Да. Особенно, если вы добавите в смесь такие вещи, как plinq, для чего и была моя реализация.
Кэмерон МакФарланд
расширил мой ответ, дайте мне знать, что вы думаете
Сэм Шафран
@CameronMacFarland - можете ли вы объяснить, почему необходима вторая проверка количества == размера? Спасибо.
Дугас
8

System.Interactive предоставляет Buffer()для этой цели. Некоторое быстрое тестирование показывает, что производительность аналогична решению Сэма.

dahlbyk
источник
1
Вы знаете семантику буферизации? Например: если у вас есть перечислитель, который выплевывает строки размером 300 Кб и попытаетесь разбить его на фрагменты размером 10000, у вас будет недостаточно памяти?
Сэм Шафран
Buffer()возвращается, IEnumerable<IList<T>>так что да, у вас, вероятно, есть проблема - она ​​не течет, как у вас.
dahlbyk
7

Вот подпрограмма разделения списка, которую я написал пару месяцев назад:

public static List<List<T>> Chunk<T>(
    List<T> theList,
    int chunkSize
)
{
    List<List<T>> result = theList
        .Select((x, i) => new {
            data = x,
            indexgroup = i / chunkSize
        })
        .GroupBy(x => x.indexgroup, x => x.data)
        .Select(g => new List<T>(g))
        .ToList();

    return result;
}
Эми Б
источник
6

Я нахожу, что этот маленький фрагмент хорошо справляется со своей работой.

public static IEnumerable<List<T>> Chunked<T>(this List<T> source, int chunkSize)
{
    var offset = 0;

    while (offset < source.Count)
    {
        yield return source.GetRange(offset, Math.Min(source.Count - offset, chunkSize));
        offset += chunkSize;
    }
}
erlando
источник
5

Что насчет этого?

var input = new List<string> { "a", "g", "e", "w", "p", "s", "q", "f", "x", "y", "i", "m", "c" };
var k = 3

var res = Enumerable.Range(0, (input.Count - 1) / k + 1)
                    .Select(i => input.GetRange(i * k, Math.Min(k, input.Count - i * k)))
                    .ToList();

Насколько я знаю, GetRange () является линейным с точки зрения количества взятых элементов. Так что это должно хорошо работать.

Роман Пекар
источник
5

Это старый вопрос, но это то, чем я закончил; он перечисляет перечисляемое только один раз, но создает списки для каждого из разделов. Он не страдает от неожиданного поведения при ToArray()вызове, как это делают некоторые реализации:

    public static IEnumerable<IEnumerable<T>> Partition<T>(IEnumerable<T> source, int chunkSize)
    {
        if (source == null)
        {
            throw new ArgumentNullException("source");
        }

        if (chunkSize < 1)
        {
            throw new ArgumentException("Invalid chunkSize: " + chunkSize);
        }

        using (IEnumerator<T> sourceEnumerator = source.GetEnumerator())
        {
            IList<T> currentChunk = new List<T>();
            while (sourceEnumerator.MoveNext())
            {
                currentChunk.Add(sourceEnumerator.Current);
                if (currentChunk.Count == chunkSize)
                {
                    yield return currentChunk;
                    currentChunk = new List<T>();
                }
            }

            if (currentChunk.Any())
            {
                yield return currentChunk;
            }
        }
    }
aolszowka
источник
Было бы хорошо преобразовать это в метод Расширения:public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> source, int chunkSize)
krizzzn
+1 за ваш ответ. Однако я рекомендую две вещи: 1. используйте foreach вместо while и используя block. 2. Передайте chunkSize в конструктор List, чтобы список знал его максимальный ожидаемый размер.
Усман Зафар
4

Мы нашли, что решение Дэвида Б. сработало лучше всего. Но мы адаптировали его к более общему решению:

list.GroupBy(item => item.SomeProperty) 
   .Select(group => new List<T>(group)) 
   .ToArray();
mwjackson
источник
3
Это хорошо, но сильно отличается от того, о чем просил оригинальный аскер.
Эми Б
4

Это следующее решение - самое компактное, которое я мог придумать, это O (n).

public static IEnumerable<T[]> Chunk<T>(IEnumerable<T> source, int chunksize)
{
    var list = source as IList<T> ?? source.ToList();
    for (int start = 0; start < list.Count; start += chunksize)
    {
        T[] chunk = new T[Math.Min(chunksize, list.Count - start)];
        for (int i = 0; i < chunk.Length; i++)
            chunk[i] = list[start + i];

        yield return chunk;
    }
}
Марк-Андре Бертран
источник
4

Старый код, но это то, что я использовал:

    public static IEnumerable<List<T>> InSetsOf<T>(this IEnumerable<T> source, int max)
    {
        var toReturn = new List<T>(max);
        foreach (var item in source)
        {
            toReturn.Add(item);
            if (toReturn.Count == max)
            {
                yield return toReturn;
                toReturn = new List<T>(max);
            }
        }
        if (toReturn.Any())
        {
            yield return toReturn;
        }
    }
Роберт Макки
источник
После публикации я понял, что это в значительной степени тот же код, который был опубликован casperOne 6 лет назад с изменением использования .Any () вместо .Count (), поскольку мне не нужен весь счетчик, просто нужно знать, существует ли он ,
Роберт Макки
3

Если список имеет тип system.collections.generic, вы можете использовать доступный метод «CopyTo» для копирования элементов вашего массива в другие вложенные массивы. Вы указываете начальный элемент и количество элементов для копирования.

Вы также можете сделать 3 клона из своего исходного списка и использовать «RemoveRange» в каждом списке, чтобы уменьшить список до нужного размера.

Или просто создайте вспомогательный метод, который сделает это за вас.

Jobo
источник
2

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

public static IEnumerable<IEnumerable<T>> Chunk<T>(this IEnumerable<T> source, 
                                                   int chunkSize)
{
    if (chunkSize <= 0)
        throw new ArgumentOutOfRangeException($"{nameof(chunkSize)} should be > 0");

    var nbChunks = (int)Math.Ceiling((double)source.Count()/chunkSize);

    return Enumerable.Range(0, nbChunks)
                     .Select(chunkNb => source.Skip(chunkNb*chunkSize)
                     .Take(chunkSize));
}
Bertrand
источник
1
Очень похоже на подход, который я использовал, но я рекомендую, чтобы источник не был IEnumerable. Например, если источник является результатом запроса LINQ, Skip / Take вызовет перечисления nbChunk запроса. Может стать дорогим. Лучше было бы использовать IList или ICollection в качестве типа для источника. Это позволяет избежать проблемы в целом.
РБ Дэвидсон
2

Для всех, кто интересуется упакованным / поддерживаемым решением, библиотека MoreLINQ предоставляет Batchметод расширения, который соответствует вашему запрашиваемому поведению:

IEnumerable<char> source = "Example string";
IEnumerable<IEnumerable<char>> chunksOfThreeChars = source.Batch(3);

BatchРеализация похожа на ответ Камерона MacFarland в , с добавлением перегрузки для преобразования куска / пакет , прежде чем вернуться, и выполняет очень хорошо.

Kevinoid
источник
это должен быть принятый ответ. Вместо того, чтобы изобретать колесо, следует использовать morelinq
Отабек
1

Использование модульного разбиения:

public IEnumerable<IEnumerable<string>> Split(IEnumerable<string> input, int chunkSize)
{
    var chunks = (int)Math.Ceiling((double)input.Count() / (double)chunkSize);
    return Enumerable.Range(0, chunks).Select(id => input.Where(s => s.GetHashCode() % chunks == id));
}
Янош Г.
источник
1

Просто вставляю мои два цента. Если вы хотите «собрать» список (визуализировать слева направо), вы можете сделать следующее:

 public static List<List<T>> Buckets<T>(this List<T> source, int numberOfBuckets)
    {
        List<List<T>> result = new List<List<T>>();
        for (int i = 0; i < numberOfBuckets; i++)
        {
            result.Add(new List<T>());
        }

        int count = 0;
        while (count < source.Count())
        {
            var mod = count % numberOfBuckets;
            result[mod].Add(source[count]);
            count++;
        }
        return result;
    }
mattylantz
источник
1

Другой способ - использование оператора Rx Buffer.

//using System.Linq;
//using System.Reactive.Linq;
//using System.Reactive.Threading.Tasks;

var observableBatches = anAnumerable.ToObservable().Buffer(size);

var batches = aList.ToObservable().Buffer(size).ToList().ToTask().GetAwaiter().GetResult();
frhack
источник
ИМХО самый пупер ответ.
Станислав Берков
1
public static List<List<T>> GetSplitItemsList<T>(List<T> originalItemsList, short number)
    {
        var listGroup = new List<List<T>>();
        int j = number;
        for (int i = 0; i < originalItemsList.Count; i += number)
        {
            var cList = originalItemsList.Take(j).Skip(i).ToList();
            j += number;
            listGroup.Add(cList);
        }
        return listGroup;
    }
Радость чжу
источник
0

Я взял основной ответ и сделал его контейнером IOC, чтобы определить, где разделить. ( Для тех, кто действительно хочет разделить только на 3 пункта, читая этот пост во время поиска ответа? )

Этот метод позволяет разделить на любой тип элемента по мере необходимости.

public static List<List<T>> SplitOn<T>(List<T> main, Func<T, bool> splitOn)
{
    int groupIndex = 0;

    return main.Select( item => new 
                             { 
                               Group = (splitOn.Invoke(item) ? ++groupIndex : groupIndex), 
                               Value = item 
                             })
                .GroupBy( it2 => it2.Group)
                .Select(x => x.Select(v => v.Value).ToList())
                .ToList();
}

Так что для ОП код будет

var it = new List<string>()
                       { "a", "g", "e", "w", "p", "s", "q", "f", "x", "y", "i", "m", "c" };

int index = 0; 
var result = SplitOn(it, (itm) => (index++ % 3) == 0 );
ΩmegaMan
источник
0

Такой перформативный, как подход Сэма Шафрана .

public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> source, int size)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (size <= 0) throw new ArgumentOutOfRangeException(nameof(size), "Size must be greater than zero.");

    return BatchImpl(source, size).TakeWhile(x => x.Any());
}

static IEnumerable<IEnumerable<T>> BatchImpl<T>(this IEnumerable<T> source, int size)
{
    var values = new List<T>();
    var group = 1;
    var disposed = false;
    var e = source.GetEnumerator();

    try
    {
        while (!disposed)
        {
            yield return GetBatch(e, values, group, size, () => { e.Dispose(); disposed = true; });
            group++;
        }
    }
    finally
    {
        if (!disposed)
            e.Dispose();
    }
}

static IEnumerable<T> GetBatch<T>(IEnumerator<T> e, List<T> values, int group, int size, Action dispose)
{
    var min = (group - 1) * size + 1;
    var max = group * size;
    var hasValue = false;

    while (values.Count < min && e.MoveNext())
    {
        values.Add(e.Current);
    }

    for (var i = min; i <= max; i++)
    {
        if (i <= values.Count)
        {
            hasValue = true;
        }
        else if (hasValue = e.MoveNext())
        {
            values.Add(e.Current);
        }
        else
        {
            dispose();
        }

        if (hasValue)
            yield return values[i - 1];
        else
            yield break;
    }
}

}

leandromoh
источник
0

Может работать с бесконечными генераторами:

a.Zip(a.Skip(1), (x, y) => Enumerable.Repeat(x, 1).Concat(Enumerable.Repeat(y, 1)))
 .Zip(a.Skip(2), (xy, z) => xy.Concat(Enumerable.Repeat(z, 1)))
 .Where((x, i) => i % 3 == 0)

Демо-код: https://ideone.com/GKmL7M

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

public class Test
{
  private static void DoIt(IEnumerable<int> a)
  {
    Console.WriteLine(String.Join(" ", a));

    foreach (var x in a.Zip(a.Skip(1), (x, y) => Enumerable.Repeat(x, 1).Concat(Enumerable.Repeat(y, 1))).Zip(a.Skip(2), (xy, z) => xy.Concat(Enumerable.Repeat(z, 1))).Where((x, i) => i % 3 == 0))
      Console.WriteLine(String.Join(" ", x));

    Console.WriteLine();
  }

  public static void Main()
  {
    DoIt(new int[] {1});
    DoIt(new int[] {1, 2});
    DoIt(new int[] {1, 2, 3});
    DoIt(new int[] {1, 2, 3, 4});
    DoIt(new int[] {1, 2, 3, 4, 5});
    DoIt(new int[] {1, 2, 3, 4, 5, 6});
  }
}
1

1 2

1 2 3
1 2 3

1 2 3 4
1 2 3

1 2 3 4 5
1 2 3

1 2 3 4 5 6
1 2 3
4 5 6

Но на самом деле я бы предпочел написать соответствующий метод без linq.

Qwertiy
источник
0

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

Ex. список сообщений.

 List<dynamic> messages = new List<dynamic>
        {
            new { FcntUp = 101, CommTimestamp = "2019-01-01 00:00:01" },
            new { FcntUp = 102, CommTimestamp = "2019-01-01 00:00:02" },
            new { FcntUp = 103, CommTimestamp = "2019-01-01 00:00:03" },

            //restart of sequence
            new { FcntUp = 1, CommTimestamp = "2019-01-01 00:00:04" },
            new { FcntUp = 2, CommTimestamp = "2019-01-01 00:00:05" },
            new { FcntUp = 3, CommTimestamp = "2019-01-01 00:00:06" },

            //restart of sequence
            new { FcntUp = 1, CommTimestamp = "2019-01-01 00:00:07" },
            new { FcntUp = 2, CommTimestamp = "2019-01-01 00:00:08" },
            new { FcntUp = 3, CommTimestamp = "2019-01-01 00:00:09" }
        };

Я хочу разделить список на отдельные списки, поскольку счетчик перезапускается. Вот код:

var arraylist = new List<List<dynamic>>();

        List<dynamic> messages = new List<dynamic>
        {
            new { FcntUp = 101, CommTimestamp = "2019-01-01 00:00:01" },
            new { FcntUp = 102, CommTimestamp = "2019-01-01 00:00:02" },
            new { FcntUp = 103, CommTimestamp = "2019-01-01 00:00:03" },

            //restart of sequence
            new { FcntUp = 1, CommTimestamp = "2019-01-01 00:00:04" },
            new { FcntUp = 2, CommTimestamp = "2019-01-01 00:00:05" },
            new { FcntUp = 3, CommTimestamp = "2019-01-01 00:00:06" },

            //restart of sequence
            new { FcntUp = 1, CommTimestamp = "2019-01-01 00:00:07" },
            new { FcntUp = 2, CommTimestamp = "2019-01-01 00:00:08" },
            new { FcntUp = 3, CommTimestamp = "2019-01-01 00:00:09" }
        };

        //group by FcntUp and CommTimestamp
        var query = messages.GroupBy(x => new { x.FcntUp, x.CommTimestamp });

        //declare the current item
        dynamic currentItem = null;

        //declare the list of ranges
        List<dynamic> range = null;

        //loop through the sorted list
        foreach (var item in query)
        {
            //check if start of new range
            if (currentItem == null || item.Key.FcntUp < currentItem.Key.FcntUp)
            {
                //create a new list if the FcntUp starts on a new range
                range = new List<dynamic>();

                //add the list to the parent list
                arraylist.Add(range);
            }

            //add the item to the sublist
            range.Add(item);

            //set the current item
            currentItem = item;
        }
Claes-Philip Staiger
источник
-1

Чтобы вставить мои два цента ...

Используя тип списка для источника, который будет разбит на части, я нашел другое очень компактное решение:

public static IEnumerable<IEnumerable<TSource>> Chunk<TSource>(this IEnumerable<TSource> source, int chunkSize)
{
    // copy the source into a list
    var chunkList = source.ToList();

    // return chunks of 'chunkSize' items
    while (chunkList.Count > chunkSize)
    {
        yield return chunkList.GetRange(0, chunkSize);
        chunkList.RemoveRange(0, chunkSize);
    }

    // return the rest
    yield return chunkList;
}
Патрик
источник