Discussion :

[lezurp]

Bonjour,

J ai un petit soucis pour organise mes donne ou plustot des doute sur ce qui est le plus utimale. Je voudrais votre avis sur mes choix.
Tout d'abord bravo et Merci si vous liser mon post jusqu au bout .

j ai une grande quantite de donne que je dois manipuler .

Pour simplifier mes donnees viennent d'environ 30 capteurs.
j ai aux moins: YYYY, MM, JJ, HH, mm, second, info1, et info2,

pour econnomiser un peu de place en memoire, je mettrais
YYYYMMJJHH dans un Uint,
mm Ushort
second Ushort
info1 et 2 dans un float ( pas trop le choix) les valeur allant de 0 a 2000 et sont toujours 6 chiffres ex:1500,89 ou 1,45879

Je voudrais idealement qu elle prennent le moins de place possible en memoire tout en me deplacent a l interieur de celle ci le plus rapidement possible.

1) la premier chose qui m est venu a l espris c ets de prendre toutes les donen de chaque acquisition et de les mettres telquel dans une std::list et au moment de la creation ( insertion) je mettrais dans std::set un iterateur (ou un pointeur) sur le premeir element de chaque jour.

ce qui m interesse principalement c ets de pouvoir passe d'un element n a n+1 le plus vite possible ( de n a n-1) peu etre plus lent.

Le probleme c ets que j ai vraiemnt becoup de donne environ 30000000 ( 30millions oui) par capteur , soit a la louche 1g0 de donen par capteur. C est gerable en une seul fois car le pc avec lequel je bosse a 12go ( vive le 64 bytes) , je trouve quand emem ca un peu limite.

2) je me suis dit que je vais econnomise sur les info redondante.

ja i donc decouper ca ainsi

Class A contient une map de <YYYYMMJJ(int),ObjetdeB>
Class B contient une map de <HHmm(Ushort),ObjetdeC>
Class C contient une list de Objet de D
Class D contient , 2 float(inof 1 et2) et un short( second)

a la Louche j estime que cette structre me ferai gagne environ 30% de espace memoire.
Mais la j ai plusieur question :

A)et ce que passer d une aquisition a une autre ne va pas me demander beaucoup plus de temp a final ?

B) etant une peu perferctioniste je voudrai evite de construire dans ma class qui remplie A ( et toutes les autre par la meme ocasion) un objetBtemporaire qui serai rempli par un objet C temporaire

je voudrai eviter ce genre de chose dans la class qui remplirai:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
	Map2 m;
	m.insert (make_pair (1.2, Map1 ()));
	m[1.2].insert (make_pair (3, "three"));
	m[1.2].insert (make_pair (5, "five"));
 
	m.insert (make_pair (.5, Map1 ()));
	m[.5].insert (make_pair (5, "five"));
	m[.5].insert (make_pair (1, "one"));
	m[.5].insert (make_pair (9, "nine"));

je voudrais appeler une focntion de A style
add(YYYY, MM, JJ, HH, mm, second, info1, et info2)
qui appelerai B avec
add( HH, mm, second, info1, et info2)
qui applerrai C avec
add ( second, info1, et info2)
qui applerrai D avec
add ( second, info1, et info2)

LE comble du comble serai que je mettre touts les capteur dans une listla ca ferai vraiment usine a gaz , mais je ne voie pa trop d'alternative

Merci de vos commentaires.

[bretus]

Bonjour,

Pourquoi tu t'obstines à charger tout ça en RAM?

[JolyLoic]

Les list introduisent un overhead de 2 pointeurs par objet. De plus, elles se parcourent pas de manière optimale, puisque leurs données sont réparties un peu partout en mémoire, ce qui fait que la mémoire cache n'est pas utilisé à son optimum.
Remplacer ces lists par un vector devrait te faire gagner.

Par contre, telle que tu la décris, ta structure me semble quand même assez lourde à utiliser. De plus, à cause d'histoires d'alignement (padding), ton objet D n'est pas optimal, il va prendre en mémoire plus de place que ce qu'il utilise vraiment. Du coup, il serait intéressant :
- Soit que D ne contienne que les deux floats (mais je ne sais pas si c'est compatible avec tes données)
- Soit que D contienne un peu plus
- Soit que tu utilises des spécificités de ton compilateur pour stocker tes D sans padding (mais risque de baisse de perfs)

Donc, en prenant le seconde option, je dirais qu'à ta place, je tenterais une map par année, mois, jour qui contient des données contenant heure, minute, seconde, f1, f2 dans un vector.

Pourquoi garder la map de premier niveau, alors que des données contenant directement toute l'information de date ne prendraient probablement pas plus de place ? Tout simplement parce que comme on stocke dans un vector, qui utilise de la mémoire contiguë (ce qui est une bonne chose), tout allouer d'un bloc demanderait un bloc contiguë énorme (ce qui en est une mauvaise). D'où l'idée de le fragmenter un peu...

[lezurp]

Bonjour,

1) je charge tout en ram car j utilise ces donnees (la totalite a chaque fois) pour effectuer de grandes quantitées de simulation numerique avec de tres tres nombreuse iterations. C est vraiment pas pour le plaisir . D ou l interet pour moi de passer d'un element a un autre rapidement.

2)

