accélérer les algorithm

Version imprimable

Bonjour,
constatant que les algo utilise souvent la fonction swap. J'ai essayer de jouer avec pour optimiser un sort.
Voici le code :

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
class A 
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
	bool operator<(const A& a) {return nb<a.nb;}
	A&  operator=(const A& a) 
		{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb<a.nb;
		myString=a.myString;
		return (*this);
		}
	void swap(A& a) 
		{
			static int nbswap(0);
			std::cout<<"swap : "<<++nbswap<<std::endl;
			std::swap(nb,a.nb);
			myString.swap(a.myString);
		};
private:
	std::string myString;
	int nb;
 
};
//specialisation de la fonction swap pour la class A
template<>
inline void std::swap<A> ( A& a, A& b )
{
	a.swap(b);
};
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
return 0;
}

En prenant l'hypothèse qu'un égale dure 1 second (du au reallocation et recopie de memoire), et swap .5s (echange de la mémoire, donc peut de recopie)

Les résultats que j'obtiens sous visual 20005 sont :
- sans le swap : 234 operation egale = 234s
- avec le swap : 74 operation swap et 72 operation egale = 109 s

Ce qui n'est pas négligable.
Maintenant je me demandé si :
1- ce que j'ai fait est tout à fait correcte
2- il n'y as pas d'autre manière de faire
3- on est obligé de spécifier std::swap

[EDIT]
4- existe t'il d'autre astuce comme celle la???
merci

voici une rversion qui marche avec GCC

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
	bool operator<(const A& a)const {return nb<a.nb;}
	A&  operator=(const A& a)
		{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
		}
	void swap(A& a)
		{
			static int nbswap(0);
			std::cout<<"swap : "<<++nbswap<<std::endl;
			std::swap(nb,a.nb);
			myString.swap(a.myString);
		};
private:
	std::string myString;
	int nb;
 
};
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
	return 0;
}

Les résultats que j'obtiens avec GCC sous ubuntu sont :
- sans le swap : 361 operation egale = 361s
- avec le swap : 88 operation swap et 185 operation egale = 229 s

26/11/2007, 18h58
yan

Au faite, pour ceux qui veule tester,pour enlever le swap, il suffit de commenter la definition de std::swap
27/11/2007, 22h51
yan

personne n'as d'idée???
27/11/2007, 23h08
yan

Bon,
j'ai trouvé un truc pour ceux que cela intéresse :
http://www.tantalon.com/pete/cppopt/...l.htm#Swapping
08/03/2008, 11h08
r0d

Il serait intéressant de faire des tests sur des gros conteneurs bien remplis. Et chronométrer, avec différentes méthodes, sur différentes plateformes, et avec une machine dédiée (je veux dire un machine où aucune appli ne tourne, pas même les démons/services réseau etc.)
08/03/2008, 11h34
yan

Citation:

Envoyé par r0d

Il serait intéressant de faire des tests sur des gros conteneurs bien remplis. Et chronométrer, avec différentes méthodes, sur différentes plateformes, et avec une machine dédiée (je veux dire un machine où aucune appli ne tourne, pas même les démons/services réseau etc.)

Why not ;)
Le petit bout de code que j'ai fournie est pour cela aussi

pas mal le post.... seulement j'ai essayer de lancer ton code (avec le swap décommenté) et c'est l'opérateur d'affectation qui est appelé :? comment forcer l'appel de swap?

Edit: j'ai essayé de changer le code pour afficher à l'écran le contenu du vector<A> utilisant l'algo copy, avec un ostream_iterator de maniere sioux, mais ça marche pas la compilation... des idées?

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
 
 
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	A&  operator=(const A& a)
	{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
	}
 
	void swap(A& a)
	{
		static int nbswap(0);
		std::cout<<"swap : "<<++nbswap<<std::endl;
		std::swap(nb,a.nb);
		myString.swap(a.myString);
	}
 
	friend std::ostream& operator <<(std::ostream& lhs, A& rhs)
	{
		rhs.Print(lhs);
 
		return  lhs;
	}	
 
	void Print(std::ostream& os)
	{
		os<< "id= " << nb <<" chaine= " << myString;	
	}
 
 
private:
	std::string myString;
	int nb;
 
};
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
 
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
 
	std::copy(vect.begin(),vect.end(),std::ostream_iterator<A>(std::cout," "));
 
	return 0;
}

