• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Optymalizacja czasu wykonania programu konsolowego opartego o generator kombinacji

VPS Starter Arubacloud
+2 głosów
887 wizyt
pytanie zadane 11 sierpnia 2019 w Offtop przez tothk2a11 Początkujący (290 p.)
edycja 14 sierpnia 2019 przez tothk2a11

Witam,

Szukam sposobu na skrócenie czasu wykonywania obliczeń przez mały programik konsolowy

Napisałem mały program konsolowy który generuje kolejne kombinacje bez powtórzeń. Sumuje składniki kombinacji i zlicza kombinacje o tej samej sumie.

Programik hula aż miło. Ale kombinatoryka w pewnym momencie stawia go przed ścianą (ścianą czasu wykonywania). Dla dużych zbiorów liczbowych składających się z maksymalnie 10 elementowych kombinacji, czas jego wykonania jest sporym problemem. 

Test dla największego zbioru jaki wykonałem (dla k=10, n=70), trwał niecałe 7 godzin. Zależność czasu wykonania od liczby kombinacji, jest niestety funkcją potęgową. 

 

 

 

 

 

 

Program w czasie t=24201,7s wykonał  obliczeń na C=396 704 524 216 kombinacjach.

Co daje prędkość V = 16 391 597 kombinacji na sekundę. 

Problem  w tym że chciał bym wykonać obliczenia dla wszystkich zbiorów kombinacji od (k=10, n=10), (k=10, n=92). Szacunkowo to nie całe 47 dni ciągłej pracy. 

Jak zwiększyć wydajność pracy takiego programiku. W związku z tym mam do zainteresowanych i bardziej obeznanych kilka pytań: 

1)  Na co dzień używam code block (17.12) który kompiluje mi to na aplikacje 32-bitową. 

    >>>> Czy zmiana kompilatora na 64 bitowy zwiększy wydajność aplikacji.

2) Z tego co widzę w podglądzie procesów system (win7) przydziela mi maksymalnie 50 % dostępnej mocy obliczeniowej procesora.

    >>>> Idzie to jakoś zwiększyć??? ustawienia priorytetu mam na maksymalne.

3) Asem z programowania nie jestem, na co dzień nie mam z tym kontaktu. Zapewne da się zoptymalizować sam kod programu. Jeśli ma ktoś jakieś jakieś uwagi, lub propozycje jak to usprawnić to czekam na sugestię. 

4) Może jakiś inny algorytm zastosować i napisać coś wydajniejszego.  
 


// na każdej wygenerowanej kombinacji wykonuje sumę składników a wynik zapisuje w tabA
// // Generator kombinacji - generuje dowolne k-elementowe kombinacje z n-elementowego zbioru sk³adników, w porz¹dku leksykonograficznym dane zapisuje w pliku
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <conio.h>
#include <time.h>
#include <windows.h>

using namespace std;


