Schnellere Alternative zu verschachtelten Schleifen?

Ich muss eine Liste von Zahlenkombinationen erstellen. Die Zahlen sind ziemlich klein, so dass ich byteeher als verwenden kann int. Es sind jedoch viele verschachtelte Schleifen erforderlich, um jede mögliche Kombination zu erhalten. Ich frage mich, ob es eine effizientere Möglichkeit gibt, das zu tun, wonach ich suche. Code ist bisher:

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

Ich habe überlegt, so etwas wie ein zu verwenden BitArray, bin mir aber nicht sicher, wie ich es integrieren könnte.

Alle Empfehlungen wäre sehr dankbar. Alternativ ist dies vielleicht der schnellste Weg, um das zu tun, was ich will?

BEARBEITEN Einige kurze Punkte (und Entschuldigung, ich habe diese nicht in den ursprünglichen Beitrag aufgenommen):

• Die Zahlen und deren Reihenfolge (2, 3, 4, 3, 4, 3, 3 usw.) sind sehr wichtig. Daher hilft die Verwendung einer Lösung wie dem Generieren von Permutationen mit LINQ nicht, da die Maxima in jeder 'Spalte' sind anders
• Ich bin kein Mathematiker, also entschuldige ich mich, wenn ich die Fachbegriffe wie "Permutationen" und "Kombinationen" nicht richtig verwende :)
• Ich tun müssen alle diese Kombinationen füllen auf einmal - ich kann nicht nur eine greifen oder eine andere basiert auf einem Index
• Die Verwendung byteist schneller als die Verwendung int, das garantiere ich . Bei der Speichernutzung ist es auch viel besser, mehr als 67 Millionen Bytes als Ints zu haben
• Mein oberstes Ziel ist es, nach einer schnelleren Alternative zu verschachtelten Schleifen zu suchen.
• Ich habe überlegt, parallel zu programmieren, aber aufgrund der iterativen Natur dessen, was ich erreichen möchte, konnte ich keinen Weg finden, dies erfolgreich zu tun (auch nicht mit ConcurrentBag) - aber ich bin froh, dass ich mich als falsch erwiesen habe :)

FAZIT

Caramiriel hat eine gute Mikrooptimierung bereitgestellt, die einige Zeit in den Schleifen spart, daher habe ich diese Antwort als richtig markiert. Eric erwähnte auch, dass es schneller ist, die Liste vorab zuzuweisen. Aber zu diesem Zeitpunkt scheinen die verschachtelten Schleifen tatsächlich der schnellstmögliche Weg zu sein (deprimierend, ich weiß!).

Wenn Sie genau das ausprobieren möchten StopWatch, womit ich ein Benchmarking durchgeführt habe , verwenden Sie 13 Schleifen, die bis zu 4 in jeder Schleife zählen - das ergibt ungefähr 67 m + Zeilen in der Liste. Auf meinem Computer (i5-3320M 2.6GHz) dauert die optimierte Version ca. 2.2s.

Sie können die Eigenschaften einer Struktur verwenden und die Struktur im Voraus zuweisen. Ich habe im folgenden Beispiel einige Ebenen abgeschnitten, aber ich bin sicher, dass Sie die Einzelheiten herausfinden können. Läuft ungefähr 5-6 mal schneller als das Original (Release-Modus).

Der Block:

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

Die Schleife:

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

Es ist schneller, weil nicht jedes Mal, wenn Sie es der Liste hinzufügen, eine neue Liste zugewiesen wird. Da diese Liste erstellt wird, muss auf jeden anderen Wert (a, b, c, d, e) verwiesen werden. Sie können davon ausgehen, dass jeder Wert innerhalb der Schleife nur einmal geändert wird, sodass wir ihn dafür optimieren können (Datenlokalität).

Lesen Sie auch die Kommentare für Nebenwirkungen.

Die Antwort wurde bearbeitet, um ein T[]anstelle von a zu verwenden List<T>.

Was Sie tun, ist zu zählen (mit variablem Radix, aber immer noch zu zählen).

Da Sie C # verwenden, möchten Sie vermutlich nicht mit nützlichen Speicherlayouts und Datenstrukturen spielen, mit denen Sie Ihren Code wirklich optimieren können.

Hier poste ich also etwas anderes, das vielleicht nicht zu Ihrem Fall passt, aber es ist erwähnenswert: Falls Sie tatsächlich spärlich auf die Liste zugreifen, hier eine Klasse, mit der Sie das i-te Element in linearer Zeit (eher) berechnen können als exponentiell wie die anderen Antworten)

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

Sie können diese Klasse auf diese Weise verwenden

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

Jetzt c[i]ist das gleiche wie Ihre Liste, nennen Sie es l, l[i].

Wie Sie sehen können, können Sie all diese Schleifen leicht vermeiden :), selbst wenn Sie die gesamte Liste vorab berechnen, da Sie einfach einen Carry-Ripple-Zähler implementieren können.

Zähler sind ein sehr studiertes Fach, ich rate dringend, nach Literatur zu suchen, wenn Sie das Gefühl haben.

Methode 1

Eine Möglichkeit, dies zu beschleunigen, besteht darin, die Kapazität anzugeben, wenn Sie diese weiterhin verwenden List<byte[]>möchten.

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

