Разделить список на подсписки с помощью LINQ - PullRequest
352 голосов
/ 07 января 2009

Можно ли как-нибудь разделить 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]

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

Ответы [ 27 ]

345 голосов
/ 07 января 2009

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

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. Затем преобразуйте каждую группу в список и IEnumerable из List в List из List s

300 голосов
/ 15 июня 2011

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

/// <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);
    }
}
93 голосов
/ 03 мая 2012

В целом подход, предложенный 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.

64 голосов
/ 07 января 2009

Вы можете использовать несколько запросов, которые используют 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 возвращает ложь Когда счетчик находится в этой позиции, последующие вызовы 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,

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

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

45 голосов
/ 06 января 2014

Хорошо, вот мое мнение:

  • полностью ленивый: работает с бесконечными перечислимыми
  • нет промежуточного копирования / буферизации
  • 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.

14 голосов
/ 23 февраля 2015

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

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;
     }
  }
}
12 голосов
/ 20 сентября 2014

Я думаю, что следующее предложение будет самым быстрым. Я жертвую ленивостью источника 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;
    }
}
9 голосов
/ 12 июля 2012

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

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

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

8 голосов
/ 03 мая 2012

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

8 голосов
/ 03 мая 2012

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

/// <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;
        }
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...