int main()
{//1p



 int k=10;            // kombinacja k-elementowa
 int n=24;            // liczba elementów zbioru



 cout << "podaj liczbe element\242e kombinacji\nk = ";
 cin >> k;
 cout << "podaj rozmiar zbioru\nn = ";
 cin >> n;

    ostringstream oss1, oss2 ; //strumien pobierajacy dane ze zmiennych
    oss1 << k;
    oss2 << n;

 cout << "\nWygenerowane dane zostanom zapisane w pliku tekstowym: C:/Users/HP-G72/Desktop/rozkladSum k = " + oss1.str()+ ", n = " + oss2.str()+ ".txt\n\n";

//POCZĄTEK POMIARU CZASU
float t0 = GetTickCount();

string const daneDoOdczytu("C:/Users/HP-G72/Desktop/rozkladSum k = " + oss1.str()+ ", n = " + oss2.str()+ ".txt"); // lokalizacja pliku do odczytu/zapisu

//tablica do przechowywania danych
//tablica robocza - po sumowaniu każdej kombinacji odpowiednia zmienna +1

    int sumaMax = k*(n - 0.5*k + 0.5 );
    int sumaMin = k*(0.5*k + 0.5 );
    int liczbaPrzedzialow = sumaMax-sumaMin+1;

    int x = liczbaPrzedzialow; //liczba elementów/ SZEROKOKOŚĆ TABLICY


    int tabA[sumaMax+1];
    int *ws[sumaMax+1];

    for (int i=0; i<sumaMax+1; i++)
    {

        ws[i]=&tabA[i];
        tabA[i] = 0;

    }
//tablica na poszczegulne elementy kombinacji tablica k elementowa
    int a[k];
    int *wa[k];

        for (int i=0; i<k; i++)
    {
        wa[i]=&a[i];
        *wa[i] = 0;

    }

//Generator kombinacji + operacje na wygenerowanej kombinacji

    //int licznik=1;

    int z=k-1;

    //generowanie pierwszej kombinacji
    int suma=0;

        for (int i=0; i < k ; i++)
        {
            a[i]=i+1;
            suma += a[i];
        }

        //suma 10 elementów kombinacji
        tabA[suma]++;   //suma 10 elementów kombinacji

    //*******************************
    //generowanie kolejnych kombinacji

        for (int i=0; z>=0; i++) // warunek koñca generowania kombinacji
        {
            if (a[z]< (n-(k-z-1))) // sprawdz czy ostatni element mo¿na powiêkszyæ
            {
                a[z]++; // jeœli warunek spe³niony, ostatni element kombinacji +1
                        // ustaw kolejne elementy kombinacji o 1 wieksze od poprzednich
                while (z+1<k)
                {
                    a[z + 1] = a[z] + 1;
                    z++;
                }
                //licznik++;

                //operacje na wygenerowanej kombinacji
//TU BĘDZIE PODSTAWIENIE NUMERU ELEMENTU NA MASE

                suma=0;
                for (int i=0; i<k; i++)
                {
                    suma += a[i];
                }

                tabA[suma]++;
//KONIEC OPERACJI NA POJEDYŃCZEJ KOMBINACJI

            //dalszy ciąg generatora kombinacji
            }
            else
               {
                   z--;
               }
        } //KONIEC PRACY GENERATORA

//KONIEC POMIARU CZASU
//***********************************************************
 float t1 = GetTickCount();

//cout<<t0<<"\n"<<t1;
//cout<<"\n"<<(t1-t0)/1000;


//ZAPIS DANYCH DO PLIKU

    fstream plik; // deklaracja zmiennej plikowej
        plik.open(daneDoOdczytu.c_str(), ios::app); // otwarcie pliku

        //pocz¹tek zapisu danych w pliku - formatowanie wiersza
        plik <<(t1-t0)/1000 <<",";

        for (int i=sumaMin; i < sumaMax+1 ; i++)
        {
            plik << tabA[i] << ", ";
        }
        plik << "\n";

        plik.close();


 //getch();
 return 0;

}

Jak działa program (co jest w kodzie):

> Na start deklaruje się liczbę elementów kombinacji (k) i liczbę elementów zbioru (n).

>> Rezerwuje pamięć na zliczanie sum (int tabA[]), oraz na przechowywanie elementów kombinacji (int a[]).

>>> Generowanie pierwszej kombinacji w porządku leksykograficznym + sumowanie poszczególnych składników kombinacji, które realizuje w tej samej pętli. Po wyjściu z pętli  zwiększam o 1 wartość zmiennej odpowiadającej sumie składników.

>>>> Generowanie kolejnej kombinacji w porządku leksykograficznym + sumowanie poszczególnych składników + zliczenie kolejnej sumy.

         > Pętla for wykonująca się dla reszty kombinacji - wykonuje się dopóki warunek pętli jest spełniony

         >> if sprawdza czy ostatni element można powiększyć, jeśli tak zwiększa ostatni element o 1, generując kolejne kombinacje aż do maksymalnego elementu zbioru. Jeśli warunek nie jest spełniony zmniejsza o 1 kolejny element od końca. W następnej pętli for sprawdza ponownie warunek i generuje kolejne kombinację.

