Alternative plus rapide aux boucles imbriquées?

J'ai besoin de créer une liste de combinaisons de nombres. Les nombres sont assez petits donc je peux utiliser byteplutôt que int. Cependant, il nécessite de nombreuses boucles imbriquées afin d'obtenir toutes les combinaisons possibles. Je me demande s'il existe une manière plus efficace de faire ce que je recherche. Le code jusqu'à présent est:

var data = new List<byte[]>();
for (byte a = 0; a < 2; a++)
for (byte b = 0; b < 3; b++)
for (byte c = 0; c < 4; c++)
for (byte d = 0; d < 3; d++)
for (byte e = 0; e < 4; e++)
for (byte f = 0; f < 3; f++)
for (byte g = 0; g < 3; g++)
for (byte h = 0; h < 4; h++)
for (byte i = 0; i < 2; i++)
for (byte j = 0; j < 4; j++)
for (byte k = 0; k < 4; k++)
for (byte l = 0; l < 3; l++)
for (byte m = 0; m < 4; m++)
{
    data.Add(new [] {a, b, c, d, e, f, g, h, i, j, k, l, m});
}

J'envisageais d'utiliser quelque chose comme a BitArraymais je ne sais pas comment je pourrais l'intégrer.

Toutes les recommandations seraient grandement appréciés. Sinon, c'est peut-être le moyen le plus rapide de faire ce que je veux?

EDIT Quelques points rapides (et excuses, je ne les ai pas mis dans le message d'origine):

• Les nombres et leur ordre (2, 3, 4, 3, 4, 3, 3, etc.) sont très importants, donc utiliser une solution telle que Générer des permutations à l'aide de LINQ n'aidera pas car les maximums dans chaque `` colonne '' sont différent
• Je ne suis pas mathématicien, alors je m'excuse si je n'utilise pas correctement les termes techniques comme «permutations» et «combinaisons» :)
• Je ne dois remplir toutes ces combinaisons à la fois - je ne peux pas saisir un ou l' autre , selon un indice
• L'utilisation byteest plus rapide que l'utilisation int, je le garantis . Il est également bien meilleur sur l'utilisation de la mémoire d'avoir plus de 67 millions de tableaux d'octets plutôt que de
• Mon objectif ultime ici est de rechercher une alternative plus rapide aux boucles imbriquées.
• J'ai envisagé d'utiliser la programmation parallèle, mais en raison de la nature itérative de ce que j'essaie d'accomplir, je n'ai pas pu trouver un moyen de le faire avec succès (même avec ConcurrentBag) - mais je suis heureux d'avoir tort :)

CONCLUSION

Caramiriel a fourni une bonne micro-optimisation qui réduit le temps des boucles, j'ai donc marqué cette réponse comme correcte. Eric a également mentionné qu'il est plus rapide de pré-attribuer la liste. Mais, à ce stade, il semble que les boucles imbriquées soient en fait le moyen le plus rapide possible de le faire (déprimant, je sais!).

Si vous voulez essayer exactement ce avec quoi j'essayais de comparer StopWatch, optez pour 13 boucles comptant jusqu'à 4 dans chaque boucle - cela fait environ 67 millions de lignes dans la liste. Sur ma machine (i5-3320M 2,6 GHz), il faut environ 2,2 s pour faire la version optimisée.

Vous pouvez utiliser les propriétés d'une structure et allouer la structure à l'avance. J'ai coupé certains niveaux dans l'exemple ci-dessous, mais je suis sûr que vous serez en mesure de comprendre les détails. Fonctionne environ 5 à 6 fois plus vite que l'original (mode de libération).

Le bloc:

struct ByteBlock
{
    public byte A;
    public byte B;
    public byte C;
    public byte D;
    public byte E;
}

La boucle:

var data = new ByteBlock[2*3*4*3*4];
var counter = 0;

var bytes = new ByteBlock();

