Discussion :

[Invité]

Bonjour,

L'application sur laquelle je travaille utilise beaucoup de tableaux associatifs. Certains d'entre eux sont très gros (le principal pourrait avoir, en régime de croisière plusieurs centaines de milliers, peut être un million d'entrées), d'autres sont plus petits (quelques milliers d'entrées), mais tous sont très sollicités à l'exécution.

Ces tableaux associatifs partagent tous une caractéristique commune : on n'y fait ni insertion, ni suppression. Ils sont lus au démarrage de l'appli (ou la première fois qu'on en a besoin), dans des fichiers produits par une autre application (je peux en changer le format si nécessaire). Aujourd'hui ils sont indexés par des string.

En première approche, j'ai utilisé des map, que je charge à partir de fichiers triés selon la clef. Quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

map<string,MonType>

Et je fais appel à find() pour les recherches. Sur un fichier déjà trié, le chargement se fait en temps linéaire, et les recherches en temps logarithmique.

Après réflexion, il me semble qu'un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

vector<pair<string,MonType> >

trié dans l'ordre des clefs, et une recherche binaire, fonctionnerait mieux. A priori, le chargement est aussi linéaire (mais certainement de coefficient dominant plus faible que pour la map), la recherche aussi logarithmique, et l'empreinte mémoire sans doute plus faible...

Est ce bien le cas?

Du coup, je me demande si je peux améliorer cela...

J'ai réfléchi à deux solutions, par forcément exclusives l'une de l'autre

1- une réindexation de mes codes, destinée à remplacer les string par des entiers. Les recherches binaires effectuant des comparaisons assez nombreuses (entre 10 et 20 par recherche dans mon cas), utiliser une comparaison d'entier devrait significativement améliorer le temps de recherche, et également réduire l'empreinte mémoire de mon tableau...

2- l'utilisation d'un tableau haché (hash_map), les codes de hachage étant précalculés dans le fichier initial (pour éviter de les refaire au chargement), mais du coup, je me demande si cela n'est pas strictement équivalent à ma réindexation...

Qu'en pensez vous? Qu'utiliseriez vous?

(je précise que je suis sous Borland Builder 6, que ma STL est une STLPort, et que seuls des bouts de boost fonctionnent, en revanche, je n'aurais aucun complexe à me lancer dans un codage d'algorithme spécifique, cette recherche est réellement le coeur de l'application).

Merci d'avance
Francois

[JolyLoic]

Un vecteur de pair risque de poser problème pour les grands tableaux, car il demande à ce que la mémoire soit continue.

Je n'ai pas trop compris comment tu comptes remplacer des strings par des entiers ?

Est-ce que tu vas souvent chercher les mêmes données ? Il y a des structures d'arbres comme une map mais qui vont réordonner des données à chaque interrogation de telle manière que les demandes fréquentes soient plus proches du sommet.

Une hashmap, pourquoi pas, mais en faisant bien attention d'éviter les doublons.
Tes strings sont-ils semblables d'une exécution à l'autre ? Tu pourrais dans ce cas faire un test de la fonction de hash voir ce qu'elle vaut ?

[Invité]

Un vecteur de pair risque de poser problème pour les grands tableaux, car il demande à ce que la mémoire soit continue.

Effectivement... En fait, je me rend compte qu'il n'est pas nécessaire de stocker ensembles les clefs et les valeurs, mais juste d'associer à chaque clef "quelque chose" qui permettre de retrouver la valeur correspondante...

On pourrait donc avoir soit un vecteur de pair<clef,adresse> (l'adrresse étant un indice dans le tableau des valeurs), soit même juste un vecteur de clefs, en utilisant la position renvoyée comme l'indice dans un vecteur de valeurs...

Merci beaucoup pour la suggestion...

Je n'ai pas trop compris comment tu comptes remplacer des strings par des entiers ?

En fait, les string qui me servent de clefs sont assez peu utilisées pour elles mêmes (essentiellement lors de sauvegardes), et généralement utilisées comme index dans mes tables associatives. Dans la mesure où mes tables ne bougent pas d'une éxécution à l'autre, je me disais que je pourrais peut être tout réindexer avant l'exécution, en associant à chaque string un entier unique, et en remplaçant, partout où je peux, le string par l'entier... Ca ressemble à la notion d'index de table dans les Bases de Données, si tu veux.

De cette façon mes recherches se font sur des entiers, au lieu des strings, mais je conserve dans un coin la correspondance "index clef", pour les quelques cas ou je dois utiliser les clefs...

Est-ce que tu vas souvent chercher les mêmes données ? Il y a des structures d'arbres comme une map mais qui vont réordonner des données à chaque interrogation de telle manière que les demandes fréquentes soient plus proches du sommet.

Tu m'intéresses ! En fait, je pense que je vais avoir à peu près 500 000 entrées dans le tableau principal, mais qu'à l'éxécution, il sera rare qu'on n'ait besoin de plus d'une centaine. En fait, je sais même assez précisément (à l'exécution) quelles entrées vont revenir (certaines opérations utilisent des entrées juste une fois, d'autres indiquent qu'une entrée va souvent servir...)

En y repensant, je suis même probablement capable de classer a priori mes variables en fonction de leur fréquence d'utilisation... Peut on fabriquer une map qui prenne ces éléments en compte?

Une petite référence livresque me serait bien utile là?

Tes strings sont-ils semblables d'une exécution à l'autre ? Tu pourrais dans ce cas faire un test de la fonction de hash voir ce qu'elle vaut ?

Oui, c'est en fait un peu ce qui m'a retenu jusqu'ici, le fait de devoir trouver une fonction de hachage valable...

Francois

[JolyLoic]

Une petite référence livresque me serait bien utile là?

http://en.wikipedia.org/wiki/Splay_tree

[Invité]

http://en.wikipedia.org/wiki/Splay_tree

Merci beaucoup!

Francois

[Invité]

J'ai fait des essais toute cette semaine avec des maps de quelques dizaines de milliers d'éléments (parfois plus), indexées soit par des int soit par des string...

En gros, je les charge à partir de fichiers déjà triés (le manuel me dit que cela garantit de meilleurs temps de chargement, enfin je crois), et je les utilise pour des recherches.

Je les ai comparées à une implémentation utilisant deux vecteurs, un trié pour les clefs, l'autre pour les valeurs, et un opérateur[] surchargé utilisant la fonction lower_bound().

Ma conclusion du moment est : pas de maps. En gros, le chargement des maps est environ 8 fois plus lent que celui des vecteurs, et la recherche même pas plus rapide. D'autres ont ils essayé et rencontré se problème, ou y aurait il un gros piège dans lequel je suis tombé (ca me ressemblerait...)?

Du coup, j'ai une question annexe : la structure que j'utilise a grosso modo cette forme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
template<typename S,typename T> class MaMappe {
  vector<S> Idx;
  vector<T> Data;
}

Idx contient les clefs, Data les données. De temps en temps, il peut m'arriver d'avoir à réordonner une telle structure. Je sais trier mes clefs avec sort, bien sur, mais comment faire pour réordonner automatiquement Data (sans avoir à recopier les données...)?

Dans le même ordre d'idées, y a-t-il un moyen simple (dans la STL) pour, au lieu de trier explicitement les données d'un vecteur, construire un indice permettant de parcourir ce vecteur dans l'ordre de tri? Un paramètre à passer à sort(), une astuce comme cela?

Merci d'avance
Francois