>>>>> Po wykonaniu wszystkich kombinacji i zliczeniu ilości sum składników zapisuje dane w pliku. Poza tym sprawdza czas wykonania programu.

komentarz 11 sierpnia 2019 przez tkz Nałogowiec (42,000 p.)

Zainteresuj się std::next_permutation, std::count_if wydaje mi się, że może pomóc.

Edit: albo w ogóle biblioteka algorithm https://en.cppreference.com/w/cpp/algorithm i tym https://en.cppreference.com/w/cpp/chrono bo nagłówek windows.h nie jest najlepszym wyjściem. 

komentarz 11 sierpnia 2019 przez Aisekai Nałogowiec (42,190 p.)
edycja 11 sierpnia 2019 przez Aisekai
Mógłbyś bardziej wyjaśnić problem, oraz podać jakieś przykładowe dane? Najlepiej dla jakiegoś małego inputu. Czy chodzi Ci o to, że dostajesz jakiś zbiór n elementowy, wybierasz z niego k elementów (mogą się powtarzać, w sensie zbiór n może składać się z k x n[0]) i zwraca strukturę w której są elementy przedstawiające ilość kombinacji mających takie same sumy, tak? Czy mogą istnieć dwa takie zbiory jak np: {1,2,3,4} i {2,1,3,4}? Czy jeżeli elementy będą się powtarzać, ale w innej kolejności to bierzemy pod uwagę tylko jeden? Czy elementy są różne? Czy początkowy zbiór może składać się z {1,1,1,1,1,2}? Mamy zbiór wejściowy to: [1,1,3,1], czy zbiór wyjściowy składający się z {n0], n[3]} a zbiór {n0], n[1]} to te same zbiory (czyli tylko jeden bierzemy pod uwagę), czy to są dwa różne zbiory?
komentarz 11 sierpnia 2019 przez adrian17 Ekspert (344,100 p.)
Szybkie spostrzeżenie, które może mieć lub nie mieć znaczenia: to wygląda na rozkład normalny, nie?
komentarz 11 sierpnia 2019 przez tothk2a11 Początkujący (290 p.)
edycja 12 sierpnia 2019 przez tothk2a11

Zasadniczo to faktycznie nie napisałem co jest celem tego programu. 

Program generuje kombinacje bez powtórzeń k-elementowych ze zbioru n-elementowego (każdy element może występować tylko raz w kombinacji). Sumuje składniki każdej kombinacji i zlicza ile kombinacji miało tą samą sumę. Zwraca ile było kombinacji dla sumy minimalnej wszystkich sum pośrednich i sumy maksymalnej.  W rezultacie daje rozkład wszystkich kombinacji na pule o tej samej wartości sumy. 

Na przykładzie totolotka, dajmy na to duży lotek.

Losujemy 6 kombinacji z 49. k=6 n=49. Wszystkie możliwe kombinacje to C=n! / k!(n-k)!

W tym przypadku program generuje pierwszą kombinacje

[1][2][3][4][5][6] => suma(min)  k-elementów = 21  jest to suma minimalna wszystkich kombinacji 

Ostatnia kombinacja to [44][45][46][47][48][49] => suma(max)  k-elementów = 279  jest to suma maksymalna.

Program ma wygenerować wszystkie kombinacie pośrednie policzyć ich sumy i podać rozkład wszystkich kombinacji na podstawie ich sumy. Na podanym przykładzie rezultatem będzie. 

[21][22][23][24][25][26]  ...   [274][275][276][277][278][279]   sumy w pełnym zakresie    

[ 1 ][ 1 ][ 2 ][ 3 ][ 5 ][ 7 ]  ...   [  7  ][  5  ][  3  ][  2  ][  1  ][  1  ]  ile kombinacji ma tą samą sumę.

Istotny jest sam rozkład wartości który posłuży do  dalszych obliczeń. A bardziej dokładniej o różnice między kolejnymi ilościami wartości sum.

 

