Podziel listę na listy podrzędne za pomocą LINQ


377

Czy jest jakiś sposób na podzielenie a List<SomeObject>na kilka osobnych list SomeObject, używając indeksu pozycji jako ogranicznika każdego podziału?

Pozwól, że zilustruję:

Mam List<SomeObject>i ja potrzebujemy List<List<SomeObject>>lub List<SomeObject>[], tak że każdy z tych wynikających list będzie zawierał grupę 3 sztuk na pierwotnej liście (kolejno).

na przykład.:

  • Oryginalna lista: [a, g, e, w, p, s, q, f, x, y, i, m, c]

  • Listy wynikowe: [a, g, e], [w, p, s], [q, f, x], [y, i, m], [c]

Potrzebowałbym również wynikowego rozmiaru list, aby był parametrem tej funkcji.

Odpowiedzi:


378

Wypróbuj następujący kod.

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();
}

Chodzi o to, aby najpierw pogrupować elementy według indeksów. Dzielenie przez trzy daje efekt grupując je w grupach po 3. Następnie przekształcić każdą grupę z listy i IEnumerableod Listdo A Listod Lists


21
GroupBy wykonuje niejawne sortowanie. To może zabić wydajność. Potrzebujemy pewnego rodzaju odwrotności SelectMany.
yfeldblum

5
@ Justice, GroupBy może być zaimplementowany przez mieszanie. Skąd wiesz, że wdrożenie GroupBy „może zabić wydajność”?
Amy B

5
GroupBy nic nie zwraca, dopóki nie wyliczy wszystkich elementów. Dlatego jest wolny. Listy, które chce OP, są ciągłe, więc lepsza metoda może dać pierwszą podlistę [a,g,e]przed wyliczeniem oryginalnej listy.
Pułkownik Panic

9
Weź ekstremalny przykład nieskończonej IEnumerable. GroupBy(x=>f(x)).First()nigdy nie da grupy. OP zapytał o listy, ale jeśli piszemy do pracy z IEnumerable, wykonując tylko jedną iterację, czerpiemy przewagę wydajności.
Pułkownik Panic

8
@Nick Order nie jest jednak zachowywany na twój sposób. Warto wiedzieć, ale należy je grupować w (0,3,6,9, ...), (1,4,7,10, ...), (2,5,8 , 11, ...). Jeśli kolejność nie ma znaczenia, to jest w porządku, ale w tym przypadku wygląda na to, że ma znaczenie.
Reafexus,

325

To pytanie jest trochę stare, ale właśnie to napisałem i myślę, że jest nieco bardziej eleganckie niż inne proponowane rozwiązania:

/// <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);
    }
}

14
Uwielbiam to rozwiązanie. Polecam dodanie tej kontroli poczytalności, aby zapobiec nieskończonej pętli: if (chunksize <= 0) throw new ArgumentException("Chunk size must be greater than zero.", "chunksize");
złamanie

10
Podoba mi się to, ale nie jest super wydajne
Sam Saffron

51
Podoba mi się ten, ale efektywność czasowa jest O(n²). Możesz iterować po liście i mieć O(n)czas.
hIpPy

8
@ hIpPy, jak to jest n ^ 2? Wydaje mi się liniowy
Vivek Maharajh,

13
@vivekmaharajh sourceza IEnumerablekażdym razem zastępowane jest opakowaniem . Więc pobieranie elementów sourceprzechodzi przez warstwy Skips
Lasse Espeholt

99

Ogólnie rzecz biorąc, podejście sugerowane przez CaseyB działa dobrze, w rzeczywistości, jeśli przechodzisz List<T>, trudno go winić, być może zmieniłbym to na:

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;
   }
}

Co pozwoli uniknąć masowych łańcuchów połączeń. Niemniej jednak podejście to ma ogólną wadę. Zmaterializuje dwa wyliczenia na porcję, aby podkreślić problem, spróbuj uruchomić:

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

