std::find_if performance en question
Salut tt le monde,
Je viens juste de faire un test de performance sur l'algo find_if et je remarque qu'en fait, contre toute attente, même sur un grand nombre d'éléments cet algo prends peu près le même temps qu'un grotesque for...
Avez vous des suggestions pour m'expliquer pourquoi et si ya moyen de faire autrement pour aller plus vite ??Merci. Cf code ci-dessous:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <iostream>
#include <set>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
struct edge
{
int a;
int b;
bool operator < (const edge & rhs) const
{
if (a < rhs.a) return true;
if (a > rhs.a) return false;
if (b < rhs.b) return true;
if (b > rhs.b) return false;
}
};
struct find_myedge : std::unary_function<edge, bool>
{
edge myedge;
find_myedge(edge aedge):myedge(aedge){}
bool operator()(edge const& m) const
{
return (m.a == myedge.a) and (m.b == myedge.b) ;
}
};
double diffclock(clock_t clock1,clock_t clock2)
{
double diffticks=clock1-clock2;
double diff=(diffticks*1000)/CLOCKS_PER_SEC;
return diff;
}
int main()
{
const int N = 500000;
clock_t begin1=clock();
edge e;
std::vector<edge> v;
e.a = 3456;
e.b = 10;
v.push_back (e);
for (int i=0; i<N; ++i)
{
e.a = rand() + rand();
e.b = rand() + rand();
v.push_back(e);
}
e.a = 9000;
e.b = 110;
v.push_back (e);
cout << "number of elements = " << v.size() << "\n";
clock_t end1=clock();
cout << "Time elapsed: " << double(diffclock(end1,begin1)) << "ms"<< endl;
edge s;
s.a = 9000;
s.b = 110;
clock_t begin=clock();
bool test = true;
if (test){
std::vector<edge>::iterator it = std::find_if( v.begin(), v.end(), find_myedge(s) );
if (it!=v.end())
cout<<"found"<<endl;
}
else {
std::vector<edge>::iterator it;
for (it=v.begin(); it!=v.end(); ++it){
if ( (it!= v.end()) && (it->a == s.a) & (it->b == s.b)) {
cout<<"found"<<endl;
break;
}
}
}//if 0
clock_t end=clock();
cout << "Time elapsed: " << double(diffclock(end,begin)) << "ms"<< endl;
return 0;
} |
