Liste chainee avec index/indices

Bonjour a tous,
Mon interrogation est la suivante;
Je souhaiterai faire une Liste (doublement) chainee, et atteindre le 5iem element de ma liste directement avec un indice. Donc au lieu de parcourir du debut et faire "->Suivant" jusqu'au 5iem element, je souhaiterai savoir si il est possible de faire plutot un truc du genre:

Val1 = emplacement memoire du premier element.
X = Taille d'un element de ma liste
Val5 etant l'emplacement du 5iem element.

Val5 = Val1 + (5 * X) //ceci pour le 5iem element


Et donc apres lire les differentes valeurs dans mon elemment a partir de son emplacement memoire.

On pourrait penser que je pourrai utiliser directement des tableaux, mais en fait je travaille sur des nuage de points tres volumineux (300000 points par exemple).
Mes questions sont: Cela est il possible? Si oui, ou puis-je trouver des exemples ou des references?

Remarque: il 'est inenvisageable de parcourir avec des "->Suivant" ou "->Precedant" vu le nombre de fois que j'aurais a parcourir ma liste plutot volumineuse.

Merci de votre attention.

une table de hash, peu-etre ?

http://std.dkuug.dk/jtc1/sc22/wg21/d...003/n1443.html

Merci de ta reponse plutot rapide,
Je ne connais pas trop cette chose mais a premiere vue cela semble interessant. Je regarde plus en profondeur pour voir si cela me convient.
En esperant que oui ... ^^
Merci encore

Citation:

---

Envoyé par eagl1

On pourrait penser que je pourrai utiliser directement des tableaux, mais en fait je travaille sur des nuage de points tres volumineux (300000 points par exemple).

---

Oui, et alors ? Ton PC fonctionne bien avec un tableau géant d'environ un milliard d'entrées, communément appelé "RAM"... Et ça marche très bien ! :mouarf:
C'est plutôt en utilisant des listes que tu vas ralentir tes performances, SAUF si les ajouts/suppressions sont courants dans ta structure (chose que tu n'as pas précisée).

Et même si c'était le cas, pour ma part, j'utiliserais un container "maison" pour ça, c'est à dire un container hybride genre "vecteur de listes de vecteurs" permettant un morcellement des données (= fragmentation) tout en réduisant drastiquement le temps d'accès direct (ou "aléatoire") aux données.

quelques liens utiles

http://www.sgi.com/tech/stl/hash_map.html

http://www.cplusplus.com/reference/stl/map/
http://www.cplusplus.com/reference/stl/multimap/

http://www.eptacom.net/pubblicazioni...ng/mphash.html

Citation:

---

Envoyé par Mac LAK

Oui, et alors ? Ton PC fonctionne bien avec un tableau géant d'environ un milliard d'entrées, communément appelé "RAM"... Et ça marche très bien ! :mouarf:
C'est plutôt en utilisant des listes que tu vas ralentir tes performances, SAUF si les ajouts/suppressions sont courants dans ta structure (chose que tu n'as pas précisée).

Et même si c'était le cas, pour ma part, j'utiliserais un container "maison" pour ça, c'est à dire un container hybride genre "vecteur de listes de vecteurs" permettant un morcellement des données (= fragmentation) tout en réduisant drastiquement le temps d'accès direct (ou "aléatoire") aux données.

---

De meme :)

Et oui si le nombre d'entrees est Fixe (ou aproximativement connu a l'avance) le tableau est une tres bonne solution !
En revanche si sa taille peut varrier de tout a rien il serait catastrophique pour les perfs d'utiliser un tableau que tu dois realouer.

Salut,

Sémantiquement parlant, un tableau et une liste (doublement chainée ou non) évoquent deux choses bien distinctes ayant des propriétés et des capacités qui leur sont propres...

L'un est en accès aléatoire, l'autre en accès séquentiel, potentiellement dans les deux sens.

L'un permet un accès rapide à un élément donné, mais demande énormément de temps en cas d'insertion (y compris en fin de tableau) alors que l'autre mettra plus de temps à atteindre un élément donné au départ de n'importe où mais donne l'assurance qu'une insertion, quel que soit l'endroit, sera effectuée quasiment en temps constant