Aby przezwyciężyć ten problem, możemy wypróbować podejście Camerona , które przechodzi powyższy test w żywych kolorach, ponieważ chodzi o wyliczenie tylko raz.

Problem polega na tym, że ma inną wadę, materializuje każdy przedmiot w każdym kawałku, problem z tym podejściem polega na tym, że zabrakło ci pamięci.

Aby to zilustrować, spróbuj uruchomić:

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

Wreszcie każda implementacja powinna być w stanie obsłużyć iterację porcji poza kolejnością, na przykład:

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

Wiele wysoce optymalnych rozwiązań, takich jak moja pierwsza wersja tej odpowiedzi, zawiodło. Ten sam problem można znaleźć w zoptymalizowanej odpowiedzi casperOne .

Aby rozwiązać wszystkie te problemy, możesz użyć:

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();


        }

    }
}

Istnieje również runda optymalizacji, które można wprowadzić w celu iteracji porcji poza kolejnością, co jest tutaj poza zakresem.

Jaką metodę wybrać? Zależy to całkowicie od problemu, który próbujesz rozwiązać. Jeśli nie przejmujesz się pierwszą wadą, prosta odpowiedź jest niezwykle atrakcyjna.

Uwaga: jak w przypadku większości metod, nie jest to bezpieczne w przypadku wielowątkowości, rzeczy mogą stać się dziwne, jeśli chcesz, aby wątek był bezpieczny, musisz wprowadzić poprawki EnumeratorWrapper.


Czy błąd byłby Enumerable.Range (0, 100) .Chunk (3) .Reverse (). ToArray () jest błędny lub Enumerable.Range (0, 100) .ToArray (). Chunk (3) .Reverse () .ToArray () zgłasza wyjątek?
Cameron MacFarland

@SamSaffron Zaktualizowałem moją odpowiedź i znacznie uprościłem kod ze względu na to, co według mnie jest najważniejszym przypadkiem użycia (i potwierdzam zastrzeżenia).
casperOne

Co z chunckowaniem IQueryable <>? Domyślam się, że podejście Take / Skip byłoby optymalne, jeśli chcemy przekazać maksimum operacji dostawcy
Guillaume86

@ Guillaume86 Zgadzam się, jeśli masz IList lub IQueryable, możesz zastosować wiele rodzajów skrótów, które znacznie by to przyspieszyły (Linq robi to wewnętrznie dla wszystkich innych metod)
Sam Saffron

1
To zdecydowanie najlepsza odpowiedź na wydajność. Mam problem z użyciem SqlBulkCopy z IEnumerable, który uruchamia dodatkowe procesy w każdej kolumnie, więc musi działać wydajnie tylko z jednym przejściem. Pozwoli mi to podzielić IEnumerable na porcje o zarządzalnej wielkości. (Dla tych, którzy zastanawiają się, włączyłem tryb przesyłania strumieniowego SqlBulkCopy, który wydaje się być zepsuty).
Brain2000 30.03.16

64

Państwo mogli korzystać z wielu pytań, które używają TakeiSkip , ale to byłoby zbyt wielu iteracji na pierwotnej liście, wierzę.

Uważam raczej, że powinieneś stworzyć własny iterator, taki jak:

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;
   }
}

Następnie możesz to wywołać, a funkcja LINQ jest włączona, dzięki czemu możesz wykonywać inne operacje na wynikowych sekwencjach.


W świetle odpowiedzi Sama czułem, że istnieje łatwiejszy sposób na zrobienie tego bez:

  • Powtarzam ponownie listę (czego początkowo nie robiłem)
  • Zmaterializowanie przedmiotów w grupach przed uwolnieniem fragmentu (w przypadku dużych fragmentów elementów wystąpiłyby problemy z pamięcią)
  • Cały kod opublikowany przez Sama

To powiedziawszy, oto kolejna przepustka, którą skodyfikowałem metodą rozszerzenia do IEnumerable<T>wywołania 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);
}

