- Code: Tout sélectionner
#ifndef TIMER_H_
#define TIMER_H_
#include
#include
#include
class Timer
{
public:
Timer() : ts(0)
{}
void start()
{
struct timeval tval;
gettimeofday(&tval, NULL);
ts = tval.tv_sec * 1000000 + tval.tv_usec;
}
double get() const
{
return get(ts);
}
double get(int refTime) const
{
struct timeval tval;
gettimeofday(&tval, NULL);
int end_time = tval.tv_sec * 1000000 + tval.tv_usec;
return static_cast(end_time-refTime) / 1000000.0;
}
void tic(){
struct timeval tval;
gettimeofday(&tval, NULL);
tics.push_back(tval.tv_sec * 1000000 + tval.tv_usec);
}
double toc(const std::string &message){
double a=toc();
std::cout0){
a = tics.back();
tics.pop_back();
}
return get(a);
}
private:
int ts;
std::list tics;
};
#endif /* TIMER_H_ */
- Code: Tout sélectionner
#include
#include "Timer.hpp"
template
void listFatal(){
if(k==1){
//skipped
return;
}
size_t stack[k];
for (size_t i = 0; i(stack); //i/o is the most expensive. skip it
}
depth--;
if(stack[depth-1]+1
void listLejeu()
{
int indice[k+1];
int i=0;
for ( i = 0; i =0; i--)
if (indice[i]
void listLejeuBase()
{
int indice[k+1];
int i, max,nb, reste,chiffre,pos,base,ok;
base = n-k+1;
// calcule de base ^k
for (max=1, i=0;i0 ; pos++,reste = reste /base )
{
chiffre = reste %base;
if (pos>0 && (chiffre > indice[k-pos]))
{
ok =false;
break;
}
else
indice[k-1-pos]=chiffre;
}
if ( ok)
{
//impression de la solution. skipped
}
}
}
template
void runTests(){
std::cout"();
t.toc("end listFatal");
t.tic();
listLejeu();
t.toc("end listLejeu");
t.tic();
listLejeuBase();
t.toc("end listLejeuBase");
}
struct Size{
enum { n = 30 };
};
int main(int argc, char** argv){
runTests();
runTests();
runTests();
runTests();
runTests();
runTests();
runTests();
return 0;
}
- Code: Tout sélectionner
Resultats:
running
end listFatal : 5.4e-05
end listLejeu : 2e-06
end listLejeuBase : 1e-06
running
end listFatal : 0.001011
end listLejeu : 0.001347
end listLejeuBase : 0.398276
running
end listFatal : 0.328998
end listLejeu : 0.319482
end listLejeuBase : 2e-06
running
end listFatal : 2.83512
end listLejeu : 2.40135
end listLejeuBase : 1e-06
running
end listFatal : 0.83854
end listLejeu : 0.736533
end listLejeuBase : 98.9158
running
end listFatal : 0.007209
end listLejeu : 0.008876
end listLejeuBase : 121.723
running
end listFatal : 2e-06
#ben alors, listLejeu loop infinie ? :D
La tendance, c'est ton premier algo plus rapide, j'ai aussi runné qq echantillons à n=40, ou mon algo est plus rapide, mais grossomodo, le tiens est fréquemment plus rapide.
Base à fait deux coups d'éclat à et qui sont un peu suspect ^^ (mais peut-être corrects!)
