Szybsza alternatywa dla zagnieżdżonych pętli?

Muszę stworzyć listę kombinacji liczb. Liczby są dość małe, więc mogę użyć bytezamiast int. Jednak wymaga wielu zagnieżdżonych pętli, aby uzyskać każdą możliwą kombinację. Zastanawiam się, czy istnieje skuteczniejszy sposób na zrobienie tego, o co mi chodzi. Dotychczasowy kod to:

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

Rozważałem użycie czegoś takiego jak a, BitArrayale nie jestem pewien, jak mógłbym to zastosować.

Wszelkie zalecenia będą mile widziane. A może to najszybszy sposób na zrobienie tego, co chcę?

EDYTUJ Kilka szybkich uwag (i przeprosiny, których nie umieściłem w oryginalnym poście):

• Liczby i ich kolejność (2, 3, 4, 3, 4, 3, 3 itd.) Są bardzo ważne, więc użycie rozwiązania takiego jak Generowanie permutacji za pomocą LINQ nie pomoże, ponieważ wartości maksymalne w każdej „kolumnie” są różne
• Nie jestem matematykiem, więc przepraszam, jeśli nie używam poprawnie terminów technicznych, takich jak „permutacje” i „kombinacje” :)
• I nie trzeba wypełnić wszystkie te kombinacje na raz - nie mogę po prostu chwycić jedną lub inny oparty na indeksie
• Używanie bytejest szybsze niż używanie int, gwarantuję to. O wiele lepsze jest również wykorzystanie pamięci, aby mieć 67 mln + tablic bajtów zamiast int
• Moim ostatecznym celem jest znalezienie szybszej alternatywy dla zagnieżdżonych pętli.
• Rozważałem użycie programowania równoległego, ale ze względu na iteracyjny charakter tego, co próbuję osiągnąć, nie mogłem znaleźć sposobu, aby to zrobić z sukcesem (nawet z ConcurrentBag) - jednak cieszę się, że się mylę :)

WNIOSEK

Caramiriel dostarczył dobrą mikro-optymalizację, która pozwala zaoszczędzić trochę czasu na pętli, więc oznaczyłem tę odpowiedź jako poprawną. Eric wspomniał również, że wstępne przydzielenie listy jest szybsze. Ale na tym etapie wydaje się, że zagnieżdżone pętle są w rzeczywistości najszybszym możliwym sposobem zrobienia tego (przygnębiające, wiem!).

Jeśli chcesz wypróbować dokładnie to, z czym próbowałem StopWatchporównać, użyj 13 pętli zliczających do 4 w każdej pętli - to daje około 67 milionów linii na liście. Na moim komputerze (i5-3320M 2,6GHz) wykonanie zoptymalizowanej wersji zajmuje około 2,2 sekundy.

Możesz użyć właściwości struktury i przydzielić strukturę z wyprzedzeniem. Obcięłem niektóre poziomy w poniższej próbce, ale jestem pewien, że będziesz w stanie rozgryźć szczegóły. Działa około 5-6 razy szybciej niż oryginał (tryb zwolnienia).

Blok:

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

Pętla:

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

Jest szybsze, ponieważ nie przydziela nowej listy za każdym razem, gdy dodajesz ją do listy. Ponieważ tworzy tę listę, potrzebuje odniesienia do każdej innej wartości (a, b, c, d, e). Możesz założyć, że każda wartość jest modyfikowana tylko raz w pętli, więc możemy ją zoptymalizować, aby to zrobić (lokalność danych).

Przeczytaj także komentarze dotyczące skutków ubocznych.

Zmodyfikowano odpowiedź, aby użyć T[]zamiast a List<T>.

To, co robisz, to liczenie (ze zmienną podstawą, ale nadal liczysz).

Ponieważ używasz C #, zakładam, że nie chcesz bawić się użytecznym układem pamięci i strukturami danych, które pozwalają naprawdę zoptymalizować kod.

Więc tutaj zamieszczam coś innego, co może nie pasować do twojego przypadku, ale warto to zauważyć: jeśli faktycznie uzyskujesz dostęp do listy w rzadki sposób, tutaj klasa, która pozwala obliczyć i-ty element w czasie liniowym (raczej niż wykładniczy jak inne odpowiedzi)

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

Możesz użyć tej klasy w ten sposób

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

teraz c[i]jest taka sama jak liście, nazwij go l, l[i].

Jak widzisz, możesz łatwo ominąć wszystkie te pętle :), nawet jeśli wstępnie obliczasz całą listę, ponieważ możesz po prostu zaimplementować licznik Carry-Ripple.

Liczniki to bardzo przestudiowany temat, zdecydowanie radzę poszukać jakiejś literatury, jeśli czujesz.

Metoda 1

Jednym ze sposobów na przyspieszenie jest określenie pojemności, jeśli planujesz nadal używać List<byte[]>, w ten sposób.

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