for (byte a = 0; a < 2; a++)
{
    bytes.A = a;
    for (byte b = 0; b < 3; b++)
    {
        bytes.B = b;
        for (byte c = 0; c < 4; c++)
        {
            bytes.C = c;
            for (byte d = 0; d < 3; d++)
            {
                bytes.D = d;
                for (byte e = 0; e < 4; e++)
                {
                    bytes.E = e;
                    data[counter++] = bytes;
                }
            }
        }
    }
}

C'est plus rapide car il n'alloue pas de nouvelle liste à chaque fois que vous l'ajoutez à la liste. De plus, comme il crée cette liste, il a besoin d'une référence à toutes les autres valeurs (a, b, c, d, e). Vous pouvez supposer que chaque valeur n'est modifiée qu'une seule fois dans la boucle, afin que nous puissions l'optimiser pour ce faire (localité des données).

Lisez également les commentaires pour les effets secondaires.

Modification de la réponse pour utiliser un T[]au lieu d'un List<T>.

Ce que vous faites, c'est compter (avec une base variable, mais toujours en comptant).

Puisque vous utilisez C #, je suppose que vous ne voulez pas jouer avec une disposition de mémoire et des structures de données utiles qui vous permettent vraiment d' optimiser votre code.

Donc, ici, je poste quelque chose de différent, qui peut ne pas convenir à votre cas, mais cela vaut la peine de noter: si vous accédez réellement à la liste de manière clairsemée, voici une classe qui vous permet de calculer le i-ème élément en temps linéaire (plutôt que exponentielle comme les autres réponses)

class Counter
{
    public int[] Radices;

    public int[] this[int n]
    {
        get 
        { 
            int[] v = new int[Radices.Length];
            int i = Radices.Length - 1;

            while (n != 0 && i >= 0)
            {
                //Hope C# has an IL-opcode for div-and-reminder like x86 do
                v[i] = n % Radices[i];
                n /= Radices[i--];
            }
            return v;
        }
    }
}

Vous pouvez utiliser cette classe de cette façon

Counter c = new Counter();
c.Radices = new int[] { 2,3,4,3,4,3,3,4,2,4,4,3,4};

maintenant c[i]est le même que votre liste, nommez - le l, l[i].

Comme vous pouvez le voir, vous pouvez facilement éviter toutes ces boucles :) même lorsque vous pré-calculez toute la liste dans son ensemble, car vous pouvez simplement implémenter un compteur Carry-Ripple.

Les compteurs sont un sujet très étudié, je vous conseille vivement de rechercher de la littérature si vous vous sentez.

Méthode 1

Une façon d'accélérer le processus consiste à spécifier la capacité si vous prévoyez de continuer à l'utiliser List<byte[]>, comme ceci.

var data = new List<byte[]>(2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4);

Méthode 2

De plus, vous pouvez utiliser System.Arraydirectement pour obtenir un accès plus rapide. Je recommande cette approche si votre question insiste pour que chaque élément soit physiquement peuplé en mémoire, dès le départ.

var data = new byte[2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4][];
int counter = 0;

for (byte a = 0; a < 2; a++)
    for (byte b = 0; b < 3; b++)
        for (byte c = 0; c < 4; c++)
            for (byte d = 0; d < 3; d++)
                for (byte e = 0; e < 4; e++)
                    for (byte f = 0; f < 3; f++)
                        for (byte g = 0; g < 3; g++)
                            for (byte h = 0; h < 4; h++)
                                for (byte i = 0; i < 2; i++)
                                    for (byte j = 0; j < 4; j++)
                                        for (byte k = 0; k < 4; k++)
                                            for (byte l = 0; l < 3; l++)
                                                for (byte m = 0; m < 4; m++)
                                                    data[counter++] = new[] { a, b, c, d, e, f, g, h, i, j, k, l, m };

Cela prend 596 ms pour terminer sur mon ordinateur, ce qui est environ 10,4% plus rapide que le code en question (qui prend 658 ms).

Méthode 3