Cechą charakterystyczną dla dowolnego n i k<=n każdego rozkładu jest jego symetria względem środkowego przedziału którą można opisać krzywą gaussa.

Zakres pracy programu jaki mnie interesuje jest dla k=10 (wartość maksymalna ) i n=92 (wartość maksymalna )  

komentarz 11 sierpnia 2019 przez tothk2a11 Początkujący (290 p.)
A podchodząc do tego od strony matematycznej. Da się policzyć ile wartości znajdzie się w poszczególnym przedziale dla sumy kombinacji z dowolnym k i n.

2 odpowiedzi

+1 głos
odpowiedź 12 sierpnia 2019 przez mokrowski Mędrzec (155,460 p.)
wybrane 12 sierpnia 2019 przez tothk2a11
 
Najlepsza
Co do kodu:

1. Stosujesz tablice VLA https://en.wikipedia.org/wiki/Variable-length_array które nie są elementem C++

2. Zbędne jest generowanie kombinacji jeśli: wiesz że rozkład będzie symetryczny, wiesz ile ich jest :) (zerknij do wyników)

3. Masz komentarze które nie przystają do kodu... co to jest "U BĘDZIE PODSTAWIENIE NUMERU ELEMENTU NA MASE" ?

4. Wydziel funkcje.

Co do algorytmu:

1. Wiedząc że rozkład jest normalny, nie ma potrzeby obliczania tych sum... chyba że masz wyraźną intencję..

2. To że system przydziela Ci 50 % czasu CPU, związane jest z pojedynczym wątkiem na procesorze. Jeśli program będzie wielowątkowy, aplikacja przyśpieszy. Tu wątki (jeśli już), będą sensowne do wydzielenia prac kolejnych kombinacji rozkładu.
komentarz 12 sierpnia 2019 przez tothk2a11 Początkujący (290 p.)
edycja 12 sierpnia 2019 przez tothk2a11

Dzięki za istotne uwagi.

1) Co do tablic: to mógł byś mi wyjaśnić co jest nie tak. Nie bardzo wiem, co w tym wypadku jest nie tak. Za skromną wiedzę w tym temacie posiadam. Jakiś link do przykładu jak to powinno wyglądać dla C++.

2) Opierając się o matematyczne wykorzystanie rozkładu normalnego otrzymuje wyniki o nie całkowitych wartościach przedziałów.Powoduje to wprowadzenie drobnego błędu wynikającego z zaokrąglaniem, który na dużych liczbach daje znaczne rozbieżności z rzeczywistością - średni +/-1,5%.   

Co do braku konieczności generowania kombinacji  to BARDZO CELNA UWAGA. Tu może leżeć klucz do sukcesu. 

Po sprawdzeniu jak wygląda zależność wartości sumy od nr kombinacji, mam pewne przemyślenia jak to wykonać innym algorytmem.

Po przejrzeniu jak wielkość zbioru wpływa na rozkład sum. Wnioskuje że da się to opisać rekurencyjnie za pomocą ciągu liczbowego. Co w przypadku programowania wpłynie na złożycie pamięci. 

Tu mam jedno pytanie: Czy takie podejście wpłynie na skrócenie czasu potrzebnego na otrzymanie wyniku.

 

3) Komentarze to faktycznie niektóre mogą być niespójne. Program w założeniu miał wykonywać parę dodatkowych obliczeń na wygenerowanej kombinacji. A przy wycinaniu kodu nie usuwałem komentarzy - mój błąd.

4) Co do funkcji. Z tego co wiem na pewno funkcje zwiększają przejrzystość kodu i jego funkcjonalność. Ale czy wpływa to na wydajność obliczeniową programu.

5) Co do wątków to na razie po za moim zasięgiem. Na razie przerabiam podejście obiektowe. Ale to tylko hobbystycznie. Na co dzień przerzucam stal na budowie co ma się nijak do programowania.

W weekend pewnie przetestuje inne rozwiązanie tego problemu. O wynikach pewnie napisze po testach wydajności.

