tableau associatif

Thomas LEDUC wrote:

bonjour,

Bonjour,

Connaissez vous une implémentation robuste des tableaux associatifs
(table de hachage - collections d'éléments avec une indexation non
entière) en C ?

Je dirais bien std::map ;-) ...
Il y a par exemple la Kazlib :
doc module de hachage :
http://users.footprints.net/~kaz/kazlib_doc/node78.html
telechargement : http://users.footprints.net/~kaz/kazlib.html

En bref, quelque chose qui me permette de stocker et
retrouver "rapidement" un index de type chaîne de caractères
(comme par exemple : "1,106,-12,13,-123,14,89") au sein de la
structure.

A faire soi-même ce n'est pas bien compliqué mis à part la fonction
de hachage qui va demander plus d'attention. Si tu cherches "hash
functions"+C sous Google, tu auras des liens intéressants dont
celui-ci : http://burtleburtle.net/bob/hash/doobs.html

Regis

Targeur fou wrote:

Thomas LEDUC wrote:

Connaissez vous une implémentation robuste des tableaux
associatifs (table de hachage - collections d'éléments avec
une indexation non entière) en C ?

Je dirais bien std::map ;-) ...

Qui n'est pas un tableau haché, mais un arbre équilibré.
(N'empèche que pour jusqu'à quelque milliers d'éléments, on ne
remarque pas la différence en temps.)

Il y a par exemple la Kazlib :
doc module de hachage :
http://users.footprints.net/~kaz/kazlib_doc/node78.html
telechargement : http://users.footprints.net/~kaz/kazlib.html

En bref, quelque chose qui me permette de stocker et retrouver
"rapidement" un index de type chaîne de caractères (comme par
exemple : "1,106,-12,13,-123,14,89") au sein de la structure.

A faire soi-même ce n'est pas bien compliqué mis à part la
fonction de hachage qui va demander plus d'attention.

En effet. Et c'est un travail qu'il faudrait fournir aussi si tu
récupère un algorithme du tableau haché tout fait.

Si tu cherches "hash functions"+C sous Google, tu auras des
liens intéressants dont celui-ci :
http://burtleburtle.net/bob/hash/doobs.html

C'est le grand problème avec le reseau ; on trouve tout, du bon
et du mauvais. D'après les tests que j'ai fait, sur une variété
de données, les meilleurs hachages se basaient sur un simple
application multiplicative :

h[i] = (A * h[i + 1] + c[i]) % 2^N ;

(ou c, c'était la chaîne à hacher, et c[i] le i-ième caractère).
Mais évidemment, pas pour n'importe quelle valeur de A:-). Tous
mes tests utilisaient N == 32 ; sur une machine de 32 bits,
faire le calcul sur des unsigned int fait le modulo
automatiquement. Pour A, j'ai eu de bons résultats avec des
valeurs 31, 127 et 16777619 ; le meilleur résultat n'était pas
le même selon le jeu de données, mais la différence se tenait
toujours dans l'incertitude de la mésure. (Les deux premières
valeurs sont des primes de Mersenne. Pour la troisième, voir
http://www.isthe.com/chongo/tech/comp/fnv/. Où d'ailleurs ils
utilisent un ^ à la place du + dans l'algorithme.)

Parmi les hachages que j'ai essayé, le Pearson (d'un article
dans les CACM) et le Jenkins (l'article dont tu as posté l'URL)
étaient systèmatiquement les pire -- entre 20% et 50% plus
lents. Mais je n'ai essayé que des codes prétendus bons -- on
peut certainement faire beaucoup pire.

Quand j'aurais du temps, je veux réfaire les tests, en ajoutant
et des jeux de données et encore des hachages. J'ai constaté un
certain nombre d'anomalies, que j'aimerais investigué. (Donc,
par exemple, sur la plupart des jeux de données, A = 1047 était
aussi vite que les valeurs ci-dessus, mais avec un, et un seul
jeu de données, elle était prèsque 6 fois plus lente.) Aussi, je
n'ai mésuré que les temps d'accès (ce qui est après tout ce qui
nous intéresse le plus) ; j'aimerais instrumenté pour mésurer
aussi le nombre de comparaisons, etc.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

James Kanze wrote:

Targeur fou wrote:

Thomas LEDUC wrote:

Connaissez vous une implémentation robuste des tableaux
associatifs (table de hachage - collections d'éléments avec
une indexation non entière) en C ?

Je dirais bien std::map ;-) ...

Qui n'est pas un tableau haché, mais un arbre équilibré.
(N'empèche que pour jusqu'à quelque milliers d'éléments, on ne
remarque pas la différence en temps.)

bah...cela reste quand même un super conteneur associatif.

[coupé]

Si tu cherches "hash functions"+C sous Google, tu auras des
liens intéressants dont celui-ci :
http://burtleburtle.net/bob/hash/doobs.html

C'est le grand problème avec le reseau ; on trouve tout, du bon
et du mauvais. D'après les tests que j'ai fait, sur une variété
de données, les meilleurs hachages se basaient sur un simple
application multiplicative :

h[i] = (A * h[i + 1] + c[i]) % 2^N ;

(ou c, c'était la chaîne à hacher, et c[i] le i-ième caractère).
Mais évidemment, pas pour n'importe quelle valeur de A:-). Tous
mes tests utilisaient N == 32 ; sur une machine de 32 bits,
faire le calcul sur des unsigned int fait le modulo
automatiquement. Pour A, j'ai eu de bons résultats avec des
valeurs 31, 127 et 16777619 ; le meilleur résultat n'était pas
le même selon le jeu de données, mais la différence se tenait
toujours dans l'incertitude de la mésure. (Les deux premières
valeurs sont des primes de Mersenne. Pour la troisième, voir
http://www.isthe.com/chongo/tech/comp/fnv/. Où d'ailleurs ils
utilisent un ^ à la place du + dans l'algorithme.)

J'ai relu il y a peu le bouquin de Sedgewick (algos en C) a propos des
fonctions de hachage et utiliser N (taille de la table, i.e. nombre de
noeuds de liste primaires) premier avec une simple méthode additive
modulo N (méthode de Horner) semble être ce qu'il y a de mieux comme
compromis simplicité/efficacité.

[coupé]

Quand j'aurais du temps, je veux réfaire les tests, en ajoutant
et des jeux de données et encore des hachages. J'ai constaté un
certain nombre d'anomalies, que j'aimerais investigué. (Donc,
par exemple, sur la plupart des jeux de données, A = 1047 était
aussi vite que les valeurs ci-dessus, mais avec un, et un seul
jeu de données, elle était prèsque 6 fois plus lente.) Aussi, je
n'ai mésuré que les temps d'accès (ce qui est après tout ce qui
nous intéresse le plus) ; j'aimerais instrumenté pour mésurer
aussi le nombre de comparaisons, etc.

Je te souhaite du courage pour tester tout ça ;). Si la fonction de
hachage est correcte et distribue à peu près uniformément M
éléments dans une table de N noeuds primaires (temps d'accès
"presque" direct ici), avec M>N, on peut s'attendre à retrouver un
élément dans un temps proportionnel à M/N. Au pire, ce sera dans un
temps proportionnel à M (le hachage est cassé :)).

Regis

Targeur fou wrote:

Si tu cherches "hash functions"+C sous Google, tu auras des
liens intéressants dont celui-ci :
http://burtleburtle.net/bob/hash/doobs.html

Presente des methodes trop couteuses sans reelle plus-value.

C'est le grand problème avec le reseau ; on trouve tout, du bon
et du mauvais. D'après les tests que j'ai fait, sur une variété
de données, les meilleurs hachages se basaient sur un simple
application multiplicative :

h[i] = (A * h[i + 1] + c[i]) % 2^N ;

(ou c, c'était la chaîne à hacher, et c[i] le i-ième caractère).
Mais évidemment, pas pour n'importe quelle valeur de A:-). Tous
mes tests utilisaient N == 32 ; sur une machine de 32 bits,
faire le calcul sur des unsigned int fait le modulo
automatiquement. Pour A, j'ai eu de bons résultats avec des
valeurs 31, 127 et 16777619 ; le meilleur résultat n'était pas

effectivement, ce sont toutes les constantes que j'ai retenues pour des
strings (j'utilise 31).

le même selon le jeu de données, mais la différence se tenait
toujours dans l'incertitude de la mésure. (Les deux premières
valeurs sont des primes de Mersenne.

Et d'utilisation particulierement rapide.

Pour la troisième, voir

http://www.isthe.com/chongo/tech/comp/fnv/. Où d'ailleurs ils
utilisent un ^ à la place du + dans l'algorithme.)

Vraie multiplication.

J'ai relu il y a peu le bouquin de Sedgewick (algos en C) a propos des
fonctions de hachage et utiliser N (taille de la table, i.e. nombre de
noeuds de liste primaires) premier avec une simple méthode additive
modulo N (méthode de Horner) semble être ce qu'il y a de mieux comme
compromis simplicité/efficacité.

taille de table premier est plus lent que prendre N = 2^M (modulo =
mask). Dans ce cas c'est la constante additive qui doit etre premiere
(pas plus cher).

a+, ld.

Laurent Deniau wrote:

Targeur fou wrote:

Si tu cherches "hash functions"+C sous Google, tu auras des
liens intéressants dont celui-ci :
http://burtleburtle.net/bob/hash/doobs.html

Presente des methodes trop couteuses sans reelle plus-value.

C'était mon impression aussi, quand je l'ai vu. J'ai mésuré pour
en être sûr ; les mésures ont confirmé l'impression.

C'est le grand problème avec le reseau ; on trouve tout, du bon
et du mauvais. D'après les tests que j'ai fait, sur une variété
de données, les meilleurs hachages se basaient sur un simple
application multiplicative :

h[i] = (A * h[i + 1] + c[i]) % 2^N ;

(ou c, c'était la chaîne à hacher, et c[i] le i-ième caractère).
Mais évidemment, pas pour n'importe quelle valeur de A:-). Tous
mes tests utilisaient N == 32 ; sur une machine de 32 bits,
faire le calcul sur des unsigned int fait le modulo
automatiquement. Pour A, j'ai eu de bons résultats avec des
valeurs 31, 127 et 16777619 ; le meilleur résultat n'était pas

effectivement, ce sont toutes les constantes que j'ai retenues
pour des strings (j'utilise 31).

Ce qui est celui qui sert en Java aussi.

J'en suis un peu méfiant. La valeur maximum est limitée pour des
chaînes très courtes. Donc, par exemple, pour des chaînes de
deux caractères, le code haché ne serait jamais plus que 8160,
alors qu'il y 65356 chaînes possibles, et on pourrait bien
imaginer un cas où le table contient 10000 éléments ou plus.
(Mais le mot opératif ici, c'est imaginer -- je doute que le cas
se produise beaucoup dans la pratique.)

le même selon le jeu de données, mais la différence se
tenait toujours dans l'incertitude de la mésure. (Les deux
premières valeurs sont des primes de Mersenne.

Et d'utilisation particulierement rapide.

Ça dépend de la machine. Sur un IA-32 moderne, je doute que ça
fait une différence. Si la machine n'a pas de multiplication
rapide, en revanche, la multiplication par une prime de Mersenne
se fait effectivement avec un décalage et une soustraction. (En
passant, autant que je sache, je suis le premier à proposer
l'idée.)

Pour la troisième, voir

http://www.isthe.com/chongo/tech/comp/fnv/. Où d'ailleurs ils
utilisent un ^ à la place du + dans l'algorithme.)

Vraie multiplication.

Tout à fait. Reste que sur un Sun Sparc (avec une multiplication
assez lente), il est aussi rapide que les autres. Je n'ai pas eu
le temps d'évaluer plus loin, pour voir si c'est parce que le
compilateur arrivait à optimiser cette multiplication aussi, ou
si c'est parce qu'il a effectivement une meilleur répartition.

Quand j'ai inventé l'utilisation des primes de Mersenne, je
travaillais sur un 8086. Et le compilateur ne savait pas
convertir les multiplications par une constante en des décalages
et des additions ou des soustractions. Là, il y avait
effectivement une différence de temps d'une facteur d'à peu près
cinq.

J'ai relu il y a peu le bouquin de Sedgewick (algos en C) a
propos des fonctions de hachage et utiliser N (taille de la
table, i.e. nombre de noeuds de liste primaires) premier avec
une simple méthode additive modulo N (méthode de Horner)
semble être ce qu'il y a de mieux comme compromis
simplicité/efficacité.

taille de table premier est plus lent que prendre N = 2^M
(modulo = mask). Dans ce cas c'est la constante additive qui
doit etre premiere (pas plus cher).

En général, on fait le calcul modulo 2^N, ou N est le nombre de
bits de la machine, ce qui veut dire que le modulo est gratuit.
Seulement une fois calculer sur la chaîne complète, on fait
modulo la taille de la table. Ça limite les dégats.

Mais en fait, j'utilise aussi systèmatiquement des tables de
taille 2^n, simplement parce que c'est plus facile à les faire
grandir -- je garde le hachage initial dans le noeud, et quand
je dois faire grandir, je double la taille de la table ; trouver
la place dans la nouvelle table va alors très vite.

--
James Kanze home: www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

James Kanze wrote:

Quand j'ai inventé l'utilisation des primes de Mersenne, je
travaillais sur un 8086. Et le compilateur ne savait pas
convertir les multiplications par une constante en des décalages
et des additions ou des soustractions. Là, il y avait
effectivement une différence de temps d'une facteur d'à peu près
cinq.

J'ai relu il y a peu le bouquin de Sedgewick (algos en C) a
propos des fonctions de hachage et utiliser N (taille de la
table, i.e. nombre de noeuds de liste primaires) premier avec
une simple méthode additive modulo N (méthode de Horner)
semble être ce qu'il y a de mieux comme compromis
simplicité/efficacité.

taille de table premier est plus lent que prendre N = 2^M
(modulo = mask). Dans ce cas c'est la constante additive qui
doit etre premiere (pas plus cher).

En général, on fait le calcul modulo 2^N, ou N est le nombre de
bits de la machine, ce qui veut dire que le modulo est gratuit.
Seulement une fois calculer sur la chaîne complète, on fait
modulo la taille de la table. Ça limite les dégats.

Mais en fait, j'utilise aussi systèmatiquement des tables de
taille 2^n, simplement parce que c'est plus facile à les faire
grandir -- je garde le hachage initial dans le noeud, et quand
je dois faire grandir, je double la taille de la table ; trouver
la place dans la nouvelle table va alors très vite.

Oui je prenais deja 2^N pour la taille de la taible. Et de plus, si tu
resouts les collisions par double hash ou une sequence au lieu d'une
liste, c'est plus rapide (modulo immediat). De plus le deuxieme hash a
seulement besoin de retourner une valeur impaire pour etre premier avec
2^N, ce qui est tres facile. Et enfin, on peut recalculer tres
rapidement la nouvelle taille minimum de la table pour qu'il n'y est
plus de collision, puis on arrondit au 2^N superieur. C'est ce que je
m'autorise quand le ratio nouvelle_taille/occupation reste raisonable ce
qui me permet de retourner (temporairement) en O(1).

a+, ld.