Nic dziwnego, tylko podstawowe sprawdzanie błędów.

Przechodząc do 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);
}

Zasadniczo dostaje IEnumerator<T> i ręcznie iteruje każdy element. Sprawdza, czy są jakieś elementy do wyliczenia. Po wyliczeniu każdego fragmentu, jeśli nie ma już żadnych elementów, wybucha.

Po wykryciu elementów w sekwencji przekazuje odpowiedzialność za IEnumerable<T>implementację wewnętrzną do 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());
}

Ponieważ MoveNextzostał już przywołany do IEnumerator<T>przekazanego ChunkSequence, zwraca przedmiot o, Currenta następnie zwiększa liczbę, upewniając się, że nigdy nie zwróci więcej niżchunkSize elementów i przechodzi do następnego elementu w sekwencji po każdej iteracji (ale jest zwarty, jeśli liczba uzyskane elementy przekraczają rozmiar porcji).

Jeśli nie pozostały żadne elementy, InternalChunkmetoda wykona kolejne przejście w zewnętrznej pętli, ale gdy MoveNextzostanie wywołana po raz drugi, nadal zwróci false, zgodnie z dokumentacją (moje wyróżnienie):

Jeśli MoveNext minie koniec kolekcji, moduł wyliczający jest ustawiany za ostatnim elementem w kolekcji, a MoveNext zwraca false. Gdy moduł wyliczający znajduje się w tej pozycji, kolejne wywołania MoveNext również zwracają wartość false, dopóki nie zostanie wywołane polecenie Reset.

W tym momencie pętla pęknie, a sekwencja sekwencji zakończy się.

To jest prosty test:

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();
    }
}

Wynik:

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

Ważna uwaga, to nie zadziała, jeśli nie wyczerpiesz całej sekwencji potomnej lub nie przerwiesz jej w żadnym punkcie sekwencji rodzicielskiej. Jest to ważne zastrzeżenie, ale jeśli twój przypadek użycia jest taki, że zużyjesz każdy element sekwencji sekwencji, to zadziała dla ciebie.

Dodatkowo, będzie to robić dziwne rzeczy, jeśli będziesz grał z rozkazem, tak jak zrobił to Sam w pewnym momencie .


Myślę, że to najlepsze rozwiązanie ... jedynym problemem jest to, że lista nie ma długości ... ma liczbę. Ale łatwo to zmienić. Możemy to poprawić, nawet nie konstruując List, ale zwracając ienumerables, które zawierają odniesienia do głównej listy z kombinacją przesunięcia / długości. Jeśli więc rozmiar grupy jest duży, nie marnujemy pamięci. Skomentuj, jeśli chcesz, żebym to napisał.
Amir,

@Amir Chciałbym zobaczyć to spisane
samandmoore

Jest to przyjemne i szybkie - Cameron opublikował również bardzo podobny po twoim, z zastrzeżeniem, że buforuje fragmenty, może to prowadzić do braku pamięci, jeśli fragmenty i rozmiary przedmiotów są duże. Zobacz moją odpowiedź na alternatywną, choć znacznie bardziej włochatą odpowiedź.
Sam Saffron

@SamSaffron Tak, jeśli masz dużą liczbę elementów List<T>, oczywiście będziesz mieć problemy z pamięcią z powodu buforowania. Z perspektywy czasu powinienem był to zauważyć w odpowiedzi, ale wydawało się, że w tamtym czasie koncentrowano się na zbyt wielu iteracjach. To powiedziawszy, twoje rozwiązanie jest rzeczywiście bardziej włochate. Nie testowałem tego, ale teraz zastanawiam się, czy istnieje mniej owłosione rozwiązanie.
casperOne