Vous pouvez également utiliser la technique suivante pour une initialisation à faible coût qui convient à l'accès de manière clairsemée. Ceci est particulièrement favorable lorsque seuls certains éléments peuvent être nécessaires et que leur détermination initiale est considérée comme inutile. De plus, des techniques comme celles-ci peuvent devenir la seule option viable lorsque vous travaillez avec des éléments plus vastes lorsque la mémoire est insuffisante.

Dans cette mise en œuvre, chaque élément doit être déterminé paresseusement, à la volée, lors de l'accès. Naturellement, cela entraîne un coût de CPU supplémentaire qui est encouru lors de l'accès.

class HypotheticalBytes
{
    private readonly int _c1, _c2, _c3, _c4, _c5, _c6, _c7, _c8, _c9, _c10, _c11, _c12;
    private readonly int _t0, _t1, _t2, _t3, _t4, _t5, _t6, _t7, _t8, _t9, _t10, _t11;

    public int Count
    {
        get { return _t0; }
    }

    public HypotheticalBytes(
        int c0, int c1, int c2, int c3, int c4, int c5, int c6, int c7, int c8, int c9, int c10, int c11, int c12)
    {
        _c1 = c1;
        _c2 = c2;
        _c3 = c3;
        _c4 = c4;
        _c5 = c5;
        _c6 = c6;
        _c7 = c7;
        _c8 = c8;
        _c9 = c9;
        _c10 = c10;
        _c11 = c11;
        _c12 = c12;
        _t11 = _c12 * c11;
        _t10 = _t11 * c10;
        _t9 = _t10 * c9;
        _t8 = _t9 * c8;
        _t7 = _t8 * c7;
        _t6 = _t7 * c6;
        _t5 = _t6 * c5;
        _t4 = _t5 * c4;
        _t3 = _t4 * c3;
        _t2 = _t3 * c2;
        _t1 = _t2 * c1;
        _t0 = _t1 * c0;
    }

    public byte[] this[int index]
    {
        get
        {
            return new[]
            {
                (byte)(index / _t1),
                (byte)((index / _t2) % _c1),
                (byte)((index / _t3) % _c2),
                (byte)((index / _t4) % _c3),
                (byte)((index / _t5) % _c4),
                (byte)((index / _t6) % _c5),
                (byte)((index / _t7) % _c6),
                (byte)((index / _t8) % _c7),
                (byte)((index / _t9) % _c8),
                (byte)((index / _t10) % _c9),
                (byte)((index / _t11) % _c10),
                (byte)((index / _c12) % _c11),
                (byte)(index % _c12)
            };
        }
    }
}

Cela prend 897 ms pour terminer sur mon ordinateur (également créer et ajouter à un Arraycomme dans la méthode 2 ), ce qui est environ 36,3% plus lent que le code en question (qui prend 658 ms).

Sur ma machine, cela génère les combinaisons en 222 ms vs 760 ms (les 13 boucles for):

private static byte[,] GenerateCombinations(byte[] maxNumberPerLevel)
{
    var levels = maxNumberPerLevel.Length;

    var periodsPerLevel = new int[levels];
    var totalItems = 1;
    for (var i = 0; i < levels; i++)
    {
        periodsPerLevel[i] = totalItems;
        totalItems *= maxNumberPerLevel[i];
    }

    var results = new byte[totalItems, levels];

    Parallel.For(0, levels, level =>
    {
        var periodPerLevel = periodsPerLevel[level];
        var maxPerLevel = maxNumberPerLevel[level];
        for (var i = 0; i < totalItems; i++)
            results[i, level] = (byte)(i / periodPerLevel % maxPerLevel);
    });

    return results;
}

var numbers = new[] { 2, 3, 4, 3, 4, 3, 3, 4, 2, 4, 4, 3, 4 };
var result = (numbers.Select(i => Enumerable.Range(0, i))).CartesianProduct();

