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


85

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.


1
Spróbuj użyć linq, a jeśli używasz procesora wielordzeniowego, to Parrallel.for
Jalpesh Vadgama Kwietnia

1
na podstawie tego, co widzę, nie są to permutacje, ale kombinacje kilku bardzo małych (2-4 elementów) zestawów, czy to prawda, czy rzeczywiście chcesz wszystkie / niektóre permutacje z jednego zestawu?
Carsten

Zakładam, że przeszukałeś już bing.com/search?q=c%23+permutation+enumerable iz jakiegoś powodu (niewymienionego w poście) zdecydowałeś się na istniejące odpowiedzi, takie jak stackoverflow.com/questions/4319049/ ... Rozważ listę opcje, którym się przyjrzałeś i nie zdecydowałeś, aby to pytanie było lepsze.
Alexei Levenkov

3
Jeśli chodzi o wydajność: Możesz wstępnie przydzielić listę (konstruktor) i rozwinąć niektóre pętle, ale myślę, że to wszystko ... poza wstępnym obliczaniem i przechowywaniem tych liczb. Pętle (nad głową) są prawdopodobnie najbardziej kosztowne ze wszystkich, ponieważ wewnątrz ciała jest wykonywana niewielka liczba operacji.
Caramiriel

5
@benpage: Dlaczego musisz generować wszystkie kombinacje z góry? Dlaczego nie wygenerować kombinacji ze swojego indeksu, kiedy jej potrzebujesz?
Pieter Witvoet

Odpowiedzi:


61

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


1
To struktura, więc powinieneś być w porządku =) wszystkie są unikalne. Jest kopiowany podczas wywoływania List<T>.Addmetody.
Caramiriel

4
Jest to nawet szybsze, jeśli przydzielisz pojemność do listy ()
Eric

5
Uważaj na StackOverflow wyjątków przy przydzielaniu zbyt wiele obiektów na stosie.
Andrei Tătar

7
@ Andrew Nie rozumiem, o co ci chodzi. Ten kod nie jest cykliczny i ma minimalne użycie stosu.
CodesInChaos

3
@Andrew: To jest brak pamięci, a nie przepełnienie stosu. Dzieje się tak, ponieważ List<T>.Add()metoda wykracza poza to, co może przechowywać. Spowoduje to zmianę rozmiaru (podwoi rozmiar), co oznacza ponad 2 GB pamięci. Spróbuj dokonać wstępnej alokacji, używając nowego List <ByteBlock> (maxPerLevel.Aggregate (1, (x, y) => x * y)), chociaż jest to już `` losowe '', że potrzebujesz pełnego bloku 2 GB tych danych w pamięci. Zwróć również uwagę, że data.ToArray (); jest drogie, ponieważ w tym momencie zachowuje elementy w pamięci dwukrotnie. [przeformułowane]
Caramiriel,

33

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.


4
Podoba mi się twoja odpowiedź, ale stwierdzenie, że wszystkie inne odpowiedzi są wykładnicze, jest nieprawdą.
Ciastka

1
Jaka jest prędkość w porównaniu z odpowiedzią Caramiriel?
John Odom

17
„C-kiddy- #”, naprawdę? Wydaje się to zupełnie nie na miejscu.
KChaloux

2
I to robi: Math.DivRem
Caramiriel

1
Myślę, że na pewnym poziomie optymalizacja jest kwestią użycia. Na przykład, jeśli każda tablica ma być używana tylko raz, można uniknąć intensywnej alokacji pamięci, która jest moim zdaniem krytycznym wąskim gardłem. Ponadto, jeśli chcesz obliczyć całą wartość, powinieneś wykorzystać fakt, że wykonujesz pojedyncze przyrosty (tj. Przyrost +1), unikając dzielenia. To jest bardziej pomyślane jako „out of the box” answear lub prototypu, ja naprawdę nie starają się ją przyspieszyć, po prostu lubię to w ten sposób :)