komentarz 12 sierpnia 2019 przez mokrowski Mędrzec (155,460 p.)

Ad. 1

Tablice VLA to tablice alokowane na stosie z wielkością obliczoną w trakcie działania programu. To nie jest właściwość C++. W C++ wszystkie wielkości tablic alokowanych na stosie, powinny być stałe i nie obliczone w trakcie działania programu. Jeśli program oblicza/przyjmuje wielkość tablicy w trakcie działania, powinieneś ją alokować na stercie (przez new). To .. uciążliwe i dlatego w Twoim przypadku lepiej użyć std::vector (a nie tablic w ogólności).

Ad. 2

Jeszcze raz zerknij do wyników. One zawsze są symetryczne więc wystarcza policzenie tylko do połowy przedziału.

Ad. 4

Funkcje nie wpłyną na wydajność. Jak sam widzisz, masz w innym miejscu wąskie gardła algorytmu. Nawet jeśli będziesz chciał "urwać ms", to uczynisz funkcje inline i wstawią się w miejscu wykonania.

Ad. 5

Tę optymalizację, zostaw na koniec.

Łatwiej kombinacje zrobisz tak:

#include <vector>
#include <iostream>
#include <algorithm>

void show_combination(unsigned n, unsigned k) {
    // Kontener "z filtrem"
    std::vector<bool> vec(n);
    std::fill(vec.begin(), vec.begin() + k, true);

    do {
        for(auto i = 0UL; i < n; ++i) {
            if(vec[i]) {
                std::cout << (i + 1) << ' ';
            }
        }
        std::cout << '\n';
    } while(std::prev_permutation(vec.begin(), vec.end()));
}

int main() {
    unsigned n;
    unsigned k;
    // TODO: Sprawdzenie poprawności wprowadzenia danych n i k.
    std::cout << "Podaj wartość n: ";
    std::cin >> n;
    std::cout << "Podaj wartość k: ";
    std::cin >> k;
    std::cout << "Kombinacje liczb z zakresu [1, n] to:\n";
    show_combination(n, k);
}

 

komentarz 12 sierpnia 2019 przez mokrowski Mędrzec (155,460 p.)
edycja 12 sierpnia 2019 przez mokrowski

PS. Jeśli "tanio" chcesz poczuć różnicę z optymalizacji, dodaj do kompilacji flagi:

-O3 -march=native

ta pierwsza to "minus Ooo trzy". Przy dłuższych obliczeniach, będzie widać różnicę choć to nie znaczy że algorytm jest optymalny.

Z premedytacją (trochę inne założenia co do wyniku) uruchomiłem następujący program:

include <vector>
#include <map>
#include <iostream>
#include <algorithm>

std::map<unsigned, unsigned> calculate_sum_combination(unsigned n, unsigned k) {
    std::vector<bool> vec(n);
    std::fill(vec.begin(), vec.begin() + k, true);
    std::map<unsigned, unsigned> mp;

    do {
        auto sum = 0UL;
        for(auto i = 0UL; i < n; ++i) {
            if(vec[i]) {
                sum += i + 1;
            }
        }
        ++mp[sum];
    } while(std::prev_permutation(vec.begin(), vec.end()));
    return mp;
}


int main() {
    unsigned n = 35;
    unsigned k = 10;
    auto mp = calculate_sum_combination(n, k);
    for(const auto& pr: mp) {
        std::cout << pr.first << ' ' << pr.second << '\n';
    }
}

Na platformie Raspberry Pi 3 B+ (więc nie najnowszej), przy opcjach kompilatora bez optymalizacji:

g++ -O0 -Wall -Wextra -pedantic -o combination combination.cpp

Czas wykonania dla takiej kompilacji to:

20 min 52 sec.

Natomiast dla opcji kompilacji (z optymalizacją):

g++ -O3 -march=native -Wall -Wextra -pedantic -o combination combination.cpp

to:

1 min 4 sec.