09/03/2008, 08h42
yan

Citation:

Envoyé par reptils

pas mal le post.... seulement j'ai essayer de lancer ton code (avec le swap décommenté) et c'est l'opérateur d'affectation qui est appelé :? comment forcer l'appel de swap?

Tu compile avec quoi? C'est possible que ca ne marche pas avec toute les implementation. Ca marche avec visual et gcc normalement

Citation:

Edit: j'ai essayé de changer le code pour afficher à l'écran le contenu du vector<A> utilisant l'algo copy, avec un ostream_iterator de maniere sioux, mais ça marche pas la compilation... des idées?

Je regarderai tout à l'heure

Code:

1 2 3 4 5 6 std::ostream& operator <<(std::ostream& lhs, A& rhs) { rhs.Print(lhs); return lhs; }
faut la mettre hors de la declaration de la class. Il faut peut etre un const A

09/03/2008, 11h04
reptils
Citation:

Envoyé par Mongaulois

Tu compile avec quoi? C'est possible que ca ne marche pas avec toute les implementation. Ca marche avec visual et gcc normalement

pour faire vite j'ai utilisé le gcc de cygwin (3.4.4)
Citation:
Envoyé par Mongaulois

Code:

1 2 3 4 5 6 std::ostream& operator <<(std::ostream& lhs, A& rhs) { rhs.Print(lhs); return lhs; }

faut la mettre hors de la declaration de la class. Il faut peut etre un const A
oui tu as raison, ça marche maintenant, il faut aussi que je "constifie" la A et la méthode Print

avec l'affichage du contenue :

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
 
 
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	A&  operator=(const A& a)
	{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
	}
 
	void swap(A& a)
	{
		static int nbswap(0);
		std::cout<<"swap : "<<++nbswap<<std::endl;
		std::swap(nb,a.nb);
		myString.swap(a.myString);
	}
 
	friend std::ostream& operator <<(std::ostream& lhs, const A& rhs);
	void Print(std::ostream& os) const
	{
		os<< "id= " << nb <<" chaine= " << myString<<std::endl;	
	}
 
 
private:
	std::string myString;
	int nb;
 
};
std::ostream& operator <<(std::ostream& lhs,const  A& rhs)
	{
		rhs.Print(lhs);
 
		return  lhs;
	}	
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
 
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
 
	std::copy(vect.begin(),vect.end(),std::ostream_iterator<A>(std::cout," "));
 
	return 0;
}

09/03/2008, 11h19
yan

Citation:

Envoyé par reptils

pour faire vite j'ai utilisé le gcc de cygwin (3.4.4)

Normalement ca fonctionne. En faite peut que tu n'as pas fait attention. IL ne fait pas que des swap. Il fait les deux
09/03/2008, 11h21
reptils

oui mais seul les messages d'opération d'affectation s'affichent, et j'en ai 361 comme par hasard
09/03/2008, 11h26
yan

Citation:

Envoyé par reptils

oui mais seul les messages d'opération d'affectation s'affichent, et j'en ai 361 comme par hasard

:cry: ok...
Peut tu mettre le code?
Histoire que j'essaie de mon coté avec le même code?

et hop!

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
 
 
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	A&  operator=(const A& a)
	{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
	}
 
	void swap(A& a)
	{
		static int nbswap(0);
		std::cout<<"swap : "<<++nbswap<<std::endl;
		std::swap(nb,a.nb);
		myString.swap(a.myString);
	}
 
	friend std::ostream& operator<<(std::ostream& lhs,const A& rhs);
 
 
	void Print(std::ostream& os) const
	{
		os<< "id= " << nb <<" chaine= " << myString;	
	}
 
 
private:
	std::string myString;
	int nb;
 
};
 
std::ostream& operator<<(std::ostream& lhs,const A& rhs)
{
	rhs.Print(lhs);
 
	return  lhs;
}
 
 
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
 
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
 
	std::copy(vect.begin(),vect.end(),std::ostream_iterator<A>(std::cout," \n"));
 
	return 0;
}

Commentes le std::copy si tu ne souhaite pas voir affiché le contenu du vector :)

09/03/2008, 11h47
yan

Peut tu réessayer en enlevant la toute première ligne

Code:

#include <cstdlib>
09/03/2008, 11h55
reptils

c'est pareil, en fait j'ai mis tout à l'heure parce que je voulais faire un system("pause")
09/03/2008, 12h02
yan

Citation:

Envoyé par reptils

c'est pareil, en fait j'ai mis tout à l'heure parce que je voulais faire un system("pause")

On ne sais jamais....
Je testerais tout à l'heure

:?
donc en faite, j'ai trouvé le problème

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
      typedef typename iterator_traits<_ForwardIterator1>::value_type
	_ValueType1;
      typedef typename iterator_traits<_ForwardIterator2>::value_type
	_ValueType2;
 
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator1>)
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator2>)
      __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
				  _ValueType2>)
      __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
				  _ValueType1>)
 
      const _ValueType1 __tmp = *__a;
      *__a = *__b;
      *__b = __tmp;
    }

cette fonction n'utilise pas le swap....
SI tu remplace ce morceau de code

Code:

1
2
3
 const _ValueType1 __tmp = *__a;
      *__a = *__b;
      *__b = __tmp;

par

Code:

swap( *__a ,*__b);

et que tu met la partie swap au dessus,
ca marche de la balle. Mais bon :roll:
ca ce trouve dans le fichier
include\c++\3.4.2\bits\stl_algobase.h

09/03/2008, 15h51
yan
Il devrait etre possible de specialiser la fonction
Code:

1 2 void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
pour appeler le swap avec mingw
09/03/2008, 16h14
reptils

mouais ça devrait etre le plus simple

Code:

1 2 3 4 5 6 7 8 namespace std { template<> inline void iter_swap<vector<A>::iterator,vector<A>::iterator> ( vector<A>::iterator a, vector<A>::iterator b ) { (*a).swap(*b); }; }
En faite c'est encore mieux que ce que je disait. Dans les compte, j'ai oublié le constructeur par recopie!!!

Citation:

Envoyé par r0d

Il serait intéressant de faire des tests sur des gros conteneurs bien remplis. Et chronométrer, avec différentes méthodes, sur différentes plateformes, et avec une machine dédiée (je veux dire un machine où aucune appli ne tourne, pas même les démons/services réseau etc.)

voila chef

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
100
101
102
103
104
105
106
107
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <ctime>
 
//afficher les log de copi, egale et swap
#define LOG 0
//utilisation du swap de la class A
#define USE_SWAP 1
//specification pour mingw
#define USE_MINGW 0
 
//class qui contient la fonction swap pour éviter des recopie de memoire
//trié par nb
//contient un vector de 10000
class A
{
public :
	A(int a) :nb(a),myVector(10000){ };
 
	A(const A& a)
	{
		*(this)=a;
	}
 
	A&  operator=(const A& a)
	{
 
		#if LOG
			static int nbegale(0);
			std::cout<<"= : "<<++nbegale<<std::endl;
		#endif
		nb = a.nb;
		myVector=a.myVector;
		return (*this);
	}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	void swap(A& a)
	{
		#if LOG
			static int nbswap(0);
			std::cout<<"swap : "<<++nbswap<<std::endl;
		#endif
		std::swap(nb,a.nb);
		myVector.swap(a.myVector);
	}		
 
	int					 nb;
	std::vector<double>  myVector;
 
 
};
//specialisation de la fonction swap pour la class A
#if USE_SWAP
	namespace std
	{
 
		template<>
		inline void swap<A> ( A& a, A& b )
		{
			a.swap(b);
		};
		//specialisation de iter_swap pour utiliser swap dans l'implementation de mingw 
		#if USE_MINGW
			template<class T>
			inline void iter_swap<> ( typename T::iterator a, typename T::iterator b )
			{
				(*a).swap(*b);
			};
		 #endif
	}
 #endif
int main(int argc, char** argv)
{
 
	//taille du vector de A à trier
	for(int nb_vect = 10;nb_vect <1000;nb_vect+=100)
	{
 
		double somme(0);
		clock_t t;
		//moyenne sur 10 sort 
		for(int a=0;a<10;++a)
		{
			//pour comparer les resultats on initialise la graine aléatoire 
			//pour garantir la même suite aléatoire à chaque execution
			srand(0);
 
			//vecteur à trier
			std::vector<A> vect(nb_vect);
			for(int i=0;i<nb_vect;++i)
			{
				vect[i].nb=rand();
			}
			//on fait le trie
			t=clock();
				std::sort(vect.begin(),vect.end());
			somme+=clock()-t;
		}
 
		std::cout<<nb_vect<<"  :  "<<somme/10<<std::endl;
	}		
	return 0;
}

