Salut    
 
Je cherche à manipuler le plus rapidement possible des tableaux 1D et 2D de taille variable.
...et j'ai pensé à Boost    
D'après la doc, il semble que l'utilisation d'array ou multiarray ne concerne que des tableaux de tailles fixes    
Est-ce bien vrai, n'y a-t-il pas d'astuces pour gérer des tableaux de taille variable ?
 
merci pour vos précisions...

1D dynamqiue : std::vector
2D dynalmique : boost::multi_array
 
Y a que boost::array qui gére des tailles statiques.

 
Ah, je me disais bien que j'avais mal lu, merci Joel F    
Je vais donc revoir ce que j'avais commencé à faire avec multi_array...
Mais à première vue, ce qui semble peu pratique, c'est l'absence d'un push_back , car il faut directement attaquer les positions dans le tableau tab[n][n][...]. Et d'après ce que j'imagine, on doit évaluer le nombre d'éléments ds chaque dimension avant de trouver l'emplacement suivant !?
... et pas d' erase non plus, là par contre je vois pas comment effacer un élément  

c'est une matrice NxM[...] ça n'a pas de sens de changer la taille d'un élément. Si ton machin c'est plus un tas de spaghettis, alors tu ferais mieux de faire des list de list [...] de vector

Donc même si je voulais modifier la capacité de la 2d colonne du premier élément de ma matrice, cela s'appliquerait à toute les autres.  
Il faut donc fixer les limites dès le début,  même si on ne sait pas quelle sera la quantité de particules (2d col) contenu dans une mollécule(1ere col) ?
 

Ben je voudrais juste associer à chaque assiette (1er col), une quantité variable de spaghettis (2d col)  

Donc pas une matrice, ni un tableau (au sens taille fixe).

effectivement, le besoin suggère plutot un vector de list non ?
ou un array de list si la "1ere colonne" ne change jamais de taille.
apres, en fonction des besoins des accès aux listes (en terme de perfs par rapport aux operations qui seront faites le plus souvent), il faut choisir le bon conteneur.
par exemple, si tu ne sais pas la taille finale, tu ne feras que push_back dessus puis finir par parcourir le tout et désallouer tout a la fin.
boost::fast_pool sera un parfait allocateur pour les list.

Par list  veux-tu dire ptr_list de boost ?
 
En tout cas le principe du vector de liste semble le plus approprié.  
Pour avoir une idée, quelle serait la différence en terme de performance entre une matrice et un vector ou array de list ?
 
Car si c'est considérable, quitte à avoir de nombreuses cases vides,  peut être faudrait-il conserver la première solution  ?
 
Enfin, je ne me rends pas encore compte de ce que je pourrais gagner comme perf mais ces calculs ayant lieu en même temps que d'autres,  des collisions 3d géré par un moteur de physique par ex, il faudrait que je sois le plus léger possible    
 

Je ne l'ai pas encore testé mais en faisant quelques recherches je suis tombé sur cette remarque (http://www.nabble.com/-boost::pool [...] 29499.html) :
 
1. memory blocks allocated by boost::fast_pool tended to never get freed again until the end of the program, because the release mechanism was (is?) disabled
... In fact, when I tested it, fast_pool eventually ran out of memory at about the same time the the local member variable storing the memory increment size sufferd an overflow!
 
J'ai peut être pas compris, mais on dirait qu'on ne peut pas libérer de la mémoire avec cette méthode !?

Tu t'y prendrais comment alors ?

oula, en effet si il y a des leaks.... je ne sais pas je n'ai jamais testé cet allocateur.
j'utilise un conteneur freelist qui me convient
-> http://lightness1024.free.fr/xtrem [...] eelist.hpp
 
si tu veux utiliser des indices tres disparates pour ne jamais rien mettre dans les zones libres, il s'agit d'un contenu "sparse".
peut etre que ce que tu veux c'est ca ?
 

 
ceci créerait une "matrice" de 20 colonnes mais indexée par des valeurs potentiellement tres étalées sans gigantesque perte de mémoire (comme ce serait le cas avec un vector)
chacune des colonne contiendrait un nombre variable de valeur 'double', avec une operation 'push' rapide.
il serait rapide d'acceder en random a une colonne specifique, mais tu ne pourrais que itérer sur les lignes.

y a pas de leak, juste que la politique de dealloc est de desaoulée en fin de programme ce qui peut mener à arriver à la fin de la zone allouable dans un programme.

Comme le dit JoelF c'est un choix volontaire... j'aimerais bien comprendre l'intérêt    
Peut-on encore parler le tailles dynamiques si l'on ne peut libèrer de la mémoire durant l'execution d'un programme !?
 

 
Yep, je ne demande qu'à essayer ...  
 

Que veux-tu dire par gigantesque , c'est mesurable ?
 

