Schnellere Alternative zu verschachtelten Schleifen?

85

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.

benpage
quelle
1
Versuchen Sie, linq zu verwenden und wenn Sie Multicore-Prozessor verwenden, dann Parrallel.for
Jalpesh Vadgama
1
Basierend auf dem, was ich sehe, sind dies nicht die Permutationen, sondern die Kombinationen einiger sehr kleiner (2-4 Elemente) Mengen. Ist das richtig oder möchten Sie tatsächlich alle / einige Permutationen einer Menge?
Carsten
Ich gehe davon aus youve gesucht bing.com/search?q=c%23+permutation+enumerable bereits und aus irgendeinem Grunde (nicht im Beitrag erwähnt) entschieden gegen bestehende Antworten wie stackoverflow.com/questions/4319049/... ... Erwäge Optionen, die Sie geprüft und gegen die Sie sich entschieden haben, um diese Frage zu verbessern.
Alexei Levenkov
3
Wenn es um Leistung geht: Sie können die Liste (Konstruktor) vorab zuordnen und einige Schleifen abrollen, aber ich denke, das ist es auch ... abgesehen von der Vorberechnung und Speicherung dieser Zahlen. Die Schleifen (Overhead) sind wahrscheinlich die teuersten von allen, da im Körper nur wenige Operationen durchgeführt werden.
Caramiriel
5
@benpage: Warum müssen Sie alle Kombinationen im Voraus generieren? Warum nicht eine Kombination aus dem Index generieren, wenn Sie sie benötigen?
Pieter Witvoet

Antworten:

61

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

Caramiriel
quelle
1
Es ist eine Struktur, also solltest du in Ordnung sein =) sie sind alle einzigartig. Es wird beim Aufrufen der List<T>.AddMethode kopiert .
Caramiriel
4
Es ist noch schneller, wenn Sie die Kapazität der Liste () zugewiesen haben
Eric
5
Achten Sie auf Stapelüberlauf- Ausnahmen, wenn Sie zu viele Objekte auf dem Stapel zuweisen .
Andrei Tătar
7
@ Andrew Ich verstehe deinen Standpunkt nicht. Dieser Code ist nicht rekursiv und hat eine minimale Stapelverwendung.
CodesInChaos
3
@ Andrew: Das ist nicht genügend Speicher, kein Stackoverflow. Dies liegt daran, dass die List<T>.Add()Methode über den Punkt hinausgeht, an dem sie gespeichert werden kann. Dadurch wird die Größe geändert (doppelte Größe), wodurch mehr als 2 GB Speicher benötigt werden. Versuchen Sie die Vorbelegung mithilfe der neuen Liste <ByteBlock> (maxPerLevel.Aggregate (1, (x, y) => x * y)), obwohl es bereits 'zufällig' ist, dass Sie einen vollständigen 2-GB-Block dieser Daten im Speicher benötigen. Beachten Sie auch, dass data.ToArray (); ist teuer, weil es zu diesem Zeitpunkt zweimal Elemente im Speicher hält. [umformuliert]
Caramiriel
33

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.

Adam
quelle
4
Ich mag Ihre Antwort, aber zu sagen, dass alle anderen Antworten exponentiell sind, ist falsch.
Kekse
1
Wie schnell ist das im Vergleich zu Caramiriels Antwort?
John Odom
17
"C-kiddy- #", wirklich? Das scheint völlig unangebracht.
KChaloux
2
Und es tut: Math.DivRem
Caramiriel
1
Ich denke, dass Optimierung auf einer bestimmten Ebene eine Frage der Verwendung ist. Wenn beispielsweise jedes Array nur einmal verwendet werden soll, können Sie die intensive Speicherzuweisung vermeiden, die meiner Meinung nach der kritische Engpass ist. Wenn Sie den gesamten Wert berechnen möchten, sollten Sie außerdem die Tatsache ausnutzen, dass Sie einzelne Inkremente (dh +1 Inkremente) ausführen, um eine Division zu vermeiden. Dies ist eher als "out of the box" -Antwear oder als Prototyp gedacht, ich habe nicht wirklich versucht, es zu beschleunigen, ich mag es einfach so :)
14

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

