accélérer les algorithm

Version imprimable

Voir 40 message(s) de cette discussion en une page

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

Voir 40 message(s) de cette discussion en une page