Ce qu'il faut, c'est arriver à te faire une idée précise de ce que tu passera le plus de temps à faire, histoire de maximiser au mieux les performances.

Maintenant, il reste peut être une solution alternative qui te permettra de retrouver un élément donné aussi rapidement que dans un tableau (grâce à la dicotomie): le tableau binaire, qui peut être une solution à envisager ;)

Citation:

---

Envoyé par Mac LAK

Oui, et alors ? Ton PC fonctionne bien avec un tableau géant d'environ un milliard d'entrées, communément appelé "RAM"... Et ça marche très bien ! :mouarf:
C'est plutôt en utilisant des listes que tu vas ralentir tes performances, SAUF si les ajouts/suppressions sont courants dans ta structure (chose que tu n'as pas précisée).

---

L'usage des tableaux présente malgré tout une limite que, pour autant que les éléments soient "suffisamment importants" (en terme de place utilisée en mémoire), les listes sont en mesure de dépasser: Le fait que tous les éléments d'un tableau utilise un espace mémoire contigus.

Comme il faut malgré tout prendre en compte le fait qu'une application donnée fonctionne régulièrement en même temps que d'autres, on ne peut exclure l'impossibilité de trouver un espace mémoire suffisant pour représenter de manière contigüe l'ensemble des éléments.

Par contre, il reste malgré tout beaucoup plus facile de trouver X fois quelques bytes "éparpillés" en mémoire que de trouver un espace capable de contenir X fois ces quelques bytes, même si la structure à représenter demande 8 (ou 16) bytes de moins (qui correspondent, tout simplement, aux référence vers l'élément précédent et l'élément suivant);)

Citation:

---

Et même si c'était le cas, pour ma part, j'utiliserais un container "maison" pour ça, c'est à dire un container hybride genre "vecteur de listes de vecteurs" permettant un morcellement des données (= fragmentation) tout en réduisant drastiquement le temps d'accès direct (ou "aléatoire") aux données.

---

Effectivement, une forme hybride peut souvent s'avérer être "la moins mauvaise solution" ;)

Citation:

---

Envoyé par koala01

Effectivement, une forme hybride peut souvent s'avérer être "la moins mauvaise solution" ;)

---

Je le pense aussi : partir sur un tableau, qui est l'entrée unique d'une liste chaînée.
A l'insertion, quel que soit l'endroit, on "coupe" le tableau en deux éléments (=> de deux à trois entrées dans la liste) au point d'insertion, et on crée un nouveau tableau pour les nouvelles données. Chaque élément de la liste doit simplement connaître la taille du tableau associé afin de pouvoir surcharger l'opérateur [] correctement.

@Mac Lak
A combien de temps évaluerais-tu la création d'un tel template? Avec sa batterie de tests unitaires et ces méthodes de base :

insert(int, object)
size()
push_back(object)
remove(int)
at(int)
operator []

Sans forcément considérer toutes les features d'une collection,les iterators et tout ça?

En fait, c'est le genre de choses pour lesquelles je verrais plus un arbre binaire de recherche (cousu si nécessaire, mais ça n'est pas forcé: des algos de parcours itératif existent) qu'une liste...
L'accès par index et l'insertion/suppression se feront en temps logarithmique...

Je dirais qu'il faudrait environ 4 jours de conception/codage pour le container, plus deux bonnes journées de tests / calculs de perfs.

Par contre, faut bien voir qu'il est peu probable que les containers de la STL soient directement utilisables : classiquement, le std::vector va poser un souci car il n'est pas capable de se scinder en deux sans recopie. Il faudra aussi prévoir une taille de base pour la création des vecteurs, de façon à ce que plusieurs ajouts au même endroit ne cause pas une explosion de l'algo par ajout d'autant de vecteurs, mais de taille 1.


Pour l'ABR, c'est également une solution, mais le calcul est biaisé si l'on optimise en mettant des vecteurs plus ou moins longs comme feuilles, car l'arbre sera alors très difficile à équilibrer... Et si l'on prends chaque élément unitaire en guise de feuille, alors on a un équilibre correct, mais on perds le gain apporté par une semi-linéarité telle que l'offre un container mixte.

