VECTEUR CREUX

Signaler
Messages postés
147
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009
-
sazaju
Messages postés
48
Date d'inscription
lundi 4 août 2008
Statut
Membre
Dernière intervention
3 juin 2013
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/55196-vecteur-creux

sazaju
Messages postés
48
Date d'inscription
lundi 4 août 2008
Statut
Membre
Dernière intervention
3 juin 2013

Idée jetée sans trop y réfléchir : pour le coup du problème de rapidité d'accès, pense à une table de hachage. Accès en O(1), mais il faut avoir une taille donnée pour la table. Si tu gères bien tu peux avoir une table dynamique (mais nécessite généralement le re-calcul des indices) ou si on considère que ça arrive rarement avoir une solution différentes pour les valeurs en trop (e.g. liste chaînée).
opossum_farceur
Messages postés
147
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009

Hi!

Cette alternative aux vecteurs creux permet certes d'économiser la place occupée en mémoire, mais risque fort, si les données sont importantes, d'être pénalisante du point de vue des performances. En effet, la solution de stockage utilisée, à savoir la liste chaînée à accès séquentiel, n'est pas vraiment ce qui se fait de mieux : s'il y a N données, il faudra en moyenne N/2 itérations pour lire une donnée.
La solution? : utiliser std::map le tableau associatif de la STL (#include <map>) qui ordonne les données selon leur indice, et permet d'accéder à une donnée en en moyenne log(N) itérations (l'inconvénient de cette solution, c'est l'insertion des données, qui prend évidemment plus de temps, mais bon...).

Bon courage!