Dla n=70 k= 10 i optymalizacji, jeszcze się liczy :) wstawię czas jak skończy jeśli będę miał cierpliwość.

komentarz 14 sierpnia 2019 przez tothk2a11 Początkujący (290 p.)
edycja 14 sierpnia 2019 przez tothk2a11

Dzięki za zgrabnie napisany kod - potestuje w weekend. Chwilowo nie mam czasu, a muszę najprawdopodobniej przeinstalować code block c++. W kodach które podałeś powyżej nie kompiluje mi typu: auto na zastępczy typ zmiennej. 

Aby działało muszę ręcznie w kodzie przydzielić odpowiedni typ zmiennej przed kompilowaniem kodu.

W drugim przypadku (tym z sumą) przy kompilacji wyrzuca mi błąd w 28 linii kodu. Najprawdopodobniej wina kompilatora. Będę miał więcej czasu to wgryzę się w temat.

Co do uwagi odnośnie Ad. 2 z poprzedniego komentarza. Wiem o co ci chodzi, ale niestety w tym wypadku to się nie sprawdza.

Przebieg zależności wielkości sumy od nr kombinacji pokazuje że wygenerowanie połowy kombinacji nie wystarczy do dokładnego zliczenia wszystkich sum.

Liczba wszystkich sum ze środka przedziału znana jest dopiero pod koniec wygenerowanych kombinacji. Wygenerowanie połowy kombinacji nic nie daje. Ponieważ dokładnie w połowie wszystkich kombinacji suma wraca do wartości o 10 większych od sumy minimalnej. 

Z tego co mi się wydaje to pierwsza kombinacja z drugiej połowy kombinacji przyjmuje wartości n-k większe od sumy minimalnej. Tego nie jestem jeszcze pewien, ale jeśli to prawda to mam już pewien pomysł jak dzięki temu skrócić czas obliczeń.

U mnie  n=70 k=10 liczył  prawie 7 godzin (6:43:22) na dość starym sprzęcie z wykorzystaniem połowy mocy obliczeniowej.  

Co do platformy Raspberry Pi 3 B+ to nawet nie byłem świadom o istnieniu takiego cudeńka. Nie jestem na bieżąco z rozwojem technologii IT odkąd poszedłem na studia, a to było ładnych kilka lat temu. Chemia strasznie uzależnia i zniewala umysł - dosłownie i w przenośni.   

komentarz 14 sierpnia 2019 przez vector Dyskutant (9,200 p.)
Nie rozumiem po co explicite przeglądać te wszystkie permutacje. Według tego sposobu co opisałem można dostać te same dane w dużo krótszym czasie np.: dla (n, k) = (70, 10) liczy się w 0.01s
komentarz 18 sierpnia 2019 przez tothk2a11 Początkujący (290 p.)

@mokrowski,

Interesuje mnie jak zbudowana jest ta funkcja:

prev_permutation(vec.begin(), vec.end()))

Można gdzieś znaleźć dokumentacje co do jej budowy. Chciał bym jej zajrzeć w przysłowiowe bebechy i zrozumieć jak działa. Czy to wiedza tajemna znana tylko twórcom tej funkcji???

Z tego co znajduje w sieci to same sposoby jej implementacji i opisy jej zastosowania.

Na podstawie zaproponowanego kodu napisałem identyczny programik który liczy dokładnie to samo co napisałem samodzielnie. Z porównania wydajności obu wersji. program z wykorzystaniem wspomnianej funkcji wypada nieznacznie gorzej (we wszystkich testowanych zakresach danych liczy około 2% dłużej).

 

Co do samego problemu związanego z czasem wykonywania to najlepszy rezultat uzyskałem zmieniając system operacyjny na Linuksa. Optymalniej wykorzystuje zasoby sprzętowe (wzrost wydajności obliczeniowej o około 30 % na tym samym sprzęcie). 

 

komentarz 18 sierpnia 2019 przez mokrowski Mędrzec (155,460 p.)
edycja 18 sierpnia 2019 przez mokrowski

https://en.cppreference.com/w/cpp/algorithm/next_permutation

