Discussion :

[olivier21c]

Bonjour à tous
J'ai besoin dans un programme d'utiliser un tableau contenant une liste d'objets.

La solution que j'utilise actuellement est la suivante

// déclaration
boost::multi_array<std::vector<MonObjet>, 2> MaListe( boost::extents[L][H]);
// init
std::vector<MonObjet> vec(N);
std::fill( MaListe.data(), MaListe.data() + MaListe.num_elements(), vec);

Donc j'ai ici un tableau 2D qui contient pour chaque case un vector d'objets MonObjet. (L'utilisation d'un tableau 2D est faite d'un point de vue logique car c'est en rapport avec une image, mais je peux tout à fait envisager un tableau 1D, de même pour vector).

Le problème est que j'ai dans ma fonction un nombre très important d'accès à cette structure(pour modifier un un élément du vector d'une case), et de plus je doit trier mon vector à chaque fois (de la case correspondante).
Le temps est trop important pour cette appli (cela augmente le temps de 110ms environ).

Je cherche donc tout autre moyen de stocker mes Objets, qui permette un accès le plus rapide possible.
J'espère que quelqu'un aura une petite piste pour m'aiguiller.
Merci d'avance

[koala01]

Salut,

Je voudrais être sur de comprendre ton problème...

Tu dois donc:

Pouvoir modifier les données du vecteur (et non supprimer une donnée pour en mettre une autre à la place, la différence est de taille) et
1- trier le vecteur une fois la modification effectuée ou
2- déplacer l'ensemble du vecteur dans ta matrice 2D ou encore
3- faire 1 et 2 à la suite

Quelques pistes à suivre:
S'il est envisageable de créer une nouvel objet pour le placer dans la première collection et de supprimer l'élément modifié, peut être devrais tu envisager autre chose qu'un vecteur (un set ou une map, peut être )

Si le tri de tes objets s'effectue sur des chaines de caractères, peut être devrais tu envisager de la transformer de manière à avoir un entier unique (CRC, MD5 ou autre inside )... Les chaines de caractères ne sont vraiment pas adaptées pour la comparaison rapide

Faut il réellement trier le tableau à chaque fois qu'un objet est modifié ne pourrais tu pas envisager l'utilisation d'un booléen indiquant qu'il doit être (ou non) trié, et ne le faire qu'en cas de besoin

Je m'explique là dessus: Si tu tries ton tableau à chaque fois que tu modifie un objet et que tu en modifie 5 coup sur coup, tu trie... 5 fois ton tableau, alors qu'une seule fois aurait pu suffire, après les 5 modifications...

Si tu peux te le permettre, tu as peut être intérêt à prévoir un test "dois-je trier le vecteur " avant l'accès. Si le test est à vrai, on appelle la fonction de tri, sinon, on passe directement à l'accès

[olivier21c]

Salut,

Merci de ta réponse.

Alors en fait, je me ballade à l'intérieur de mon tableau, et à chaque fois je modifie une valeur d'un élément du vector de la case courante.

Chaque modification correspond au remplacement de mon élément par un nouveau, mais comme l'élément ne comporte que des valeurs type int et float, je fais une modification des valeurs au lieu de créer un nouvel élément et de remplacer l'ancien.

Concernant le tri, ne réalité je dois remplacer le "plus mauvais" élément du vector (ce qui explique le besoin du tri).
J'utilisais pour trier la fonction std::sort en surchargeant l'opérateur <.
Et ainsi je modifiais le dernier élément du vector trié.

Finalement j'ai modifié ce point, au lieu de trier, je récupère le max du vector (std::max_element), ce qui me permet de le modifier sans trier des centaines de milliers de fois mes vector. J'ai ainsi pu gagner beaucoup de temps.

Par contre je m'intérroge toujours si l'utilisation de boost::multi_array + vector est la meilleure pour mon cas.

[koala01]

A vrai dire (je me suis levé tot ce matin suite à un mal de dents), je suis peut être extrêmement fatigué, mais je n'arrive pas à comprendre à quoi servent les différents élément que tu nous présente.

Il faudrait nous en dire plus

1. Tes objet sont composé, as-tu dis, d'un float et d'un int. Que représentent-tils
2. Ton vector d'objet est une "collection de base", à quoi sert-elle
3. Ta matrice (actuellement multi-array) contient pour chaque case une collection de base, pourquoi
4. Qu'est-ce qui a trait à l'image, dans l'histoire

A mon avis, une fois que nous aurons ces réponses, nous devrions être en mesure de t'orienter (ou peut-etre tes réponses susciteront-elles d'autres questions ...)

[Sylvain Togni]

Par contre je m'intérroge toujours si l'utilisation de boost::multi_array + vector est la meilleure pour mon cas.

Si la taille des vector est toujours la même mieux vaut un boost::multi_array à trois dimensions, cela sera plus efficace.

[atttchoum]

Si la taille des vector est toujours la même mieux vaut un boost::multi_array à trois dimensions, cela sera plus efficace.

C'est ce que je me disais mais vu que la troisième dimension dois être triée sa n'est peut être pas la meilleur solution. En même temps je ne connais pas du tout boost .

[olivier21c]

J'ai aussi pensé au multi_array à 3D, mais pas encore implémenté pour tester.
je pense que le triage ou comme je l'ai dis plus haut l'accès à max_element ne serait pas gênant.

Pour expliquer mieux mon cas:
je travaille sur une image, et pour chaque pixel de cette image je dois effectuer différents calculs, c'est la raison pour laquelle j'utilise un multi_array à 2D (mais je peux tout aussi bien faire avec une autre structure en 1D de taille W*H).

Donc pour chaque pixel un calcul de deux valeurs est effectué :
- un indice (int)
- la valeur du calcul (float) servant à la comparaison.

Pour chaque pixel, différents calculs sont ainsi effectués (mais pas tous à la suite, je dois d'abord parcourir une fois tous les pixels et faire le calcul, puis un 2eme fois, etc.).
A la base mon appli ne devait conserver que la meilleur valeur : donc il suffisait de comparer ma variable float avec le nouveau calcul et de remplacer si nouveauFloat < meilleurFloatCourant (et pas besoin de vector, juste un multi_array de int).


Cependant à présent, je souhaite conerver les N meilleures valeurs, d'où l'idée première d'utiliser un vector de taille N, où je stocke les N meilleures valeurs de chaque pixel.
Avant je triais le tableau, et maintenant je remplace juste la plus mauvaise avec std::max_element.

Voila, j'espère avoir été assez clair.