@casperOne tak ... Google dał mi tę stronę, gdy szukałem sposobu na podzielenie elementów wyliczeniowych, w moim konkretnym przypadku użycia dzielę niesamowicie dużą listę rekordów, które są zwracane z bazy danych, jeśli zmaterializuję je w lista, która wybuchłaby (w rzeczywistości dapper ma bufor: opcja false tylko dla tego przypadku użycia)
Sam Saffron

48

Ok, oto moje zdanie na ten temat:

  • całkowicie leniwy: działa na nieskończonych wyliczeniach
  • bez pośredniego kopiowania / buforowania
  • O (n) czas wykonania
  • działa również, gdy sekwencje wewnętrzne są tylko częściowo zużywane

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());
}

Przykładowe użycie

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}}

Objaśnienia

Kod działa poprzez zagnieżdżenie dwóch yield iteratorów opartych na.

Zewnętrzny iterator musi śledzić, ile elementów zostało skutecznie pochłoniętych przez wewnętrzny (fragment) iterator. Odbywa się to poprzez zamknięcie za remainingpomocą innerMoveNext(). Niewykorzystane elementy fragmentu są odrzucane, zanim następny fragment zostanie podany przez zewnętrzny iterator. Jest to konieczne, ponieważ w przeciwnym razie otrzymujesz niespójne wyniki, gdy wewnętrzne wyliczenia nie zostaną (całkowicie) wykorzystane (np. c3.Count()Zwrócą 6).

Uwaga: odpowiedź została zaktualizowana w celu usunięcia niedociągnięć wskazanych przez @aolszowka.


2
Bardzo dobrze. Moje „prawidłowe” rozwiązanie było o wiele bardziej skomplikowane. To jest odpowiedź nr 1 IMHO.
CaseyB

Występuje to z powodu nieoczekiwanego (z punktu widzenia API) zachowania, gdy wywoływana jest funkcja ToArray (), nie jest również bezpieczna dla wątków.
aolszówka

@aolszowka: czy mógłbyś prosić o rozwinięcie?
3dGrabber

@ 3dGrabber Być może właśnie w ten sposób ponownie rozważyłem twój kod (przepraszam, że jest tu trochę za długo, aby go pominąć, w zasadzie zamiast metody rozszerzenia podanej w sourceEnumerator). Przypadek testowy, który zastosowałem, był coś takiego: int [] arrayToSort = new int [] {9, 7, 2, 6, 3, 4, 8, 5, 1, 10, 11, 12, 13}; var source = Chunkify <int> (arrayToSort, 3) .ToArray (); Wynikło ze źródła wskazującego, że było 13 fragmentów (liczba elementów). Ma to dla mnie sens, ponieważ jeśli nie zapytałeś wewnętrznych wyliczeń, których nie wyliczał Enumerator.
aolszówka

1
@aolszowka: bardzo ważne punkty. Dodałem sekcję ostrzeżenia i użytkowania. Kod zakłada, że ​​wykonujesz iterację po wewnętrznej wyliczalności. Dzięki swojemu rozwiązaniu tracisz lenistwo. Myślę, że powinno być możliwe uzyskanie najlepszego z obu światów za pomocą niestandardowego, buforującego IEnumeratora. Jeśli znajdę rozwiązanie, opublikuję je tutaj ...
3dGrabber

18

całkowicie leniwy, bez liczenia i kopiowania:

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;
     }
  }
}

To rozwiązanie jest tak eleganckie, że przepraszam, że nie mogę głosować za odpowiedzią więcej niż raz.
Mark

3
Nie sądzę, żeby to kiedykolwiek zawiodło. Ale z pewnością może mieć dziwne zachowanie. Jeśli miałbyś 100 przedmiotów i podzieliłeś się na partie po 10, i zliczyłeś wszystkie partie bez wyliczenia żadnych pozycji z tych partii, skończyłbyś z 100 partiami po 1
CaseyB

1
Jak wspomniał @CaseyB, cierpi to z powodu tego samego niepowodzenia 3dGrabber, o którym mowa tutaj stackoverflow.com/a/20953521/1037948 , ale człowiek jest szybki!
drzaus

