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