Faut bien voir un truc : en optimisant fortement la liste chaînée maître, on peut tomber sur n'importe quel vecteur en O(log2(Nv)) (Nv = nombre de MORCEAUX, donc de vecteurs, et non pas nombre d'éléments), puis accès direct sur l'élément... Si l'on doit en lire plusieurs consécutivement, l'accès est immédiat (O(1)) tant que l'on ne change pas de segment.
Sur un ABR classique, par contre, c'est CHAQUE élément qui sera accédé en O(log2(N)) (N=nombre d'éléments total).

Citation:

---

Envoyé par Mac LAK

Sur un ABR classique, par contre, c'est CHAQUE élément qui sera accédé en O(log2(N)) (N=nombre d'éléments total).

---

Pas en passant par un itérateur bien conçu (via parcours itératif ou arbre cousu).

Citation:

---

Envoyé par Médinoc

Pas en passant par un itérateur bien conçu (via parcours itératif ou arbre cousu).

---

Ce qui implique soit une rémanence de la position courante (inutile, voire pénalisante en cas d'accès aléatoires), soit une complexité d'implémentation bien supérieure à celle que je propose.

Pour un "aussi faible" nombre d'éléments que 300.000, je pense qu'il est inutile (et même coûteux !) de sortir de l'artillerie lourde digne d'un SGBD ou filesystem, tu ne crois pas ? ;)

Votre solution de container maison hybride tel que vous la décrivez ressemble fort à de la pagination.
Personnellement je n'ai jamais éprouvé le besoin d'utiliser des listes et m'en suis toujours tiré avec des vector ou des set/map (voire unordered_set). Si jamais je devais un jour paginer je manipulerais des tableaux de taille fixe de vector (voire shared_array) dans des set. L'avantage serait aussi de pouvoir stocker les pages sur disque si le volume de données est susceptible de dépasser la taille mémoire disponible.

Citation:

---

Envoyé par camboui

Votre solution de container maison hybride tel que vous la décrivez ressemble fort à de la pagination.

---

Pas tout à fait : la pagination se base habituellement sur des pages de taille fixe, et il faut "faire avec" la taille des pages.
Dans ma solution, les segments sont de taille libre : en l'occurrence, sur un tableau (même énorme) alloué une seule fois sans aucune insertion / suppression, l'accès est identique à celui d'un (std::vector)* (avec une indirection supplémentaire).

Le but d'un tel container, c'est de permettre des ajouts/suppressions de masse extrêmement rapidement (=sans recopies), tout en assurant au maximum l'accès en O(1). Le prix, c'est une consommation mémoire qui peut ne pas être optimale à cause des segments partiellement remplis (ou sous-utilisés si on préfère ce terme).

Citation:

---

Envoyé par camboui

Si jamais je devais un jour paginer je manipulerais des tableaux de taille fixe de vector (voire shared_array) dans des set.

---

Et tu aurais des copies à chaque insertion en milieu de "tableau", c'est là le problème.

Citation:

---

Envoyé par camboui

L'avantage serait aussi de pouvoir stocker les pages sur disque si le volume de données est susceptible de dépasser la taille mémoire disponible.

---

Vu qu'avec ma méthode, tu dois faire des allocations manuellement ("refaire" un vector, en fait), rien ne t'empêche d'utiliser de l'allocation virtuelle et de rendre les segments swappables... ;)

Citation:

---

Envoyé par Mac LAK

Je dirais qu'il faudrait environ 4 jours de conception/codage pour le container, plus deux bonnes journées de tests / calculs de perfs.

---

Ca demande tout de même une bonne petite semaine d'implémentation donc, ce qui n'est absolument pas trivial. Perso dans mon secteur on ne m'offrirait malheureusement jamais ce temps...

Inconvénients du "do it yourself" ma foi :aie:

Citation:

---

Envoyé par _skip

Ca demande tout de même une bonne petite semaine d'implémentation donc, ce qui n'est absolument pas trivial. Perso dans mon secteur on ne m'offrirait malheureusement jamais ce temps...