1
To jest piękne rozwiązanie. Robi dokładnie to, co obiecuje.
Rod Hartzell

Zdecydowanie najbardziej eleganckie i praktyczne rozwiązanie. Jedyną rzeczą jest, należy dodać kontrolę liczb ujemnych i zastąpić ArgumentNullException przez ArgumentException
Romain Vergnory

13

Myślę, że następująca sugestia byłaby najszybsza. Poświęcam lenistwo źródła Enumerable ze względu na możliwość korzystania z Array.Copy i znajomość z góry długości każdej z moich podlist.

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;
    }
}

Nie tylko najszybszy, ale także poprawnie obsługuje dalsze wyliczalne operacje na wyniku, tj. Items.Chunk (5) .Reverse (). SelectMany (x => x)
zbyt

9

Możemy ulepszyć rozwiązanie @ JaredPar, aby przeprowadzić prawdziwie leniwą ocenę. Używamy GroupAdjacentBymetody, która daje grupy kolejnych elementów z tym samym kluczem:

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

Ponieważ grupy są uzyskiwane jeden po drugim, to rozwiązanie działa skutecznie z długimi lub nieskończonymi sekwencjami.


8

Kilka lat temu napisałem metodę rozszerzenia Clumpa. Działa świetnie i jest najszybszą implementacją tutaj. : 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;
        }
    }
}

powinien działać, ale buforuje 100% fragmentów, starałem się tego uniknąć ... ale okazuje się, że jest niesamowicie owłosiony.
Sam Saffron

@SamSaffron Yep. Zwłaszcza jeśli wrzucisz do miksu rzeczy takie jak plinq, do czego pierwotnie służyła moja implementacja.
Cameron MacFarland

poszerzyłem moją odpowiedź, daj mi znać, co myślisz
Sam Saffron

@CameronMacFarland - czy możesz wyjaśnić, dlaczego konieczne jest drugie sprawdzenie licznika == rozmiar? Dzięki.
dugas

8

System.Interactive zapewnia Buffer()w tym celu. Niektóre szybkie testy pokazują, że wydajność jest podobna do rozwiązania Sama.


1
znasz semantykę buforowania? np .: jeśli masz moduł wyliczający, który wyrzuca łańcuchy o wielkości 300 000 i próbuje podzielić go na fragmenty o wielkości 10 000, czy zabraknie ci pamięci?
Sam Saffron

Buffer()zwraca, IEnumerable<IList<T>>więc tak, prawdopodobnie miałbyś problem - nie działa tak jak twój.
dahlbyk

7

Oto procedura podziału listy, którą napisałem kilka miesięcy temu:

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

Uważam, że ten krótki fragment całkiem dobrze sobie radzi.

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;
    }
}

5

A co z tym?

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();

O ile mi wiadomo, GetRange () jest liniowy pod względem liczby pobranych elementów. To powinno działać dobrze.


5

To stare pytanie, ale z tym skończyłem; wylicza wyliczalny tylko raz, ale tworzy listy dla każdej partycji. Nie jest narażony na nieoczekiwane zachowanie, gdy ToArray()jest wywoływany, podobnie jak niektóre implementacje:

    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;
            }
        }
    }

Dobrze byłoby przekonwertować to na metodę rozszerzenia:public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> source, int chunkSize)
krizzzn

+1 za twoją odpowiedź. Polecam jednak dwie rzeczy: 1. używaj foreach zamiast while i block. 2. Przekaż chunkSize do konstruktora List, aby lista znała swój maksymalny oczekiwany rozmiar.
Usman Zafar

4

Okazało się, że rozwiązanie Davida B. działało najlepiej. Ale dostosowaliśmy go do bardziej ogólnego rozwiązania:

list.GroupBy(item => item.SomeProperty) 
   .Select(group => new List<T>(group)) 
   .ToArray();

