Discussion :

[eagl1]

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.

[jabbounet]

une table de hash, peu-etre ?

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

[eagl1]

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

[Mac LAK]

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 !
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.

[Niklaos]

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 !
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.

[koala01]

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

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 !
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)

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"

[Mac LAK]

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.

[_skip]

@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?

[Médinoc]

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...

[jabbounet]

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