Doit-on préciser quand une colonne est de taille fixe et l'autre non, ou ça ne change rien ?
 L'idéal étant pour moi une 1ere colonne fixe et l'autre non...
 

Là j'suis nouille sur le vocab mais 'les lignes', c'est à l'intérieur d'une colonne ou de la matrice ?
 
   
 

 
TU libère jamais pendant. Si t'as besoin de reallouer tu alloue un novueau bloc et laisse tomber l'ancien.
A la terminaison du programme, tout les blocs alloués (actifs ou inactifs sont libéré).
 
En gros, t'as une grosse alloc au debut du chargement du proigramme, allouer pendant coute rien, desallouer coute rien et t'as une seul grosse desalloc en fin de programme.
 
Donc la justification est assez simple à trouver

Lorsque tu parles de 'reallouer un novueau bloc' c'est en pensant recommencer quelque chose à partir de zéro, c-à-d supprimer forcément les données antérieures où l'on peut imaginer un transfert vers une matrice plus grande ?
J' avais pensé redéclarer une matrice plus grande à mesure que l'on ajoute des éléments  et la remplir ...mais ça paraissait absurde, étant donné que durant le transfert, 2 matrices était memoire soit 2*+ de données !?
Enfin, est-ce qu'on peut bidouiller de cette manière tout en restant performant où c'est n'importe quoi ?
 

Oui c'est clair, enfin je l'imagine comme une étape préliminaire importante au lancement d'une apli,  par ex un jeux video avec le chargement des media, textures, maillages, sons...tout un monde à mettre en place     mais pour un groupe d'objets particuliers, créer à la volé ça colle moins  

soyons clair sur ce que tu as envie de faire.
c'est bien un truc comme ca ou pas ?

Exactly !
... j'insistais juste pour savoir à quel point un tableau fixe serait plus performant mais dans l'idée ton schéma serait le mieux.
 
ps:merci pour le schèm, je vois où sont les lignes  

Avec Freelist je commence par :
 

 
Mais erreur C2676 à la ligne 14    
binary '[':'tools::freelist<T> does not define this operator or a conversion to a type acceptable to te predefined operator
 
Ca aussi ça ne marche pas:
 

 
ps: j'entends dire qu' std::size_t est un type avec lequel on mesure un array...mais ici comme on ne peut pas le redéfinir, est-ce qu'il sert de valeur indéfinie lors de la déclaration de notre tableau ?

Comme j'ai encore du mal avec la syntaxe de boost...je suis reparti du multi_array avant d'attaquer freelist :
 

 
 
J'épluche encore la doc de Boost mais pourriez vous m'aider à trouver la formulation pour nextPos ?
 
Et que pensez vous de la manière de supprimer() un élément ?
 
merci

pour quel conteneur push_back renvoit-il un bool ?
http://www.cppreference.com/wiki/stl/list/push_back
une liste ne peut pas s'acceder avec l'operateur [] c'est normal si molles[x][y] ne compile pas.
 
voici une solution avec contenu mémoire optimisé exactement par rapport au contenu et accès "efficace":
 

 
 
affichage:
 

Super Lightness1024    
 

ah, j'avais pas compris ça comme ça    
 
...par contre j'ai un peu de mal à saisir ta manière de modifier une Molle    
Jusqu'à présent je pensais la déduire du tableau (1ere col pour son ID, 2d col particle IDs),  
et là c'est carrément une Structure !
Bon, ok pour le principe mais ces 2 lignes m'intrigue :

...

Je ne vois pas où tu modifies le contenu d'une Molle ?
On dirait que ça se passe dans la sructure avec ++generate_ints produisant une valeure aléatoire ?
Comme je ne suis pas habitué à la syntaxe, j'ai l'impression que Molle() est appelé comme une fonction ?
 
Enfin, le test fonctionne, reste à formuler l'ajout/suppression des ID de mes particules ds la 2d col ...
 
merci bcp pour ton exemple    
 
ps: j'ai entendu dire que les arrays 2D d'STLSoft seraient plus rapide .?!

constructeur par défaut qui appelle ++ sur generate_int qui incremente l'entier.
 

 
creation d'un objet Molle temporaire apr appel du constructeur par defaut et copie dasn le tableau
 

Ca vaut quoi les sparse machin implémenté sur des hash ? Faut vraiment que ça soit ultra sparse, parce que niveau localité, c'est 0 ?

moi j'aime aps, les technqiues à base d'horizon m'ont trjrs paru  meilleurs.
Ca ou utilisé des algos  cache oblivious

Evidament, c'est pourtant ce que j'ai vu...mais  mal interprété les valeurs de x    

 
Ok, donc je peux faire passer les id de mes particules comme ça :
 

Ah, pourrais-tu être plus explicite ?
 