Metoda 2

Ponadto możesz użyć System.Arraybezpośrednio, aby uzyskać szybszy dostęp. Polecam to podejście, jeśli twoje pytanie nalega, aby każdy element był fizycznie zapamiętany, z góry.

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

Na moim komputerze trwa to 596 ms, czyli około 10,4% szybciej niż w przypadku danego kodu (co zajmuje 658 ms).

Metoda 3

Alternatywnie, możesz użyć następującej techniki do taniej inicjalizacji, która odpowiada dostępowi w rzadki sposób. Jest to szczególnie korzystne, gdy potrzebne mogą być tylko niektóre elementy, a określenie ich wszystkich z góry jest uważane za niepotrzebne. Co więcej, techniki takie jak te mogą stać się jedyną realną opcją podczas pracy z bardziej rozległymi elementami, gdy brakuje pamięci.

W tej implementacji każdy element jest leniwie określany w locie, po uzyskaniu dostępu. Oczywiście wiąże się to z kosztem dodatkowego procesora, który jest ponoszony podczas dostępu.

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

Na moim komputerze trwa to 897 ms (również tworzenie i dodawanie do pliku, Arrayjak w metodzie 2 ), czyli około 36,3% wolniej niż w przypadku danego kodu (co zajmuje 658 ms).

Na moim komputerze generuje to kombinacje w 222 ms vs 760 ms (13 dla pętli):

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

Korzystanie z metody rozszerzenia pod adresem 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;
}

Lista ma wewnętrznie tablicę, w której przechowuje wartości o stałej długości. Kiedy wywołujesz List.Add, sprawdza, czy jest wystarczająco dużo miejsca. Kiedy nie może dodać nowego elementu, utworzy nową tablicę o większym rozmiarze, skopiuje wszystkie poprzednie elementy, a następnie doda nowy. Zajmuje to kilka cykli.

Ponieważ znasz już liczbę elementów, możesz utworzyć listę o odpowiednim rozmiarze, która już powinna być znacznie szybsza.

Nie jestem również pewien, w jaki sposób uzyskujesz dostęp do wartości, ale możesz utworzyć tę rzecz i zapisać obraz w kodzie (ładowanie go z dysku prawdopodobnie będzie wolniejsze niż to, co robisz teraz. rzecz?

Oto inny sposób, który wymaga tylko 2 pętli. Chodzi o to, aby zwiększyć pierwszy element, a jeśli ta liczba przekroczy, zwiększyć następny.

Zamiast wyświetlać dane, możesz użyć currentValues.Clone i dodać tę sklonowaną wersję do swojej listy. Dla mnie to działało szybciej niż twoja wersja.

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

• Mam nadzieję, że ten kod działa, przekonwertowałem go z vb

Wszystkie twoje liczby są stałe w czasie kompilacji.

A co z rozwinięciem wszystkich pętli do listy (używając programu do pisania kodu):

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.

Powinno to przynajmniej zmniejszyć obciążenie pętli for (jeśli takie istnieją).

Nie znam języka C # za dużo, ale wydaje się, że istnieją pewne sposoby serializacji obiektów. A co, jeśli właśnie wygenerowałeś tę listę i serializowałeś ją w jakiejś formie? Nie jestem jednak pewien, czy deserializacja jest szybsza niż tworzenie listy i dodawanie elementów.

Czy chcesz, aby wynik był tablicą tablic? Przy obecnej konfiguracji długość wewnętrznych tablic jest stała i może być zastąpiona strukturami. Pozwoliłoby to na zarezerwowanie całej rzeczy jako jednego ciągłego bloku pamięci i zapewniłby łatwiejszy dostęp do elementów (nie jestem pewien, jak później użyjesz tej rzeczy).

Poniższe podejście jest znacznie szybsze (41 ms vs 1071 ms dla oryginału na moim pudełku):

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

A co z użyciem Parallel.For()go uruchomić? (Optymalizacja struktury docenia @Caramiriel ). Nieznacznie zmodyfikowałem wartości (a to 5 zamiast 2), więc jestem bardziej pewien wyników.

    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() jest metodą prywatną, zdefiniowaną jako:

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

W moim systemie ta wersja działa około 6 razy szybciej (1,718 sekundy w porównaniu z 0,266 sekundy).

Niektóre z Twoich liczb mieszczą się w całości na całkowitej liczbie bitów, więc możesz je „spakować” z numerem wyższego poziomu:

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

Oczywiście sprawia to, że kod jest mniej czytelny, ale zaoszczędziłeś jedną pętlę. Można to zrobić za każdym razem, gdy jedna z liczb jest potęgą dwóch, czyli w twoim przypadku jest to siedem razy.

Oto inne rozwiązanie. Poza VS działa tak szybko, jak 437,5 ms, czyli o 26% szybciej niż oryginalny kod (593,7 na moim komputerze):

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