https://en.cppreference.com/w/cpp/algorithm/prev_permutation

Na stronie głównej, https://en.cppreference.com/ masz pełną dokumentację biblioteki standardowej języka C++.

Włącz wersję języka C++11 bądź większą. Dla gcc to przełącznik -std=c++11 

PS (dodane):

Myślę że ten prosty przykład pokaże Ci jak działa ten prosty filtr dla elementów z kombinacji. Jeśli nie będziesz miał "efektu AHA!", to pytaj dalej :-)

#include <algorithm>
#include <vector>
#include <iostream>

void show_container(const std::vector<bool>& vec) {
    for(const auto b: vec) {
        std::cout << b << ' ';
    }
    std::cout << '\n';
}

void show_combination_filter(unsigned n, unsigned k) {
    std::vector<bool> vec(n);
    std::fill(vec.begin(), vec.begin() + k, true);

    do {
        show_container(vec);
    } while(std::prev_permutation(vec.begin(), vec.end()));
}

int main() {
    unsigned n = 10;
    unsigned k = 5;
    show_combination_filter(n, k);
}

Co do optymalizacji, agresywna (którą Ty zastosowałeś od razu stosując tablice), jest wykonywana na końcu. Kiedy już naprawdę zależy Ci na wyciśnięciu 7-mych potów z algorytmu. Nie wiem czy 2% jest na tyle istotne w Twoim przypadku. W praktyce liczy się balans między wydajnością a czytelnością. Podnosisz jakość kodu, stosując rozwiązania z biblioteki standardowej bo są (raczej) niezawodne i mocno zoptymalizowane.

Z kodu który podałem, możesz wycisnąć jeszcze trochę zmieniając std::map na std::unordered_map. Tyle tylko że i tak (jak zrozumiałem), kiedyś będziesz zmuszony zapłacić dodatkowym sortowaniem wyników. Chcesz przecież uzyskać rozkład. Być może jak zrobisz to na końcu 'hurtem", coś zyskasz (w mojej ocenie dla małych zakresów n i k jak to badałem ~5%)

Co do Code::Block, raczej instaluj go bez kompilatora. Domyślnie dostępny w paczkach do instalacji jest już mocno... posunięty. Jeśli będziesz chciał, prześlę Ci via prv instrukcję instalacji MinGW-W64.

Z ciekawości nawet napisałem wersję z podziałem na wątki. Myślę jednak że nieco zaciemnia problem ale jeśli chcesz to ją tu umieszczę.

+1 głos
odpowiedź 12 sierpnia 2019 przez vector Dyskutant (9,200 p.)

Jeżeli interesuje cię tylko rozkład sum k-elementowych podzbiorów zbioru {1, 2, ..., n} to da się zmniejszyć złożoność obliczeniową liczenia tego w porównaniu z przeglądaniem wszystkich podzbiorów po koleii i ich sumowaniem.

Można sobie zdefiniować tablicę trójwymiarową dp, gdzie dp[x][y][z] oznacza liczbę y-elementowych podzbiorów zbioru {1, 2, ..., n} takich że każdy element podzbioru nie jest większy od z oraz suma elementów podzbioru jest równa x.

Jak sobie popatrzymy na podzbiory jakie zlicza dp[x][y][z] to każdy taki podzbiór zawiera 'z' jako element albo nie. Jeżeli zawiera 'z' jako element to wystarczy go wyrzucić i dostajemy bijekcję z dp[x-z][y-1][z-1]. Jeżeli nie zawiera 'z' jako element to mamy bijekcje z dp[x][y][z-1]. Zatem zachodzi własność rekurencyjna dp[x][y][z] = dp[x][y][z-1] + dp[x-z][y-1][z-1]. (Oczywiście to nie jest dowód tylko intuicja. formalnie trzeba zdefiniować te zbiory i pokazać że jakaś tam funkcja to bijekcja, ale z powyższym opisem to już nie jest trudne).