Inconvénients du "do it yourself" ma foi :aie:

---

J'ai vu pire... On doit coder pour le lendemain des trucs non conceptualisés. Prétexte: "ça ressemble à ce qu'on a déjà fait 3 ans plus tôt, y'a qu'à le reprendre et l'adapter; z'avez un jour et pis c'est tout !" (ce cher yaka). Autant dire que les tests ont lieu en production. Heureusement qu'on ne fait que du traitement de donnée et qu'il n'y a pas de chaines de montage ou autre processus industriel qui en dépend.

Citation:

---

Envoyé par _skip

Ca demande tout de même une bonne petite semaine d'implémentation donc, ce qui n'est absolument pas trivial. Perso dans mon secteur on ne m'offrirait malheureusement jamais ce temps...

---

Dans le mien non plus, je te rassures : je "masque" ce genre de dev assez facilement toutefois, merci les compilations qui durent des plombes et les MAJ depuis la gestion de configuration qui sont encore plus longues... :mouarf:
C'est justement pendant ce "temps mort" fréquent que je réponds sur DVP, d'ailleurs : si c'est pour me simplifier la vie derrière (ou éviter que le client ne hurle), soit je le rentabilise au max, soit je shifte mes délais.

Dans tous les cas, le chiffre que j'annonce est avec documentation bétonnée : si c'est juste "pisser le code" et que tu arrives à mettre la main sur un programme de test de container STL (pour ne pas avoir à l'écrire toi-même), comptes deux jours.

Salut a tous,
Deja, Desole de repondre si tard (je suis alle une semaine a New York City :) ). Ensuite, merci beaucoup de vos interventions, je ne m'attendais pas a tant de commentaires.

Avant tout je tiens a preciser que les donnees sur lesquelles je travaille peuvent etre tres legeres (10000 points) a tres tres lourdes (voisinant le million de points, ou moins, ou plus) etant donne que je fais des reconstructions de reels terrains sinistres (building ecroules par exemple).

Lorsque je disais que je ne voulais pas utiliser de tableaux, c'est par ce que je me rappelais que dans mon passe, en utilisant des tableaux trop gros, le programme me donnait des trucs bisard. Mais il est vrai qu'en refaisant des tests, la ca marchait. Serait-ce par ce que les ordinateurs que j'utilisais a l'epoque n'avait pas assez de resources??? Enfin bref, l'utilisation de tableau reste qd meme inaproprie car la taille des donnees varie enormement d'une scene a une autre.

En ce qui concerne les nuages de points sur lesquels je travail, j'ai reussi a me creer une liste (doublement chainee) que je subdivise en octree qui marche pas trop mal jusqu'a maintenant (J'importe un fichier de 400000 points et cree l'octree en moins de 8sec avec un simple P4 3.00Ghz et 1Go de ram).
Mais, ce topic a ete creer car je voulais trouver un moyen de stocker les informations d'un fichier OBJ qui represente la verite du terrain (comme un CAD). Et donc comparer la reconstruction a partir de mon nuage a ce model OBJ.
Et donc, ce que j'utilisais pour travailler avec mes nuages etait tres difficilement adaptable pour l'importation des fichier OBJ (car dans un fichier OBJ, on a les coordonnes des points mais aussi les indices de points pour les polygone de la scene (ce qui n'etait pas prevu a l'origine avec mes listes(je me moque des normales et des textures))).

Alors apres reflexions de mes reels besoins et lectures des differents liens, j'en suis venu a une solution plutot simple mais qui a l'air de marcher pas trop mal.
J'utilise les vecteurs de la STL, J'ai donc deux vecteurs de structures, un pour les coordonnees et un pour les indices des points des polygones.
Je pense que certain d'entre vous penserons que C moche, mais ca marche pour le moment, c'est tout ce que je demande, :)
Je ne sais pas si je suis tout a fait clair dans ce que je dis, donc si vous voulez des precisions, demandez moi, je ferai de mon mieu pour repondre.

Merci encore de vos interventions.
Eagl

PS : Comme ce que je voulais faire a l'air de marcher pas trop mal, je me permets de mettre RESOLU :)

cool si tu as trouvé ta solution.