Kekse
quelle
1
Ihr zweiter Vorschlag ist auch eine erhebliche Einsparung in Bezug auf den Speicherverbrauch. (Aber ich würde beachten, dass davon
ausgegangen wird,
Ich muss die gesamte Liste auf einmal erstellen - ich kann nicht auf einen Index in der Liste verweisen.
Benpage
@ Taemyr Danke. Ich werde das entsprechend aktualisieren. Wenn die Implementierung wirklich darauf besteht, dass Sie die gesamte Liste im Voraus ausgefüllt haben, funktioniert diese dritte Option offensichtlich nicht für Sie.
Kekse
3
@benpage Warum muss die Liste ausgefüllt werden?
Taemyr
14

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;
}
Andrei Tătar
quelle
Das ist eine großartige Antwort! Leider läuft es langsamer als die verschachtelten Schleifen. Gibt es eine Chance, die Sie mit TPL bearbeiten können?
Benpage
leider immer noch etwas langsamer.
Benpage
1
@benpage Es gibt eine einfache Möglichkeit, es mindestens zweimal schneller zu machen. Sie müssen nur den Ergebnistyp in int [,] ändern. Dadurch wird der gesamte Array-Speicher in einem Aufruf zugewiesen. Ich bin mir nicht sicher, wie das Ihren Anforderungen entspricht (Änderung des Rückgabetyps).
Andrei Tătar
8
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;
}
Eric
quelle
1
das läuft viel langsamer :(
benpage
8

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?

gjvdkamp
quelle
Ich habe tatsächlich versucht, ein reguläres Array vorab zuzuweisen, und ob Sie es glauben oder nicht, es ist langsamer. Wie ich oben sagte, muss dies im laufenden Betrieb erstellt werden, ich kann es nicht einmal berechnen und es verlassen.
Benpage
Ja wirklich? wow - Sie laufen mit aktivierten Optimierungen, oder? (nur fragen)
Carsten
Ah, das ist ein weiteres Problem. Normale Arrays [x, y] sind gut zu verwenden, aber ein Array von Arrays ist schneller. stackoverflow.com/questions/597720/… wegen wie sie unter der Haube in IL
implementiert sind
5

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
the_lotus
quelle
3

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.

Null
quelle
Serialisierung ist ein wirklich großartiges Denken außerhalb des Rahmens!
Joel B
Leider sind die Maxima in der Liste dynamisch, ich kann dies nicht statisch eingeben. Gute Idee!
Benpage
2

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;
}
gjvdkamp
quelle
Gute Idee - genau das habe ich in meinem realen Projekt getan - ich habe es aus Gründen der Einfachheit einfach nicht in die ursprüngliche Lösung aufgenommen. Ich suchte hauptsächlich nach einer besseren Alternative zu verschachtelten Schleifen.
Benpage
1

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

jdphenix
quelle
1
Dies führt garantiert zu falschem Teilen und wird wahrscheinlich um ein Vielfaches langsamer sein.
Gjvdkamp
Nicht schlecht - leider läuft es langsamer als die for-Schleifen. FWIW Ich habe es mit ALLEN versucht Parallel.Forund VS ist abgestürzt!
Benpage
@gjvdkamp Ich habe meine Antwort mit einer parallelen Version aktualisiert, die meines Erachtens das Problem der falschen Freigabe beseitigt.
jdphenix
0

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.

Fabien Dupont
quelle
Ich würde gerne mehr über diese Antwort erfahren - können Sie sie erweitern?
Benpage
Entschuldigung für die späte Antwort. m geht von 0 bis 3, was binär 00 bis 11 ergibt, l von 0 bis 2, was 00 bis 10 ergibt. Wenn Sie sie also separat drucken, würde dies Folgendes ergeben: 00 00 00 01 00 10 00 11 01 00 .. 10 11 Sie können diese in einer einzigen Anzahl von 4 Bits von 0000 bis 1011 zusammenführen und die entsprechenden Bits mit einer Maske auswählen. Lm & 3 macht das biwise und zwischen lm und (11) b lm & 12 macht dasselbe mit lm und (1100) b dann verschieben wir uns um zwei Bits, um die "reelle" Zahl zu haben. Übrigens, ich habe gerade festgestellt, dass es in diesem Fall ausreicht, lm >> 2 zu machen.
Fabien Dupont
0

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