460 votes

Diviser une liste en sous-listes avec LINQ

Y a-t-il un moyen de séparer un List<SomeObject> en plusieurs listes distinctes de SomeObject en utilisant l'index de l'élément comme délimiteur de chaque fractionnement ?

Laissez-moi vous donner un exemple :

J'ai un List<SomeObject> et j'ai besoin d'un List<List<SomeObject>> o List<SomeObject>[] de sorte que chacune de ces listes résultantes contienne un groupe de 3 éléments de la liste originale (séquentiellement).

eg. :

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

  • Listes de résultats : [a, g, e], [w, p, s], [q, f, x], [y, i, m], [c]

J'aurais également besoin que la taille des listes résultantes soit un paramètre de cette fonction.

440voto

JaredPar Points 333733

Essayez le code suivant.

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

L'idée est d'abord de regrouper les éléments par index. La division par trois a pour effet de les regrouper par groupes de 3. Ensuite, on convertit chaque groupe en une liste et on utilise la fonction IEnumerable de List à un List de List s

32 votes

GroupBy effectue un tri implicite. Cela peut nuire aux performances. Ce dont nous avons besoin est une sorte d'inverse de SelectMany.

3 votes

@Justice, ce serait bien d'avoir un système de partitionnement intégré pour IEnumerable.

0 votes

@JaredPar Vous pouvez le faire assez facilement avec une méthode d'extension. Je soupçonne que ce n'est pas là, en partie, parce que cela ne s'intègre pas bien avec SQL. La méthode 'myEnumerable.InGroupsOf(3).Select(subEnumerable => subEnumerable.Sum()).Average()' plus des surcharges serait bien.

388voto

CaseyB Points 1709

Je viens d'écrire ceci, et je pense que c'est un peu plus élégant que les autres solutions proposées :

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

15 votes

J'adore cette solution. Je recommanderais d'ajouter ce contrôle d'intégrité pour éviter une boucle infinie : if (chunksize <= 0) throw new ArgumentException("Chunk size must be greater than zero.", "chunksize");

14 votes

J'aime bien, mais ce n'est pas très efficace.

0 votes

J'ai implémenté ma méthode de chunking IQueryable<> de cette façon, sauf que j'ai fait un Count() pour éviter n-1 .Any(). Je suppose que l'implémentation optimale dépend du contexte dans lequel sont utilisés les IQueryables (dans mon cas, il s'agit de frapper une base de données avec LINQ to SQL).

122voto

Sam Saffron Points 56236

En général, l'approche suggérée par CaseyB fonctionne très bien, en fait si vous passez dans une List<T> il est difficile de le critiquer, peut-être que je le changerais en :

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

Ce qui évitera les chaînes d'appels massives. Néanmoins, cette approche présente un défaut général. Elle matérialise deux énumérations par chunk, pour mettre en évidence le problème essayer de courir :

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

Pour surmonter cela, nous pouvons essayer Cameron qui passe le test ci-dessus haut la main puisqu'elle ne parcourt l'énumération qu'une seule fois.

Le problème est qu'il a un défaut différent, il matérialise chaque élément dans chaque chunk, le problème avec cette approche est que vous avez besoin de beaucoup de mémoire.

Pour illustrer cela, essayez d'exécuter :

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

Enfin, toute implémentation doit être capable de gérer l'itération désordonnée des morceaux, par exemple :

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

De nombreuses solutions hautement optimales comme ma première révision de cette réponse y a échoué. Le même problème peut être observé dans optimisé par casperOne réponse.

Pour résoudre tous ces problèmes, vous pouvez utiliser les moyens suivants :

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

        }

    }
}

Il existe également une série d'optimisations que l'on pourrait introduire pour l'itération hors ordre des morceaux, ce qui est hors de portée ici.

Quant à savoir quelle méthode vous devriez choisir ? Cela dépend totalement du problème que vous essayez de résoudre. Si vous n'êtes pas concerné par le premier défaut, la réponse simple est incroyablement attrayante.

Note comme avec la plupart des méthodes, cette méthode n'est pas sûre pour le multi threading, les choses peuvent devenir bizarres si vous souhaitez la rendre sûre pour le threading, vous devrez modifier EnumeratorWrapper .

0 votes

Le bug serait-il dû au fait que Enumerable.Range(0, 100).Chunk(3).Reverse().ToArray() est erroné, ou que Enumerable.Range(0, 100).ToArray().Chunk(3).Reverse().ToArray() lève une exception ?

0 votes

@SamSaffron J'ai mis à jour ma réponse et simplifié énormément le code pour ce qui me semble être le cas d'utilisation le plus important (et je reconnais les avertissements).

0 votes

Qu'en est-il du découpage de IQueryable<> ? Je pense qu'une approche Take/Skip serait optimale si nous voulons déléguer un maximum d'opérations au fournisseur.

72voto

casperOne Points 49736

Vous pourrait utiliser un certain nombre de requêtes qui utilisent Take y Skip mais cela ajouterait trop d'itérations à la liste originale, je crois.