14

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


1
Twoja druga sugestia to również znacząca oszczędność pod względem zużycia pamięci. (Ale chciałbym zauważyć, że zakłada, że ​​lista nie powinna się zmienić)
Taemyr

Potrzebuję utworzenia całej listy za jednym razem - nie mogę odwołać się do indeksu na liście.
benpage

@Taemyr Thanks. Zaktualizuję, aby odpowiednio to zauważyć. Jeśli implementacja naprawdę nalega, aby cała lista była wypełniona z góry, ta trzecia opcja oczywiście nie zadziała.
Ciastka

3
@benpage Dlaczego lista ma być wypełniona?
Taemyr

14

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

To świetna odpowiedź! Niestety działa wolniej niż zagnieżdżone pętle. Czy jest szansa, że ​​mógłbyś edytować za pomocą TPL?
benpage

niestety nadal dość wolniej.
benpage

1
@benpage Jest łatwy sposób, aby zrobić to co najmniej 2 razy szybciej. Musisz tylko zmienić typ wyników na int [,]. Spowoduje to przydzielenie całej pamięci tablicy w jednym wywołaniu. Nie jestem pewien, jak to odpowiada Twoim potrzebom (zmiana typu zwrotu).
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();

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

1
to działa dużo wolniej :(
benpage

8

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?


W rzeczywistości próbowałem wstępnie przydzielić zwykłą tablicę i wierz lub nie, jest wolniejszy. Jak powiedziałem powyżej, trzeba to utworzyć w locie, nie mogę tego raz obliczyć i zostawić.
benpage

naprawdę? wow - pracujesz z włączonymi optymalizacjami, prawda? (tylko pytam)
Carsten

Ach, to inna sprawa, zwykłe tablice [x, y] są przyjemne w użyciu, ale tablice tablic będą szybsze. stackoverflow.com/questions/597720/… z powodu tego, jak są one wdrożone pod maską w IL
gjvdkamp

5

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

3

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.


Serializacja to naprawdę świetny sposób myślenia nieszablonowy!
Joel B

Niestety maksima na liście są dynamiczne, nie mogę tego statycznie wpisać. Ale dobry pomysł!
benpage

2

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

Dobry pomysł - właściwie to właśnie zrobiłem w moim projekcie w świecie rzeczywistym - po prostu nie umieściłem go w oryginalnym rozwiązaniu ze względu na prostotę. Szukałem głównie lepszej alternatywy dla zagnieżdżonych pętli.
benpage

1

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


1
Zapewnia to fałszywe udostępnianie i prawdopodobnie będzie wielokrotnie wolniejsze.
gjvdkamp

Nieźle - niestety działa wolniej niż pętle for. FWIW Próbowałem z ALL Parallel.Forsi awaria VS!
benpage

@gjvdkamp Zaktualizowałem moją odpowiedź wersją równoległą, która moim zdaniem eliminuje fałszywy problem z udostępnianiem.
jdphenix

0

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.


Chciałbym dowiedzieć się więcej na temat tej odpowiedzi - czy mógłbyś ją rozwinąć?
benpage

Przepraszam za spóźnioną odpowiedź. m idzie od 0 do 3, co w postaci binarnej daje od 00 do 11, l od 0 do 2, co daje od 00 do 10, więc jeśli wydrukujesz je osobno, to da: 00 00 00 01 00 10 00 11 01 00 .. 10 11 Możesz połączyć je razem w jedną liczbę 4 bitów, od 0000 do 1011, i wybrać odpowiednie bity za pomocą maski lm & 3 sprawia, że ​​biwise i między lm a (11) b lm & 12 robi to samo z lm i (1100) b, a następnie przesuniemy się o dwa bity, aby otrzymać liczbę „rzeczywistą”. Swoją drogą, właśnie sobie uświadomiłem, że w tym przypadku wystarczy zrobić lm >> 2.
Fabien Dupont

0

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();
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.