std::vector et performance

Version imprimable

04/08/2010, 16h14
fleurdelys77

std::vector et performance

Bonjour tout le monde,

Je suis entrain d'écrire un programme en c++ qui manipule un grand nombre de donnée, j'utilise std::vector pour insérer et supprimer les donnée dynamiquement , mais malheureusement le temps d'exécution et trop lent.

Est ce que quelqu'un connais une autre méthode autre que les stl pour améliorer le temps d'exécution ?

Merci d'avance
04/08/2010, 17h05
JolyLoic

Quel est ton motif d'ajout ? Au début ? A la fin ? N'importe où ? Par bloc ou un par 1 ? Tu connais le nombre total à ajouter avant ? Quel est l'ordre de grandeur de ce nombre ?..
04/08/2010, 17h24
fleurdelys77

Quel est ton motif d'ajout ? Au début ? A la fin ? N'importe où ? Par bloc ou un par 1 ? Tu connais le nombre total à ajouter avant ? Quel est l'ordre de grandeur de ce nombre ?..

D'abord merci pour la réponse,
Pour l'ajout c'est n'importe où, il se fait un par un et je ne connais pas le nombre total à ajouter.
Pour ce qui est la grandeur de se nombre, 1360800000 à peut prés.

est ce que les std::list ira mieux ?

Merci
04/08/2010, 18h00
Arzar

Bonjour,

Citation:

Envoyé par fleurdelys77

Pour ce qui est la grandeur de se nombre, 1360800000 à peut prés.i

1360800000 éléments !! Tu es sûr qu'il n'y pas quelques zéros en trop ? :mrgreen:
Car si l'on suppose que tu insères des int, donc 4 octet par éléments, ça nous fait 5.09 Go au total ! Quel que soit le conteneur utilisé tu vas mettre un pc à genou en tentant de tout charger en RAM...
04/08/2010, 19h43
fleurdelys77