Je pense plutôt que vous devriez créer votre propre itérateur, comme ceci :

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

Vous pouvez ensuite l'appeler et il est activé par LINQ afin que vous puissiez effectuer d'autres opérations sur les séquences résultantes.


À la lumière de Réponse de Sam j'ai senti qu'il y avait un moyen plus facile de le faire sans :

  • Répétition de l'itération dans la liste (ce que je n'ai pas fait à l'origine).
  • matérialiser les éléments en groupes avant de libérer le morceau (pour les gros morceaux d'éléments, il y aurait des problèmes de mémoire)
  • Tout le code que Sam a posté

Ceci étant dit, voici une autre passe, que j'ai codifiée dans une méthode d'extension à IEnumerable<T> appelé Chunk :

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

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

Rien de surprenant là-dedans, juste une vérification basique des erreurs.

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

Fondamentalement, il obtient le IEnumerator<T> et itère manuellement à travers chaque élément. Il vérifie s'il y a encore des éléments à énumérer. Après l'énumération de chaque morceau, s'il n'y a plus d'éléments, il s'interrompt.

Dès qu'il détecte la présence d'éléments dans la séquence, il délègue la responsabilité de l'exécution de la séquence interne. IEnumerable<T> mise en œuvre pour 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());
}

Depuis MoveNext a déjà été appelé sur le IEnumerator<T> transmis à ChunkSequence il donne l'élément retourné par Current et incrémente ensuite le compte, en s'assurant de ne jamais retourner plus de chunkSize et de passer à l'élément suivant de la séquence après chaque itération (mais court-circuité si le nombre d'éléments obtenus dépasse la taille du morceau).

S'il n'y a plus d'éléments, alors le InternalChunk fera un autre passage dans la boucle externe, mais lorsque la méthode MoveNext est appelé une seconde fois, il retournera toujours false, selon la documentation (c'est moi qui souligne) :

Si MoveNext dépasse la fin de la collection, l'énumérateur est positionné après le dernier élément de la collection et MoveNext retourne faux. Lorsque l'énumérateur se trouve à cette position, les suivantes appels à MoveNext renvoient également false jusqu'à ce que Reset soit appelé.

À ce stade, la boucle se brise et la séquence de séquences se termine.

Il s'agit d'un test simple :

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

Sortie :

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

Une note importante, ceci no fonctionnent si vous ne drainez pas toute la séquence enfant ou si vous vous arrêtez à un point quelconque de la séquence parent. Il s'agit d'une mise en garde importante, mais si votre cas d'utilisation est que vous consommerez de la chaque élément de la séquence de séquences, alors cela fonctionnera pour vous.

En outre, il fera des choses étranges si vous jouez avec l'ordre, tout comme Sam's l'a fait à un moment donné .

0 votes

Je pense que c'est la meilleure solution... le seul problème est que la liste n'a pas de Longueur... elle a un Compte. Mais c'est facile à changer. Nous pouvons améliorer cette solution en ne construisant même pas de listes mais en retournant des ienumerables qui contiennent des références à la liste principale avec une combinaison offset/longueur. Ainsi, si la taille du groupe est grande, nous ne gaspillons pas de mémoire. Commentez si vous voulez que je l'écrive.

0 votes

Amir, j'aimerais voir cela écrit.

1 votes

C'est agréable et rapide - Cameron a posté une solution très similaire après la vôtre, le seul problème est qu'elle met en mémoire tampon les morceaux, ce qui peut conduire à une perte de mémoire si les morceaux et les tailles des éléments sont grands. Voir ma réponse pour une réponse alternative, bien que beaucoup plus difficile.

59voto

3dGrabber Points 761

Ok, voilà ce que j'en pense :

  • complètement paresseux : fonctionne sur les énumérables infinis
  • pas de copie/tampon intermédiaire
  • Temps d'exécution O(n)
  • fonctionne également lorsque les séquences internes ne sont que partiellement consommées

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

Exemple d'utilisation

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

Explications

Le code fonctionne en imbriquant deux yield les itérateurs basés sur la technologie.

L'itérateur externe doit garder la trace du nombre d'éléments qui ont été effectivement consommés par l'itérateur interne (chunk). Ceci est fait en fermant sur remaining con innerMoveNext() . Les éléments non consommés d'un chunk sont rejetés avant que le chunk suivant ne soit cédé par l'itérateur externe. Ceci est nécessaire car sinon vous obtenez des résultats incohérents, lorsque les énumérables internes ne sont pas (complètement) consommés (par ex. c3.Count() retournerait 6).

Note : La réponse a été mise à jour pour combler les lacunes signalées par @aolszowka.

3 votes

Très bien. Ma solution "correcte" était bien plus compliquée que ça. C'est la réponse #1 IMHO.

1 votes

Cette méthode présente un comportement inattendu (du point de vue de l'API) lorsque ToArray() est appelé, et elle n'est pas non plus à l'abri des threads.

0 votes

@aolszowka : pourriez-vous préciser ?

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X