Discussion :

[yan]

Il devrait etre possible de specialiser la fonction

Code :

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

1
2
void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)

pour appeler le swap avec mingw

[reptils]

mouais ça devrait etre le plus simple

[yan]

Code :

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

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!!!

[yan]

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 :

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
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 :

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 :

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]

[yan]

en remplacant le sort par :

Code :

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

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

avec swap :

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

10 : 28.1
110 : 924.8
210 : 1906.5
310 : 2904.4
410 : 3960.9

[yan]

en remplacant sort par

Code :

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

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

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

sans swap

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

[loufoque]

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

[yan]

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

pourquoi?

[JolyLoic]

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

[yan]

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

[yan]

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 ...

[JolyLoic]

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

[yan]

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

[screetch]

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

[yan]

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.

[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.

[yan]

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