Utilisation de la méthode d'extension sur http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    // base case: 
    IEnumerable<IEnumerable<T>> result =
        new[] { Enumerable.Empty<T>() };
    foreach (var sequence in sequences)
    {
        // don't close over the loop variable (fixed in C# 5 BTW)
        var s = sequence;
        // recursive case: use SelectMany to build 
        // the new product out of the old one 
        result =
            from seq in result
            from item in s
            select seq.Concat(new[] { item });
    }
    return result;
}

List a un tableau en interne où il stocke ses valeurs, avec une longueur fixe. Lorsque vous appelez List.Add, il vérifie s'il y a suffisamment d'espace. Quand il ne peut pas ajouter le nouvel élément, il créera un nouveau tableau de plus grande taille, copiera tous les éléments précédents, puis en ajoutera un nouveau. Cela prend plusieurs cycles.

Puisque vous connaissez déjà le nombre d'éléments, vous pouvez créer la liste de la bonne taille, qui devrait déjà être beaucoup plus rapide.

De plus, je ne sais pas comment vous accédez aux valeurs, mais vous pouvez créer cette chose et enregistrer l'image dans le code (le charger à partir du disque sera probablement plus lent que ce que vous faites maintenant. chose?

Voici une manière différente qui n'a besoin que de 2 boucles. L'idée est d'augmenter le premier élément et si ce nombre dépasse, d'augmenter le suivant.

Au lieu d'afficher les données, vous pouvez utiliser currentValues.Clone et ajouter cette version clonée à votre liste. Pour moi, cela a fonctionné plus rapidement que votre version.

byte[] maxValues = {2, 3, 4};
byte[] currentValues = {0, 0, 0};

do {
    Console.WriteLine("{0}, {1}, {2}", currentValues[0], currentValues[1], currentValues[2]);

    currentValues[0] += 1;

    for (int i = 0; i <= maxValues.Count - 2; i++) {
        if (currentValues[i] < maxValues[i]) {
            break;
        }

        currentValues[i] = 0;
        currentValues[i + 1] += 1;
    }

// Stop the whole thing if the last number is over
// } while (currentValues[currentValues.Length-1] < maxValues[maxValues.Length-1]);
} while (currentValues.Last() < maxValues.Last());

• J'espère que ce code fonctionne, je l'ai converti à partir de vb

Tous vos nombres sont des constantes de temps de compilation.

Qu'en est-il du déroulement de toutes les boucles dans une liste (en utilisant votre programme pour écrire du code):