Methode 2

Darüber hinaus können Sie System.Arraydirekt verwenden, um einen schnelleren Zugriff zu erhalten. Ich empfehle diesen Ansatz, wenn Ihre Frage darauf besteht, dass jedes Element im Voraus physisch im Speicher gespeichert wird.

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

Auf meinem Computer dauert dies 596 ms, was etwa 10,4% schneller ist als der betreffende Code (der 658 ms dauert).

Methode 3

Alternativ können Sie die folgende Technik für eine kostengünstige Initialisierung verwenden, die nur spärlich für den Zugriff geeignet ist. Dies ist besonders günstig, wenn möglicherweise nur einige Elemente benötigt werden und die Bestimmung aller Elemente im Voraus als unnötig angesehen wird. Darüber hinaus können Techniken wie diese die einzig praktikable Option sein, wenn mit größeren Elementen gearbeitet wird, wenn der Speicher knapp wird.

Bei dieser Implementierung muss jedes Element beim Zugriff im Handumdrehen träge bestimmt werden. Dies kostet natürlich zusätzliche CPU, die beim Zugriff anfällt.

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

Dies dauert auf meinem Computer 897 ms (auch Erstellen und Hinzufügen zu einem Arraywie in Methode 2 ), was etwa 36,3% langsamer ist als der betreffende Code (der 658 ms dauert).

Auf meinem Computer werden dadurch die Kombinationen in 222 ms gegenüber 760 ms (die 13 für Schleifen) generiert:

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

Verwenden der Erweiterungsmethode unter 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 verfügt intern über ein Array, in dem die Werte mit einer festen Länge gespeichert werden. Wenn Sie List.Add aufrufen, wird geprüft, ob genügend Speicherplatz vorhanden ist. Wenn das neue Element nicht hinzugefügt werden kann, wird ein neues Array mit einer größeren Größe erstellt. Kopieren Sie alle vorherigen Elemente und fügen Sie dann ein neues hinzu. Dies dauert einige Zyklen.

Da Sie die Anzahl der Elemente bereits kennen, können Sie eine Liste mit der richtigen Größe erstellen, die bereits viel schneller sein sollte.

Sie sind sich auch nicht sicher, wie Sie auf die Werte zugreifen, aber Sie können dieses Element erstellen und das Bild im Code speichern (das Laden von der Festplatte ist wahrscheinlich langsamer als das, was Sie jetzt tun. Wie oft lesen / schreiben Sie darauf Ding?

Hier ist ein anderer Weg, der nur 2 Schleifen benötigt. Die Idee ist, das erste Element zu erhöhen, und wenn diese Zahl überschritten wird, erhöhen Sie das nächste.

Anstatt die Daten anzuzeigen, können Sie currentValues.Clone verwenden und diese geklonte Version zu Ihrer Liste hinzufügen. Für mich lief das schneller als deine 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());

• Hoffe dieser Code funktioniert, ich habe ihn von vb konvertiert

Alle Ihre Zahlen sind Kompilierungszeitkonstanten.

Was ist mit dem Abrollen aller Schleifen in einer Liste (mit Ihrem Programm zum Schreiben von 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.

Das sollte zumindest den Overhead der for-Schleifen (falls vorhanden) wegnehmen.

Ich kenne C # nicht allzu gut, aber es scheint einige Möglichkeiten zu geben, Objekte zu serialisieren. Was wäre, wenn Sie diese Liste gerade erstellt und in irgendeiner Form serialisiert hätten? Ich bin mir nicht sicher, ob die Deserialisierung schneller ist als das Erstellen der Liste und das Hinzufügen der Elemente.

Benötigen Sie das Ergebnis als Array von Arrays? Mit dem aktuellen Setup ist die Länge der inneren Arrays festgelegt und kann durch Strukturen ersetzt werden. Dies würde es ermöglichen, das gesamte Objekt als einen fortlaufenden Speicherblock zu reservieren und einen einfacheren Zugriff auf die Elemente zu ermöglichen (nicht sicher, wie Sie dieses Objekt später verwenden).

Der folgende Ansatz ist viel schneller (41 ms gegenüber 1071 ms für das Original auf meiner 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;
}

Was ist mit Parallel.For()der Ausführung? (Lob für die Strukturoptimierung an @Caramiriel ). Ich habe die Werte leicht geändert (a ist 5 statt 2), damit ich mehr Vertrauen in die Ergebnisse habe.

    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() ist eine private Methode, definiert als:

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

Auf meinem System läuft diese Version ungefähr sechsmal schneller (1,718 Sekunden gegenüber 0,266 Sekunden).

Einige Ihrer Zahlen passen vollständig auf eine ganzzahlige Anzahl von Bits, sodass Sie sie mit der Nummer der oberen Ebene "packen" können:

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

Dies macht den Code natürlich weniger lesbar, aber Sie haben eine Schleife gespeichert. Dies kann jedes Mal erfolgen, wenn eine der Zahlen eine Zweierpotenz ist, in Ihrem Fall also sieben Mal.

Hier ist eine andere Lösung. Außerhalb von VS läuft es so schnell wie 437,5 ms, was 26% schneller ist als der ursprüngliche Code (593,7 auf meinem Computer):

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