Ciao a tutti, sto implementando una classe in C++ finalizzata a ricreare le varie sequenze del calcolo combinatorio: permutazioni (semplici e con ripetizione), combinazioni (semplici e con ripetizione), disposizioni (semplici e con ripetizione) e ripartizioni.
Sembra funzionare tutto, ma, cercando eventuali ottimizzazioni relativamente alle permutazioni, ho notato dei tempi di esecuzione che non riesco a capire. In pratica ho notato che in modalità release utilizzare la funzione sulle permutazioni da me implementata attraverso l'interfaccia di una classe determina un tempo d'esecuzione che è più del doppio rispetto al caso in cui non utilizzo alcuna classe.
Riporto di seguito un codice per spiegare meglio quello che intendo:
Questo l'output compilando senza spuntare alcun flag di ottimizzazione:
Questo invece quello che ottengo compilando con -O3:
Come mai la versione che utilizza l'interfaccia di una classe è così tanto più lenta rispetto a quella che invece non ne fa uso?
Sembra funzionare tutto, ma, cercando eventuali ottimizzazioni relativamente alle permutazioni, ho notato dei tempi di esecuzione che non riesco a capire. In pratica ho notato che in modalità release utilizzare la funzione sulle permutazioni da me implementata attraverso l'interfaccia di una classe determina un tempo d'esecuzione che è più del doppio rispetto al caso in cui non utilizzo alcuna classe.
Riporto di seguito un codice per spiegare meglio quello che intendo:
C++:
#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
using namespace std;
using namespace std::chrono;
void scambia_valori(unsigned int &a, unsigned int &b)
{
unsigned int temp = a;
a = b;
b = temp;
}
bool inverti_array(unsigned int *const v, unsigned int dim)
{
for(unsigned int i_sx = 0, i_dx = dim - 1; i_sx < i_dx; scambia_valori(v[i_sx++], v[i_dx--]));
return true;
}
class A
{
private:
unsigned int *u;
unsigned int k;
public:
A(const unsigned int N);
~A();
bool permutazione_S_successiva_();
};
A::A(const unsigned int n)
{
u = new unsigned int[k = n];
for(unsigned int i = 0; i < k; ++i)
{
u[i] = i;
}
}
A::~A()
{
delete[] u;
}
inline bool A::permutazione_S_successiva_()
{
unsigned int i = k;
while(--i && u[i - 1] > u[i]);
if(i)
{
inverti_array(u + i, k - i);
for(unsigned int j = i; j < k; ++j)
{
if(u[i - 1] < u[j])
{
scambia_valori(u[i - 1], u[j]);
return true;
}
}
}
return false;
}
bool permutazione_S_successiva_2(unsigned int *u, const unsigned int k)
{
unsigned int i = k;
while(--i && u[i - 1] > u[i]);
if(i)
{
inverti_array(u + i, k - i);
for(unsigned int j = i; j < k; ++j)
{
if(u[i - 1] < u[j])
{
scambia_valori(u[i - 1], u[j]);
return true;
}
}
}
return false;
}
int main()
{
unsigned int n = 12;
uint64_t cont;
//----------------------------------
auto start1 = high_resolution_clock::now();
cont = 0;
A a(n);
do
{
++cont;
}
while(a.permutazione_S_successiva_());
auto stop1 = high_resolution_clock::now();
cout << "perm. succ. con classe " << cont << " " << duration_cast<milliseconds>(stop1 - start1).count() << "ms" << endl;
//----------------------------------
//----------------------------------
auto start2 = high_resolution_clock::now();
cont = 0;
unsigned int *u = new unsigned int[n];
for(unsigned int i = 0; i < n; ++i)
{
u[i] = i;
}
do
{
++cont;
}
while(permutazione_S_successiva_2(u, n));
delete[] u;
auto stop2 = high_resolution_clock::now();
cout << "perm. succ. senza classe " << cont << " " << duration_cast<milliseconds>(stop2 - start2).count() << "ms" << endl;
//----------------------------------
//----------------------------------
auto start3 = high_resolution_clock::now();
cont = 0;
unsigned int *v = new unsigned int[n];
for(unsigned int i = 0; i < n; ++i)
{
v[i] = i;
}
do
{
++cont;
}
while(next_permutation(v, v + n));
delete[] v;
auto stop3 = high_resolution_clock::now();
cout << "std::next_permutation " << cont << " " << duration_cast<milliseconds>(stop3 - start3).count() << "ms" << endl;
//----------------------------------
}Questo l'output compilando senza spuntare alcun flag di ottimizzazione:
Codice:
perm. succ. con classe 479001600 20707ms
perm. succ. senza classe 479001600 19721ms
std::next_permutation 479001600 30232ms
Process returned 0 (0x0) execution time : 70.720 s
Press any key to continue.Questo invece quello che ottengo compilando con -O3:
Codice:
perm. succ. con classe 479001600 4777ms
perm. succ. senza classe 479001600 2176ms
std::next_permutation 479001600 2946ms
Process returned 0 (0x0) execution time : 9.961 s
Press any key to continue.Come mai la versione che utilizza l'interfaccia di una classe è così tanto più lenta rispetto a quella che invece non ne fa uso?
Ultima modifica:
