Discussion :

[coda_blank]

Bonsoir, je cherche en C++ une lib offrant table d'association rapide avec en clé une std::string et en valeur un pointeur (sous gcc 4.5)

C'est une application graphique qui tourne en 60 frames/sec
Je dois faire un lookup sur une table de 10000 entrées environ et 10000 appels
par frame

j'étais parti sur std::unordered_map mais elle n'a pas l'air d'être très efficace sur les string même avec 01 ou 02 activés (enfin comparé à une clé en int)

Faut il que je m'oriente vers une solution "à la main" ?

[koala01]

Salut,

Le fait est que tu n'auras JAMAISde bonnes perfs en utilisant une chaine de caractères comme clé.

La raison est tout simplement la méthode de comparaison de celles-ci : il faut comparer caractères par caractères jusqu'à trouver (ou non) une différence, et cela implique une boucle !

Une valeur strictement numérique, qui soit comparable "en une seule fois" donnera forcément des performances bien meilleures

[screetch]

en même temps c'est bien pour ca qu'on a inventé le hash qui permet de ne pas comparer les chaînes trop souvent
a mon avis le problème que tu as c'est qu'avec tes std::string tu fais des allocations en permanence. Mais c'est juste une devinette, parce que en fait les vrais programmeurs utilisent un profiler de code pour savoir ce qui coûte cher. Ils disent pas au pif comme moi :o)

[coda_blank]

Salut,

Le fait est que tu n'auras JAMAISde bonnes perfs en utilisant une chaine de caractères comme clé.

La raison est tout simplement la méthode de comparaison de celles-ci : il faut comparer caractères par caractères jusqu'à trouver (ou non) une différence, et cela implique une boucle !

Une valeur strictement numérique, qui soit comparable "en une seule fois" donnera forcément des performances bien meilleures

C'est bien ce que je pensais, il me fallait juste confirmation

Par contre y a t il moyen de faire mieux que la STL si on se cantonne au couple int/pointeur

[Emmanuel Deloget]

C'est bien ce que je pensais, il me fallait juste confirmation

Par contre y a t il moyen de faire mieux que la STL si on se cantonne au couple int/pointeur

Mieux que quoi dans la STL ? Si tu parles de std::map<>, oui, il y a mieux. Dans le TR1, on a unordered_set/unordered_multiset qui sont grosso-modo des tables de hash. Avec une fonction de hashage optimale, chercher un élément dans ces ensembles est une opération de complexité constante (indépendante du nombre d'éléments insérés).

[Klaim]

Cela dit il a déjà tenté unordered_map, comme dit dans le premier post.

Le problème est fondamentalement difficile de toutes façons, juste changer de conteneur ça ne suffira jamais.

Si les données sont indépendantes, peut être qu'en organisant ton traitement en parallèle ça aidera? Ca dépends si tu as plusieurs coeurs d'execution sur ta cible cela dit.

Pour faire mieu niveau perfs, il faut voir plus haut, donc savoir plus de choses sur ce qui est traité comme données et le contexte.

[JolyLoic]

La table de hash est plus performante en complexité, mais pas forcément en pratique. J'ai eu des retours où std::map explosait std::unordered_map tant que les jeux de donnée n'explosaient pas le million. Un des problèmes avec une table de hash est le choix de la fonction de hash. La tienne est-elle bonne par rapport aux strings que tu manipules ? As-tu beaucoup de collisions ?


Est-ce que tu as souvent besoin d'accéder aux mêmes éléments ? Si oui, un splay tree pourrait être intéressant.

10000 entrées et 10000 appels par frame, pourquoi le même nombre ? Ne peux-tu pas réorganiser ton algorithme pour faire moins d'appels ?

[pyros]

Si ta clef est un int qui n'est jamais trop grand (genre < 10000), tu peux essayer un bête std::vector de taille MAX_KEY. Niveau conso mémoire, tu aura un rendement proche du néant avec beaucoup de cases inutiles, mais niveau perf tu accédera à tes éléments en temps constant... Parfois, c'est un compromis acceptable.

[Klaim]

En fait un vector ou un array c'est ce que j'ai pensé en premier mais je me dis que c'est le "cas idéal" et du coup si ya moyen de paralléliser ça pourrait être encore plus rapide.