ps: ça rabaisse sans doute le niveau du sujet discuté   ...mais il paraît qu'en terme de perf, le plus radical reste le bon vieux tableau natif [n][n];  sachant qu'on ne pourra pas gérer d'exceptions mais si en sachant cadrer correctement...

le coup du tableau natif c'ets un bon vieux FUD.
Quant au reste : google

   bon
 
As tu déjà utilisé StlSoft ?
 
Sinon, une dernière interrogation sur les tableaux:
Un tableau fixe, déclaré ou non au début d'un programme, n'est-il pas aussi plus rapide à parcourir, du fait que ses cases mémoires sont plus compactes que celles d'un tableau dynamique qui, en fonction de la mémoire disponible à un instant T, mobilisera des cases plus disparates ?

Ca dépend si t'alloues ton tableau à N dimension comme un étudiant de L1 ou si tu mérites ton salaire (hum enfin mériter pour 3 lignes de codes...)

un tableau à N dimensions dense bien alloué est compacte et cache friendly. Sinon c'ets que tu sais pas programmer
 
J'ai donner 10 fois le code pr le faire proprement

 
Ben non, je vois tout les jorus de ingés et des psot-docs me crier que tab[][] ets plsu rapide que tout alors que meme vector<T> ou multi_array<T,N> votn strictement à la meme vitesse sur des cas normaux. Ce qui comtpe c'est le cache friendliness de l'algo pas comment ton tableau est géré (sauf remarque precedente sur l'alloc)

C'est vrai que dans mon cas, je n'ai même pas le niveau d'un mauvais étudiant    
Si j'avais compris plus tôt la puissance de la prog, j'ai pourtant eu un amiga avec des démo pirates...j'aurais changé de branche directe!.. mais bon, ch'suis plus étudiant et pouvoir apprendre grâce aux forums, c'est vraiment génial!
Merci les gars    
 

Oh oui, s'il arrive au bout de son projet, je peux te dire qu'il sera le plus heureux des hommes  

Oui, moi je prépètes ce que je lis car je commence mais toi qui exerce, en faisant tes propres tests, tu dois avoir un avis perso ?
Ce que tu m'as dis jusqu'à présent, c'était théorique ou aussi lié à ta praxis ?
 

Je découvre l'expression (http://blog.cplusplus-soup.com/200 [...] rency.html)  mais j'ai déjà rencontré un problème de processus concurrents, une boucle graphique OpenGl contre une boucle son avec buffer;  et c'est là que j'ai découvre les threads   ...

 
C'est d ela pratique, ca fait 5 ans que mon boulot c'est faire des outils de calcul haute-performances alors ce genre de blague , je les ai testé de A à Z. Moralité, l'interface entre la mémorie brute et l'utilsiateur n'a pas d'impact. La seule chose qui impact c'est la manière dont les elements sont allouées et comment on aprcourt. Engros :
 
tableau natif [][] est equivalnt à tableau dynamique dans une classe avec operator() et ces deux méthodes sont 3 à 12 fois plus rapide que des iterator.

Ok, respect    
 

 
Je le note en rouge !
...hum, encore un petit éclaircissement,  
dans  ce que tu m'as proposé plus haut, on utilise à la fois operator et iterator !?

Bah ça depends de ce que tu as besoin aussi et si ton container à une semantique de conteneur dense contigu ce qui n'est pas le cas d'une hash table.

D'accord, donc dans ce cas l'iterator est bien indispensable .
 
Sinon, comment supprimer un élément, trouver son range et redimentionner ?

lire la doc de unordered_map ?

Ben oui qd même, mais si c'est bien dans ce menu :
 
Table of Contents
 
Introduction  
The Data Structure  
Equality Predicates and Hash Functions  
Comparison with Associative Containers  
Implementation Rationale  
Change Log  
Reference  
Header <boost/unordered_set.hpp>  
Header <boost/unordered_map.hpp>  
Bibliography  
 
c que j'ai loupé un passage

Salut    
 
Tu n'aurais pas une piste, je sèche    
 
 j'ai beau lire la doc ... on parle de re_hash, unordered_multiset, de Buckets ...  
moi pas bien comprendre articulation tt ces concepts    
Je pense avoir au - compris qu'on ne pouvait pas effacer directement un élement mais qu'il fallait passer par un redimensionnement et/ou rehashage ??
 
Dans Implementation rationale j'entends parler  
Are insert and erase stable for unordered_multiset and unordered_multimap?  
It is not specified if unordered_multiset and unordered_multimap preserve the order of elements with equivalent keys (i.e. if they're stable under insert and erase). This is issue 581. The current proposal is that insert, erase and rehash are stable - so they are here.
 
...mais pas d'exemples.
 
Là seul bêtise que j'ai commencé à faire c'est:
 

Bah si Molle est un typdef de Machin*, aucun problème ?