Concernant le padding ca m avait vagement traverse l esprit ( car j ai du voir un truc sur le net a ce sujet) mais je n imaginait pas que ca pouvait faire une si grande differance. Donc sachant que j utiliserai uniquement un os 64bit (actuelement Win7 64 , avec le compilateur de windows), quel sont les tailles a idealement respecté des multiple de 4,8,16,32 ou 64. Je dirai que tout multiple de 64 vue l os, mais tu semble dire que 2 float c est ok aussi (2*4). J ai effectivement la possibilite de mettre d autres info. voir meme de combler avec un peu de rien si vraiment les perf sont tres differante. je vais essaye.

Et juste pour que je me couche moins bete sur linux (toujours 64bits mais avec gcc) et ce que cela change quelque chose, pour le padding?

Donc tout les element d un vecteur sont contigue, mais si c est un vecteur d objet contenent des int des float et tout le bazard, l insert du vecteur va s arranger pour que tout les element de l objet du vecteur sont contigue aussi ?


Je n avais aucune idee de l existance des overhead de la list. Et j etait persuadé que la memoire utilise etait contigue. comme quoi j etait dans les choux... En general pour choisir mes conteneur de la std j utilise juste le tableaux : http://www.cplusplus.com/reference/stl/

Puis selon ce que je veux faire , et selon les fonction disponible pour chaque je selection le conteneur.

Par example, je vais avoir plus tard besoin d un conteneur ou je devrai etre capable d ajouter et elever des element au debut et a la fin du conteneur etre souvent, avec ca j ai le choix entre une list et un deque, ne sachant pas exactement les implication de chaqun je me dit que toutes la focntion que j ai besoin sont present dans la list et que le deque en contient plus, il doit etre soit plus lent soit plus lourd ou les deux, donc je choisie la list. Cela em semble logique mais pas necessairement juset car je ne connai pas les implication de chaque conteneur.

Connais tu un site, tableau ou autre chose qui me permettrai de choisir plus efficacement les conteneurs je suis preneur,

Merci pour les info et conseils

[JolyLoic]

Je ne suis pas du tout un pro du padding, aussi je t'invite à faire des tests. De ce que j'ai lu là :
http://msdn.microsoft.com/en-us/libr...=vs.71%29.aspx

Ta structure aura l'alignement de sa donnée la plus grande. C'est à dire 4 bytes. Donc si tu mets dedans un autre type plus petit, genre un short, ta structure fera toujours un multiple de 4 bytes, et tu en auras gaspillé 2.

Les règles de padding peuvent changer d'un compilateur à l'autre, comme les tailles des différents types de base. Mais commes ces règles sont là pour faire plaisir au processeur, il y a des changes que le comportement par défaut soit le même...

Je ne suis pas certain d'avoir compris la seconde question. Si tu as un vecteur d'objets constitués de 2 floats et un short, en mémoire, ça va ressembler à (1 "case" == 1 byte; 00 représente le padding):

Code :

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

f1 f1 f1 f1 f2 f2 f2 f2 s1 s1 00 00 f1 f1 f1 f1 f2 f2 f2 f2 s1 s1 00 00 f1 f1 f1 f1 f2 f2 f2 f2 s1 s1 00 00

Si tu fais insert au milieu d'un vector, il va commencer par recopier en décalant d'un cran toutes les données situées après le point d'insertion. Ce qui fait qu'insert sur un vector n'est pas très efficace (O(n)) (mais push_back l'est).

Une list par contre est implémentée à l'aide d'une liste doublement chaînée. Pas de contiguïté en mémoire, mais l'insertion peut se faire sans rien déplacer, juste en jouant avec des pointeurs.

Le tableau de choix que tu proposes n'est pas trop mal, mais il possède deux graves défauts :
- Il ne précise pas la complexité pour certaines opérations dont la complexité peut varier d'un conteneur à l'autre, or c'est justement cette variation qui est souvent l'élément essentiel de choix.
- Il ne parle que de complexité algorithmique, or en cas d'égalité, il y a d'autres critères qui peuvent entrer en compte.

Il y a pour choisir le schéma dans la faq : http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur

Ou le conseil donné pas Alex Stepanov (l'inventeur de la STL), et repris par Bjarne Stroustrup en entête du chapitre sur la STL de son dernier livre, Programmation Principes et pratique avec C++ : "Use vector as the default"

[Epsilon012]

30M données dans une map (la plus part des op en O(lg(n))), la vitesse d’exécution va s'en prendre un coup, en plus si tu connais à l'avance le nombre de donnée, tu peux utiliser des hash tables (std::unordered_map en C++0x).

Ton exemple :

Code :

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

1
2
3
4
5
6
7
8
Map2 m;
m.insert (make_pair (1.2, Map1 ()));
m[1.2].insert (make_pair (3, "three"));
m[1.2].insert (make_pair (5, "five")); 
m.insert (make_pair (.5, Map1 ()));
m[.5].insert (make_pair (5, "five"));
m[.5].insert (make_pair (1, "one"));
m[.5].insert (make_pair (9, "nine"));

Moi je l'écris comme ça :

Code :

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

1
2
3
4
5
6
Map2 m;
m[1.2][3]="three";
m[1.2][5]="five";
m[.5][5]="five";
m[.5][1]="one";
m[.5][9]="nine";

L'idée de mettre plusieurs maps imbriqués pour ne pas avoir de redondance est valable mais là encore, c'est à équilibrer avec le temps d’exécution, chercher 42, puis dans la table de hachage correspondante chercher 12, ça te prend deux fois plus de temps que de chercher (42,12) dans une seule table. (mais ça prend plus de place). Dans le cas d'une map (arborescence je veux dire), ce sera moins visible c'est sur…

[lezurp]

Merci !