3
To miłe, ale zupełnie inne niż to, o co prosił pierwotny pytający.
Amy B

4

Poniższe rozwiązanie jest najbardziej kompaktowe, jakie mogłem wymyślić, czyli 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

Stary kod, ale tego właśnie używałem:

    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;
        }
    }

Po opublikowaniu, zdałem sobie sprawę, że jest to dokładnie ten sam kod napisany przez casperOne 6 lat temu, ze zmianą użycia .Any () zamiast .Count (), ponieważ nie potrzebuję całej liczby, po prostu muszę wiedzieć, czy istnieje .
Robert McKee,

3

Jeśli lista jest typu system.collections.generic, możesz skorzystać z dostępnej metody „CopyTo”, aby skopiować elementy tablicy na inne tablice podrzędne. Określ element początkowy i liczbę elementów do skopiowania.

Możesz także zrobić 3 klony z oryginalnej listy i użyć „RemoveRange” na każdej liście, aby zmniejszyć listę do pożądanego rozmiaru.

Lub po prostu stwórz metodę pomocniczą, aby zrobić to za Ciebie.


2

To stare rozwiązanie, ale miałem inne podejście. Używam, Skipaby przejść do pożądanego przesunięcia i Takewyodrębnić pożądaną liczbę elementów:

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));
}

1
Bardzo podobne do zastosowanego przeze mnie podejścia, ale zalecam, aby źródło nie było IEnumerable. Na przykład, jeśli źródło jest wynikiem zapytania LINQ, Skip / Take uruchomi wyliczenia nbChunk zapytania. Może stać się drogi. Lepiej byłoby użyć IList lub ICollection jako typu źródła. To całkowicie eliminuje problem.
RB Davidson

2

Dla wszystkich zainteresowanych pakietem / utrzymywanym rozwiązaniem biblioteka MoreLINQ zapewnia Batchmetodę rozszerzenia pasującą do żądanego zachowania:

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

BatchRealizacja jest podobna do odpowiedzi Cameron MacFarland za , z dodatkiem przeciążenia dla przekształcenia klocek / partię przed powrotem i wykonuje całkiem dobrze.


to powinna być zaakceptowana odpowiedź. Zamiast wynaleźć koło na nowo, należy użyć
morelinq

1

Korzystanie z partycjonowania modułowego:

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

Właśnie włożyłem moje dwa centy. Jeśli chcesz „wstawić” listę (wizualizować od lewej do prawej), możesz wykonać następujące czynności:

 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;
    }

1

Innym sposobem jest użycie operatora bufora Rx

//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();

IMHO najbardziej niepoprawna odpowiedź.
Stanislav Berkov 21.04.19

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

Przyjąłem pierwotną odpowiedź i postanowiłem, że jest to pojemnik MKOl, aby ustalić, gdzie podzielić. ( Bo kto tak naprawdę chce podzielić tylko na 3 elementy, czytając ten post podczas szukania odpowiedzi? )

Ta metoda pozwala na podział na dowolny typ przedmiotu w razie potrzeby.

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();
}

Tak więc dla OP kod byłby

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 );

0

Tak spektakularne, jak podejście Sama Saffrona .

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;
    }
}

}


0

Może współpracować z nieskończonymi generatorami:

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)

Kod demonstracyjny: 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

Ale tak naprawdę wolałbym pisać odpowiednią metodę bez linq.


0

Spójrz na to! Mam listę elementów z licznikiem sekwencji i datą. Za każdym razem, gdy sekwencja uruchamia się ponownie, chcę utworzyć nową listę.

Dawny. lista wiadomości.

 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" }
        };

Chcę podzielić listę na osobne listy, gdy licznik uruchomi się ponownie. Oto kod:

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;
        }

-1

Aby wstawić moje dwa centy ...

Korzystając z typu listy dla fragmentu źródła, znalazłem inne bardzo kompaktowe rozwiązanie:

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;
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.