VECTEUR CREUX
opossum_farceur
Messages postés
147
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009
-
2 juin 2013 à 22:21
sazaju Messages postés 48 Date d'inscription lundi 4 août 2008 Statut Membre Dernière intervention 3 juin 2013 - 3 juin 2013 à 21:59
sazaju Messages postés 48 Date d'inscription lundi 4 août 2008 Statut Membre Dernière intervention 3 juin 2013 - 3 juin 2013 à 21:59
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
https://codes-sources.commentcamarche.net/source/55196-vecteur-creux
3 juin 2013 à 21:59
2 juin 2013 à 22:21
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!