résultat sans swap :

Citation:

10 : 0
110 : 25
210 : 50
310 : 78.1
410 : 129.6
510 : 164.1
610 : 217.3
710 : 223.3
810 : 274.7
910 : 325.3

résultat avec swap :

Citation:

10 : 0
110 : 15.5
210 : 28.2
310 : 45.3
410 : 57.7
510 : 70.4
610 : 98.5
710 : 101.4
810 : 123.4
910 : 148.6

[edit] petite modif sur l'init de vect pour qu'elle soit plus rapide[/edit]

12/05/2008, 10h29
yan
en remplacant le sort par :
Code:

1 2 for(int j=0;j<100;++j) std::random_shuffle(vect.begin(),vect.end());
avec swap :

Citation:

10 : 0
110 : 1.6
210 : 3
310 : 3.2
410 : 6.1
510 : 1.5
610 : 3.1
710 : 3.2
810 : 4.7
910 : 4.6

sans swap

Citation:

10 : 28.1
110 : 924.8
210 : 1906.5
310 : 2904.4
410 : 3960.9
12/05/2008, 11h01
yan
en remplacant sort par
Code:

1 2 A aa(RAND_MAX/4); std::partition( vect.begin(),vect.end(),std::bind2nd( std::less<A>(), aa) );
avec swap no mesurable avec clock

Citation:

10 : 0
110 : 0
210 : 0
310 : 0
410 : 0
510 : 0
610 : 0
710 : 0
810 : 1.6
910 : 0

sans swap

Citation:

10 : 0
110 : 4.5
210 : 3.2
310 : 9.4
410 : 8
510 : 9.4
610 : 13.9
710 : 10.9
810 : 15.5
910 : 15.6
13/05/2008, 11h47
loufoque

Le mieux ce sera quand les rvalue references seront dans le langage
13/05/2008, 11h48
yan

Citation:

Envoyé par loufoque

Le mieux ce sera quand les rvalue references seront dans le langage

pourquoi?
13/05/2008, 12h57
JolyLoic

Parce que ce genre de choses sera pris en compte automatiquement ?
13/05/2008, 13h57
yan

Citation:

Envoyé par JolyLoic

Parce que ce genre de choses sera pris en compte automatiquement ?

cool.
Par contre le temps que ça ce mette en place....
Tu aurais quelque doc dessus?
je vais chercher en attendant.
merci
13/05/2008, 14h08
yan

Citation:

Envoyé par JolyLoic

Parce que ce genre de choses sera pris en compte automatiquement ?

j'ai regardé un peu les rvalue, mais je ne voit pas en quoi avoir la possibilité d'avoir une references sur un temporaire permet une prise en compte automatique de ce genre de chose ...
13/05/2008, 14h58
JolyLoic

Voir ma réponse dans la discussion que tu as entamée dans le forum C++
13/05/2008, 15h25
yan

Citation:

Envoyé par JolyLoic

Voir ma réponse dans la discussion que tu as entamée dans le forum C++

Merci. Je continuerais cette discution sur l'autre thread.
http://www.developpez.net/forums/sho...d.php?t=547007
13/05/2008, 16h27
screetch

list est plus rapide que vector dans ce cas je pense.
13/05/2008, 16h30
yan

Citation:

Envoyé par screetch

list est plus rapide que vector dans ce cas je pense.

apparemment avec une list, il n'y as pas de changement de place des éléments. Juste un changement de valeur.
http://www.developpez.net/forums/sho...d.php?t=545564

Donc cela doit être kifkif.
13/05/2008, 16h41
screetch

std::sort ne marche pas sur une liste, il faut utiliser list.sort(). et list.sort() va sans doute reordonner les cases sans toucher au contenu.
13/05/2008, 16h45
yan

Citation:

Envoyé par screetch

std::sort ne marche pas sur une liste, il faut utiliser list.sort(). et list.sort() va sans doute reordonner les cases sans toucher au contenu.

ha oui je m'égare là. dsl