data.Add(new [] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
data.Add(new [] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
etc.

Cela devrait au moins supprimer la surcharge des boucles for (s'il y en a).

Je ne suis pas trop familier avec C #, mais il semble y avoir des moyens de sérialiser des objets. Et si vous venez de générer cette liste et de la sérialiser sous une forme ou une autre? Je ne suis pas sûr que la désérialisation soit plus rapide que la création de la liste et l'ajout des éléments.

Avez-vous besoin que le résultat soit un tableau de tableaux? Avec la configuration actuelle, la longueur des tableaux internes est fixe et pourrait être remplacée par des structures. Cela permettrait à la chose entière d'être réservée comme un bloc continu de mémoire et fournit un accès plus facile aux éléments (je ne sais pas comment vous utiliserez cette chose plus tard).

L'approche ci-dessous est beaucoup plus rapide (41ms vs 1071ms pour l'original sur ma box):

struct element {
    public byte a;
    public byte b;
    public byte c;
    public byte d;
    public byte e;
    public byte f;
    public byte g;
    public byte h;
    public byte i;
    public byte j;
    public byte k;
    public byte l;
    public byte m;
}

element[] WithStruct() {
    var t = new element[3981312];
    int z = 0;
    for (byte a = 0; a < 2; a++)
    for (byte b = 0; b < 3; b++)
    for (byte c = 0; c < 4; c++)
    for (byte d = 0; d < 3; d++)
    for (byte e = 0; e < 4; e++)
    for (byte f = 0; f < 3; f++)
    for (byte g = 0; g < 3; g++)
    for (byte h = 0; h < 4; h++)
    for (byte i = 0; i < 2; i++)
    for (byte j = 0; j < 4; j++)
    for (byte k = 0; k < 4; k++)
    for (byte l = 0; l < 3; l++)
    for (byte m = 0; m < 4; m++)
    {
        t[z].a = a;
        t[z].b = b;
        t[z].c = c;
        t[z].d = d;
        t[z].e = e;
        t[z].f = f;
        t[z].g = g;
        t[z].h = h;
        t[z].i = i;
        t[z].j = j;
        t[z].k = k;
        t[z].l = l;
        t[z].m = m;
        z++;
    }
    return t;
}

Qu'en est-il de l'utiliser Parallel.For()pour l'exécuter? (Félicitations d'optimisation de structure à @Caramiriel ). J'ai légèrement modifié les valeurs (a est 5 au lieu de 2) donc je suis plus confiant dans les résultats.

    var data = new ConcurrentStack<List<Bytes>>();
    var sw = new Stopwatch();

    sw.Start();

    Parallel.For(0, 5, () => new List<Bytes>(3*4*3*4*3*3*4*2*4*4*3*4),
      (a, loop, localList) => {
        var bytes = new Bytes();
        bytes.A = (byte) a;
        for (byte b = 0; b < 3; b++) {
          bytes.B = b;
          for (byte c = 0; c < 4; c++) {
            bytes.C = c; 
            for (byte d = 0; d < 3; d++) {
              bytes.D = d; 
              for (byte e = 0; e < 4; e++) {
                bytes.E = e; 
                for (byte f = 0; f < 3; f++) {
                  bytes.F = f; 
                  for (byte g = 0; g < 3; g++) {
                    bytes.G = g; 
                    for (byte h = 0; h < 4; h++) {
                      bytes.H = h; 
                      for (byte i = 0; i < 2; i++) {
                        bytes.I = i; 
                        for (byte j = 0; j < 4; j++) {
                          bytes.J = j; 
                          for (byte k = 0; k < 4; k++) {
                            bytes.K = k; 
                            for (byte l = 0; l < 3; l++) {
                              bytes.L = l;
                              for (byte m = 0; m < 4; m++) {
                                bytes.M = m;
                                localList.Add(bytes);
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }


        return localList;
      }, x => {
        data.Push(x);
    });

    var joinedData = _join(data);

_join() est une méthode privée, définie comme:

private static IList<Bytes> _join(IEnumerable<IList<Bytes>> data) {
  var value = new List<Bytes>();
  foreach (var d in data) {
    value.AddRange(d);
  }
  return value;
}

Sur mon système, cette version fonctionne environ 6 fois plus vite (1,718 secondes contre 0,266 secondes).

Certains de vos nombres tiennent entièrement sur un nombre entier de bits, vous pouvez donc les «emballer» avec le numéro de niveau supérieur:

for (byte lm = 0; lm < 12; lm++)
{
    ...
    t[z].l = (lm&12)>>2;
    t[z].m = lm&3;
    ...
}

Bien sûr, cela rend le code moins lisible, mais vous avez enregistré une boucle. Cela peut être fait chaque fois que l'un des nombres est une puissance de deux, ce qui correspond à sept fois dans votre cas.

Voici une autre solution. En dehors de VS, il fonctionne aussi vite que 437,5 ms, ce qui est 26% plus rapide que le code d'origine (593,7 sur mon ordinateur):

static List<byte[]> Combinations(byte[] maxs)
{
  int length = maxs.Length;
  int count = 1; // 3981312;
  Array.ForEach(maxs, m => count *= m);
  byte[][] data = new byte[count][];
  byte[] counters = new byte[length];

  for (int r = 0; r < count; r++)
  {
    byte[] row = new byte[length];
    for (int c = 0; c < length; c++)
      row[c] = counters[c];
    data[r] = row;

    for (int i = length - 1; i >= 0; i--)
    {
      counters[i]++;
      if (counters[i] == maxs[i])
        counters[i] = 0;
      else
        break;
    }
  }

  return data.ToList();
}