pour l'insertion des données il me prend 2mn 38 s (sava :mrgreen: )
mon problème se pose au niveau de la suppression ( la suppression se fait au fur et à mesure dans des endroits du tableau que je ne connais pas au préalable.

est il possible de résoudre se problème ? 8O
04/08/2010, 22h37
epsilon68

t'as pensé à utiliser une database?
sqlite? (en memoire ou sur disque dependant du nombre d'element et de la rapidité)
tu t'evites beaucoup de probleme (de recherche, de suppression et d'ajout...)

en tous les cas, le vecteur n'est pas adapté pour de la suppression autre que celui de fin. et la list n'est pas vraiment adaptée pour de l'acces rapide...

peut-etre continuer avec un vecteur mais traiter les "remove" par des index qui deviennent libres (à stoker dans une list FIFO?)
-> erase est beaucoup mieux, echanger avec celui de fin puis effacer celui de fin ... hyper rapide...
04/08/2010, 22h39
JolyLoic

Pour ce qui est de faire des suppressions au milieu, un std::list sera effectivement bien plus rapide qu'un vecteur. Le problème, c'est qu'il y a pour std::list un surcoût mémoire par élément (2 pointeurs, en gros), ce qui vu le volume de données manipulé pourrait poser des problèmes.

Maintenant, si ton problème est la suppression, ne pourrais-tu pas la faire de manière plus efficace ? Par exemple, pour enlever plein d'éléments d'un coup, même non contigus, plutôt que des les enlever un par un, il est bien plus efficace de passer par du erase/remove.

En fait j'ai une matrice de 64800*100 pour chaque élément cells[k][i] de la matrice un tableau lui est associé et à chaque appel de la fonction "Loader::ajour" je cherche dans tout les tableaux si "numFace" (un entier) existe alors je l'écrase.
Donc je ne crois pas que je pourrai utiliser erase/remove
Voici la fonction où mon problème ce génère :

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
 
 
void Loader::ajour(int numface)
{
	for(int i=0; i < 68400; i++){
		for(int k = 0; k < 100; k++){
			if(cells[k][i].active == false) continue;
 
				//Contribution
				int j = 0;
				while(j < cells[k][i].listContribution.size())
				{
					if(cells[k][i].listContribution[j].numFace == numface)
					{
						cells[k][i].densite -= cells[k][i].listContribution[j].area;
						cells[k][i].listContribution.erase(cells[k][i].listContribution.begin()+j); 
					}
					else{ j ++; }	
				}
 
				//Penalité
				j = 0;
				while(j < cells[k][i].listPenalite.size())
				{
					if(cells[k][i].listPenalite[j].numFace == numface)
					{
						cells[k][i].densite += pFactor*cells[k][i].listPenalite[j].area;
						cells[k][i].listPenalite.erase(cells[k][i].listPenalite.begin()+j); 
					}
					else { j ++; }
				}
 
			// désactivation de la cellule
			if(cells[k][i].listContribution.size() == 0) cells[k][i].active = false;
 
		}
	}
}

05/08/2010, 16h21
Invité

Bonjour,
J'ai eu ce type de problème. Un grand nombre de données, la difficulté ne venait pas de la suppression, mais de trouver l'élément cherché, d'où un grand nombre de tests.
J'ai fait une organisation de liste chainée avec le technique de hachage. C'est d'une efficacité remarquable. Dans le cas de suppression les listes chainées semblent la technique la plus efficace.
05/08/2010, 16h53
Jean-Marc.Bourguet
Citation:
Envoyé par fleurdelys77

En fait j'ai une matrice de 64800*100 pour chaque élément cells[k][i] de la matrice un tableau lui est associé et à chaque appel de la fonction "Loader::ajour" je cherche dans tout les tableaux si "numFace" (un entier) existe alors je l'écrase.
Donc je ne crois pas que je pourrai utiliser erase/remove
Voici la fonction où mon problème ce génère :

Code:

1 2 3 4 5 6 7 void Loader::ajour(int numface) { for(int i=0; i < 68400; i++){ for(int k = 0; k < 100; k++){ if(cells[k][i].active == false) continue;
On n'est pas en FORTRAN, l'index qui bouge le plus vite doit etre le dernier. Inverse donc les deux boucles.

C'est quoi la definition des types?

Il y a combien d'elements dans les listXXX?

Est-ce que l'ordre dans les listXXX est important?

Il y a combien de cellules actives par appel a ajour()?
05/08/2010, 16h54
JolyLoic

Une idée pourrait être dans ta boucle de ne pas supprimer directement les valeurs à supprimer, mais de les index correspondant dans une conteneur d'éléments "à effacer". Puis dans un second temps, d'utiliser l'idiome erase/remove pour les enlever tous d'un coup. Ça peut selon les situations améliorer les choses (par exemple, si le nombre d'éléments à supprimer est faible devant le nombre total d'éléments, mais quand même relativement grand). Ou pas.
05/08/2010, 16h54
fleurdelys77

@ Pierre Dolez : justement j'ai déjà essai, après des recherches sur google j'ai trouvé que la fonction de hachage dans C++ c'est std::map mais malheureusement le résultat de l'exécution était encore plus long.

Est ce que vous pouvez me donner plus de précision, peut être j'ai mal implémenté mon programme ?

Merci encore tout le monde pour vos réponses
05/08/2010, 17h17
zul

std::map n'est pas une table de hashage. std::map est un arbre binaire pseudo-équilibré. Insertion / suppression / recherche se font en O(ln n).
std::tr1::unordered_map ou boost::unordered_map sont des tables de hash (avec la problématique d'avoir une bonne fonction de hash pour avoir des insertions / suppression / recherche en O(1) amorti).

Voila un bout de code dont le bit est de rechercher le point la plus proche d'un point donné.
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 // déclaration typedef struct PAQUET_MAT { long Xmin,Ymin,Xmax,Ymax; TMatricule *mat[100]; // un tableau de pointeurs TMatricule *blocmat; bool Pack(); PAQUET_MAT(); ~PAQUET_MAT(); }TabPaquetMat; typedef TabPaquetMat* ptrPaquetMat; struct TabRADIC //table des radicaux { char Rad[7]; AnsiString NomPlan; UINT premier, dernier, nombre; UINT Nombre(); // doit être appelé en cas de besoin si modif // renvoie le nombre de composants tq exist=true; // mais nombre est TOUJOURS le nombre réel de matricules TList *TabMatric; TabRADIC *suiv; // Le radical suivant TabRADIC(); }; for (TabRADIC *tr=tr_prem; tr; tr=tr->suiv) { // on cherche un point proche de x, y if (tr->TabMatric) { for (int ir=0; ir<tr->TabMatric->Count; ir++) // ir est un compteur { ptrPaquetMat pm= (ptrPaquetMat)tr->TabMatric->Items[ir]; if (!pm) continue; if (x > pm->Xmin-TolX && x < pm->Xmax+TolX && y > pm->Ymin-TolY && y < pm->Ymax+TolY) { for (int ic=0; ic < 100; ic++) { TMatricule *Mat=pm->mat[ic]; if (Mat && Mat->TestType(PH)) { if ((pt=(Point3D*)Mat->Objet()) != NULL ) { if ( labs(pt->ValX()-x) < TolX && labs(pt->ValY()-y) < TolY ) return pt; } } } } } } }
Voila le principe de recherche.
J'ai fixé la dimension de mes paquets à 100, mais c'est un choix.
Un composant est caractérisé par son matricule et son indice.
La liste chainée est TabRADIC. Son premier élément est tr_prem.
J'utilise une classe TList. C'est une liste de pointeurs de la bibliothèque de Borland. Ce n'est pas très pénalisant, parce que le nombre de radicaux est relativement limité.
Ce système est parfaitement au point.
Seul inconvénient, la phase test est au milieu (naturellement). C'est à dire que chaque fois que je dois faire un test, toute cette séquence doit être recopiée pour modifier seulement 2 lignes. J'ai essayé (et réussi) à utiliser un pointeur sur fonction, mais pour des raisons de simplification, cette technique n'est utilisée que dans un seul module, et encore, pas partout.
Pas de problème pour vous donner tous les détails voulus.
Pour mémoire, lorsque j'ai fait cette fonction, je n'avais pas encore de réel problème de temps d'exécution, mais cela me paraissait logique. Puis j'ai eu à traiter des données de taille considérable, et cette méthode a prouvé son efficacité, mais j'ai tout de même mis 2 jours à l'écrire et la tester :oops:

PS Il y a 2 classes Borland Builder
AnsiString qui peut être remplacée par std::string
TList qui peut (peut-être) être remplacée par std::vector
Mais, désolé, je ne connais pas le C++ dit standard
Les classes TMatricule Point3D sont perso et complètement hors-sujet

05/08/2010, 22h29
epsilon68

en sqlite et SQL, c'est devrait etre assez simple :-)
il y a longtemps, un prof m'avait dit d'integrer du SQL dans mes soft 3D,
et depuis j'y pense sans arret (je ne fais plus de 3D), par contre je pense qu'il avait raison et que à refaire, je pourrais simplifier tellement d'algorithmes avec du SQL et quelques tables...
06/08/2010, 10h56
Invité

Bonjour,
Oui, j'y avais déjà pensé aussi. Mais, ce n'est réalisable en terme de performance que si on adresse les paquets, et non les éléments individuellement. Autrement dit, le SQL résout plus un problème de volume de données que de performance.
06/08/2010, 20h09
fleurdelys77

Merci les amies pour vos réponse ça me fait chaud au coeur.
Si je résous le problème je poste la solution :ccool:
07/08/2010, 10h17
epsilon68

Citation:

Envoyé par Pierre Dolez

Bonjour,
Oui, j'y avais déjà pensé aussi. Mais, ce n'est réalisable en terme de performance que si on adresse les paquets, et non les éléments individuellement. Autrement dit, le SQL résout plus un problème de volume de données que de performance.

justement, depuis que je connais sqlite, je me dis que la performance ne serait pas tant que ca degradé, surtout qu'apres on peut gerer des models plus gros que la memoire disponible... (volume de donnée tu as raison)

apres la simplicité, on pourrait vraiment simplifier les algos et rendre le code plus claire (normalement :aie:)

la performance, je ne sais pas. Je pense que ca sera plus rapide dans tous les algo avec une recherche de valeur avec moins de maintenance.
maintenant ce qui me gene, c'est par exemple des tests de collision avec un ensemble de triangles: je pensais à utiliser des User Defined Functions.
mais du coup, ne nous coupons pas du multi-thread?

raaaa je ne sais pas