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.