Discussion :

[startup1]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[Flob90]

La complexité de find est en O(n), celle d'un for aussi. Si le prédicat utilisé par ton for est le même que celui utilisé par find et que tu utilises un break quand tu as trouvé l'élément, il n'y a pas vraiment de raison que find soit plus rapide que ton for.

Les algo de la STL n'ont rien de magiques, ce ne sont que des implémentation assez classiques d'algo eux aussi classique. Si la théorie nous dit qu'on aura pas mieux que linéaire, alors la STL ne fera pas mieux que linéaire non plus (c'est le cas pour une recherche dans une séquence de données quelconque).

Il peut exister des différences de temps (*) entre un de tes algo et un de la STL, mais si c'est le même algo cette différence ne devrait pas être significative (ie la différence de temps est faible devant la durée moyenne de l'algorithme).

(*) Lié à la facon dont tu code l'algo, nombre d'indirection par exemple.

[DonQuiche]

Pour compléter, non seulement find_if n'a rien de magique mais il est même logique qu'il soit plus lent qu'une simple boucle for puisqu'il ajoute des appels de fonctions et autres. Ce n'est que grâce aux optimisations du compilateur que cet écart peut être réduit ou annulé.

S'il faut quelque chose de plus rapide, la solution est d'utiliser une structure de données adaptée à la recherche que l'on devra mener : tableau trié, dictionnaire, arbre binaire, etc.