Rozkład sum podzbiorów dla konkretnych n, k leży w dp[x][k][n] dla x = 0, 1, ..., (n-k+1) + (n-k+2) + ... + n.

wymiary dp[x][y][z] można oszacować od góry poprzez n*k, k, n. dla każdej wartości w dp wykonujemy stałą liczbę operacji więc dostajemy złożoność (nk)^2.

Jak ktoś chce to jeszcze dorzucam implementacje w c++:

template <typename T>
using v1 = std::vector<T>;

template <typename T>
using v2 = std::vector<v1<T>>;

template <typename T>
using v3 = std::vector<v2<T>>;

// złożoność obliczeniowa O((nk)^2)
std::vector<int64_t> dp_solve(const int64_t n, const int64_t k) {
    // max_sum = (n - k + 1) + (n - k + 2) + ... + n
    const int64_t max_sum = (n + 1) * n / 2 - (n - k + 1) * (n - k) / 2;

    // dp[x][y][z] określa liczbę y-elementowych podzbiorów zbioru {1, 2, ..., n}
    // których największy element jest nie większy niż z, oraz ich suma wynosi x
    // dp[x][y][z] = dp[x][y][z-1] + dp[x-z][y-1][z-1]
    v3<int64_t> dp(max_sum + 1, v2<int64_t>(k + 1, v1<int64_t>(n + 1, 0)));
    
    // przypadek brzegowy 0-elementowy podzbiór o sumie 0
    for (int64_t z = 0; z <= n; ++z) {
        dp[0][0][z] = 1;
    }

    for (int64_t z = 1; z <= n; ++z) {
        for (int64_t y = 1; y <= k; ++y) {
            for (int64_t x = 1; x <= max_sum; ++x) {
                dp[x][y][z] = dp[x][y][z-1] + (x >= z ? dp[x-z][y-1][z-1] : 0);
            }
        }
    }

    // result[i] = liczba podzbiorów k-elementowych zbioru {1, 2, ..., n} o sumie i
    std::vector<int64_t> result(max_sum+1);
    for (int64_t i = 0; i <= max_sum; ++i) {
        result[i] = dp[i][k][n];
    }
    return result;
}

 

komentarz 14 sierpnia 2019 przez tothk2a11 Początkujący (290 p.)

Dzięki za odpowiedz. 

Z góry zaznaczę że mój mały rozumek nie za bardzo ogarnia całości kodu zawartego w implementacji. Całość mojej wiedzy opiera się na paru godzinach kursu Pasja informatyki. Z tego powodu wielu rzeczy jeszcze nie ogarniam.

Rozumiem idę przedstawionego przez ciebie algorytmu, ale muszę się przegryźć się przez  niejasne dla mnie elementy tego kodu, np: nie ogarniam za co odpowiada poniższy zapis w 28 linii kodu. 

               (x >= z ? dp[x-z][y-1][z-1] : 0);

 

Co do przeglądania wszystkich permutacji to i tak chyba nieuniknione. Każda z wygenerowanych permutacji będzie jeszcze podstawą do innych obliczeń i sortowania danych eksperymentalnych.     

komentarz 14 sierpnia 2019 przez vector Dyskutant (9,200 p.)

Jeżeli przeszkadza ci linijka

// (1)
dp[x][y][z] = dp[x][y][z-1] + (x >= z ? dp[x-z][y-1][z-1] : 0);

możesz ją zastąpić tym:

dp[x][y][z] = dp[x][y][z-1];
if (x >= z) {
    dp[x][y][z] += dp[x-z][y-1][z-1];
}

program będzie liczył dokładnie to samo. (Taka składnia (1) zwie się ternary operator).

Jeżeli koniecznie musisz przeglądać wszystkie permutacje to nie znam szybszego (jednowątkowego) sposobu ich przeglądania innego niż  mokrowski zaproponował.

Podobne pytania

+1 głos
1 odpowiedź 158 wizyt
0 głosów
1 odpowiedź 247 wizyt
0 głosów
2 odpowiedzi 366 wizyt

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...