90

Pollux (./88) :
ALC = n_entrées/NC


Non, le nombre de colision de chaque case (ou il y a collision) / nombre de chaines

(chaine = case ou il y a eu 1 ou plus de colision)

sinon on aurait la meme valeur pour chaques

Normalement les meme valeurs que thibeau sont présente dans le tableau si ce n'est la variance (je vais l'ajouter)
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

91

ben non, le produit NC*ALC est constant (= n_entrées, d'où ma formule)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

92

(edit; non je dit une bétise sur le comptage)
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

93

Pour calculer l'écart type, qui caractérisera la "randomization" de l'algo, on a besoin d'une moyenne qui prend en compte tout, même les cases vides. Je me trompe ?
[edit] ok wink
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

94

Pollux: tu trouve plus interessant "nbelement/nbcase" ? (ce qui est calculé par thibaut pour la moyenne ? c'est meme pas lié a la fonction de hashage...)

Sinon avec la variance :
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest
--------------------------------------------------------------------------------
Table size : 42
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          189     1       0       42       95.24  100.00   95.24  6180.51
 1      PJWHash         180     1       0       42       95.24  100.00   95.24  2393.23
 2      ELFHash         180     1       0       42       95.24  100.00   95.24  2393.23
 3      BKDRHash        282     1       0       42       95.24  100.00   95.24  9099.37
 4      SDBMHash        180     1       0       42       95.24  100.00   95.24  6076.23
 5      DJBHash         195     2       0       42       95.24  100.00   95.24  6212.04
 6      DEKHash         116     1       0       42       95.24  100.00   95.24   73.51
 7      BPHash          148     1       0       42       95.24  100.00   95.24  2272.71
 8      FNVHash         188     2       0       42       95.24  100.00   95.24  6136.13
 9      APHash          129     1       0       42       95.24  100.00   95.24  124.32
10      StpdHash        1800    1       32      10      400.00   23.81   95.24  132625.94
11      ThibHash        300     1       13      29      137.93   69.05   95.24  6674.04
--------------------------------------------------------------------------------
Table size : 50
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          168     1       0       50       80.00  100.00   80.00  4358.88
 1      PJWHash         175     1       0       50       80.00  100.00   80.00  1865.32
 2      ELFHash         175     1       0       50       80.00  100.00   80.00  1865.32
 3      BKDRHash        166     1       0       50       80.00  100.00   80.00  4344.68
 4      SDBMHash        162     1       0       50       80.00  100.00   80.00  4331.92
 5      DJBHash         160     1       0       50       80.00  100.00   80.00  4295.32
 6      DEKHash         96      1       0       50       80.00  100.00   80.00   66.60
 7      BPHash          126     1       0       50       80.00  100.00   80.00  1605.40
 8      FNVHash         171     1       0       50       80.00  100.00   80.00  4351.24
 9      APHash          100     1       0       50       80.00  100.00   80.00   69.36
10      StpdHash        1800    1       39      11      363.64   22.00   80.00  112611.88
11      ThibHash        250     1       20      30      133.33   60.00   80.00  6481.68
--------------------------------------------------------------------------------
Table size : 100
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          109     1       0       100      40.00  100.00   40.00  1287.42
 1      PJWHash         162     1       0       100      40.00  100.00   40.00  1509.74
 2      ELFHash         162     1       0       100      40.00  100.00   40.00  1509.74
 3      BKDRHash        115     1       9       91       43.96   91.00   40.00  1385.22
 4      SDBMHash        111     1       2       98       40.82   98.00   40.00  1373.02
 5      DJBHash         159     1       25      75       53.33   75.00   40.00  3642.90
 6      DEKHash         83      1       0       100      40.00  100.00   40.00  520.66
 7      BPHash          108     1       0       100      40.00  100.00   40.00  1377.74
 8      FNVHash         99      1       1       99       40.40   99.00   40.00  1145.80
 9      APHash          53      1       0       100      40.00  100.00   40.00   30.88
10      StpdHash        1800    1       89      11      363.64   11.00   40.00  57905.94
11      ThibHash        220     1       56      44       90.91   44.00   40.00  3375.18
--------------------------------------------------------------------------------
Table size : 256
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          124     1       32      224      17.86   87.50   15.62  944.67
 1      PJWHash         201     1       150     106      37.74   41.41   15.62  1207.43
 2      ELFHash         201     1       150     106      37.74   41.41   15.62  1207.43
 3      BKDRHash        127     1       81      175      22.86   68.36   15.62  938.22
 4      SDBMHash        1842    1       159     97       41.24   37.89   15.62  15926.27
 5      DJBHash         900     2       215     41       97.56   16.02   15.62  8468.13
 6      DEKHash         220     2       167     89       44.94   34.77   15.62  1112.35
 7      BPHash          1099    1       234     22      181.82    8.59   15.62  8419.93
 8      FNVHash         47      1       3       253      15.81   98.83   15.62  188.27
 9      APHash          24      1       0       256      15.62  100.00   15.62   16.36
10      StpdHash        1800    1       245     11      363.64    4.30   15.62  23000.37
11      ThibHash        200     1       195     61       65.57   23.83   15.62  1380.19
--------------------------------------------------------------------------------
Table size : 257
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          24      2       0       257      15.56  100.00   15.56   10.40
 1      PJWHash         175     1       40      217      18.43   84.44   15.56  572.92
 2      ELFHash         175     1       40      217      18.43   84.44   15.56  572.92
 3      BKDRHash        25      1       0       257      15.56  100.00   15.56   16.60
 4      SDBMHash        28      1       0       257      15.56  100.00   15.56   23.80
 5      DJBHash         22      1       0       257      15.56  100.00   15.56    5.56
 6      DEKHash         39      1       0       257      15.56  100.00   15.56   41.10
 7      BPHash          50      7       69      188      21.28   73.15   15.56  198.57
 8      FNVHash         32      1       0       257      15.56  100.00   15.56   16.42
 9      APHash          28      1       0       257      15.56  100.00   15.56   15.69
10      StpdHash        1800    1       246     11      363.64    4.28   15.56  22911.82
11      ThibHash        200     1       196     61       65.57   23.74   15.56  1375.76
--------------------------------------------------------------------------------
Table size : 1000
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          22      2       255     745       5.37   74.50    4.00   30.51
 1      PJWHash         63      1       128     872       4.59   87.20    4.00   40.09
 2      ELFHash         63      1       128     872       4.59   87.20    4.00   40.09
 3      BKDRHash        45      1       434     566       7.07   56.60    4.00   62.82
 4      SDBMHash        25      1       346     654       6.12   65.40    4.00   33.93
 5      DJBHash         36      1       723     277      14.44   27.70    4.00   89.98
 6      DEKHash         22      1       110     890       4.49   89.00    4.00   18.89
 7      BPHash          34      1       514     486       8.23   48.60    4.00   43.57
 8      FNVHash         18      1       253     747       5.35   74.70    4.00   15.11
 9      APHash          10      4       22      978       4.09   97.80    4.00    3.86
10      StpdHash        1800    1       989     11      363.64    1.10    4.00  5934.59
11      ThibHash        200     1       939     61       65.57    6.10    4.00  399.83
--------------------------------------------------------------------------------
Table size : 1024
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          33      1       327     697       5.74   68.07    3.91   59.47
 1      PJWHash         101     1       600     424       9.43   41.41    3.91   81.06
 2      ELFHash         101     1       600     424       9.43   41.41    3.91   81.06
 3      BKDRHash        36      1       453     571       7.01   55.76    3.91   60.24
 4      SDBMHash        462     2       734     290      13.79   28.32    3.91  995.49
 5      DJBHash         227     2       905     119      33.61   11.62    3.91  547.63
 6      DEKHash         110     4       891     133      30.08   12.99    3.91  177.45
 7      BPHash          559     1       936     88       45.45    8.59    3.91  661.07
 8      FNVHash         16      3       251     773       5.17   75.49    3.91   15.04
 9      APHash          10      6       11      1013      3.95   98.93    3.91    3.35
10      StpdHash        1800    1       1013    11      363.64    1.07    3.91  5795.87
11      ThibHash        200     1       963     61       65.57    5.96    3.91  390.82
--------------------------------------------------------------------------------
Table size : 5178
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          5       7       2692    2486      1.61   48.01    0.77    0.94
 1      PJWHash         45      1       2631    2547      1.57   49.19    0.77    1.44
 2      ELFHash         45      1       2631    2547      1.57   49.19    0.77    1.44
 3      BKDRHash        5       9       2793    2385      1.68   46.06    0.77    1.02
 4      SDBMHash        6       5       2871    2307      1.73   44.55    0.77    1.14
 5      DJBHash         8       2       2958    2220      1.80   42.87    0.77    1.28
 6      DEKHash         5       2       2331    2847      1.40   54.98    0.77    0.72
 7      BPHash          4       45      2352    2826      1.42   54.58    0.77    0.75
 8      FNVHash         6       12      2898    2280      1.75   44.03    0.77    1.18
 9      APHash          6       1       2400    2778      1.44   53.65    0.77    0.78
10      StpdHash        1800    1       5167    11      363.64    0.21    0.77  1148.61
11      ThibHash        200     1       5117    61       65.57    1.18    0.77   79.71
--------------------------------------------------------------------------------
Table size : 9728
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          8       6       7663    2065      1.94   21.23    0.41    1.03
 1      PJWHash         49      1       7393    2335      1.71   24.00    0.41    1.35
 2      ELFHash         49      1       7393    2335      1.71   24.00    0.41    1.35
 3      BKDRHash        8       1       7693    2035      1.97   20.92    0.41    0.99
 4      SDBMHash        63      1       8990    738       5.42    7.59    0.41   11.51
 5      DJBHash         30      2       9060    668       5.99    6.87    0.41    6.17
 6      DEKHash         10      6       8279    1449      2.76   14.90    0.41    1.52
 7      BPHash          43      2       8912    816       4.90    8.39    0.41    6.46
 8      FNVHash         6       1       6847    2881      1.39   29.62    0.41    0.54
 9      APHash          4       5       6461    3267      1.22   33.58    0.41    0.41
10      StpdHash        1800    1       9717    11      363.64    0.11    0.41  611.53
11      ThibHash        200     1       9667    61       65.57    0.63    0.41   42.58
--------------------------------------------------------------------------------
Table size : 54862
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          4       1       51264   3598      1.11    6.56    0.07    0.08
 1      PJWHash         46      1       51129   3733      1.07    6.80    0.07    0.12
 2      ELFHash         46      1       51129   3733      1.07    6.80    0.07    0.12
 3      BKDRHash        3       2       51031   3831      1.04    6.98    0.07    0.07
 4      SDBMHash        3       4       51069   3793      1.05    6.91    0.07    0.08
 5      DJBHash         3       3       51032   3830      1.04    6.98    0.07    0.07
 6      DEKHash         2       122     50984   3878      1.03    7.07    0.07    0.07
 7      BPHash          2       196     51058   3804      1.05    6.93    0.07    0.07
 8      FNVHash         3       9       51110   3752      1.07    6.84    0.07    0.08
 9      APHash          3       2       51023   3839      1.04    7.00    0.07    0.07
10      StpdHash        1800    1       54851   11      363.64    0.02    0.07  108.46
11      ThibHash        200     1       54801   61       65.57    0.11    0.07    7.57
--------------------------------------------------------------------------------
Table size : 98751
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          3       2       94821   3930      1.02    3.98    0.04    0.04
 1      PJWHash         45      1       94887   3864      1.04    3.91    0.04    0.07
 2      ELFHash         45      1       94887   3864      1.04    3.91    0.04    0.07
 3      BKDRHash        2       37      94788   3963      1.01    4.01    0.04    0.04
 4      SDBMHash        2       34      94785   3966      1.01    4.02    0.04    0.04
 5      DJBHash         2       35      94786   3965      1.01    4.02    0.04    0.04
 6      DEKHash         2       58      94809   3942      1.01    3.99    0.04    0.04
 7      BPHash          2       90      94841   3910      1.02    3.96    0.04    0.04
 8      FNVHash         3       4       94846   3905      1.02    3.95    0.04    0.04
 9      APHash          3       2       94831   3920      1.02    3.97    0.04    0.04
10      StpdHash        1800    1       98740   11      363.64    0.01    0.04   60.26
11      ThibHash        200     1       98690   61       65.57    0.06    0.04    4.21
--------------------------------------------------------------------------------
Table size : 104729
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR
 0      RSHash          2       36      100765  3964      1.01    3.79    0.04    0.04
 1      PJWHash         45      1       100928  3801      1.05    3.63    0.04    0.06
 2      ELFHash         45      1       100928  3801      1.05    3.63    0.04    0.06
 3      BKDRHash        3       2       100835  3894      1.03    3.72    0.04    0.04
 4      SDBMHash        3       2       100891  3838      1.04    3.66    0.04    0.04
 5      DJBHash         3       3       100857  3872      1.03    3.70    0.04    0.04
 6      DEKHash         2       64      100793  3936      1.02    3.76    0.04    0.04
 7      BPHash          2       98      100827  3902      1.03    3.73    0.04    0.04
 8      FNVHash         2       80      100809  3920      1.02    3.74    0.04    0.04
 9      APHash          3       3       100821  3908      1.02    3.73    0.04    0.04
10      StpdHash        1800    1       104718  11      363.64    0.01    0.04   56.82
11      ThibHash        200     1       104668  61       65.57    0.06    0.04    3.97


Et j'ai avec le code de thibaut :

Fonction 3 | moyenne : 15 | variance : 8487
Fonction 2 | moyenne : 15 | variance : 15595
Fonction 1 | moyenne : 15 | variance : 23019
Fonction 0 | moyenne : 15 | variance : 1472


Pour la meme liste de 4000 elements
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

95

Y'a un pb. Tu as fait bosser mon code sur une table de quelle taille ? Tu as pris en compte les cases vides ?
tu trouve plus interessant "nbelement/nbcase" ? (ce qui est calculé par thibaut pour la moyenne ? c'est meme pas lié a la fonction de hashage...)

Ouai mais je pense que Pollux et moi on est d'accord sur le fait que la meilleure façon de résoudre la question posée par le topic et dans le contexte du topic, c'est de calculer l'écart type (qu'on a indirectement par la variance, qui permet des comparaisons plus précises étant donné qu'on bosse sur des entiers).
Voici mon raisonnement :

But : On cherche à rendre minimiser le nombre moyen d'itération lors de la recherche linéaire qui fait suite au hachage.

Si on a un algo qui donne un grand écart type, ça signifie que certaines listes chaînées pointées par la table de hachage sont plus longues que d'autres.
Autrement dit, ces listes concentrent un plus grand nombre de mots, et les petites listes concentrent peu de mots.
Encore dit autrement, la probabilité pour qu'un mot choisi au hasard soit situé dans une longue liste est plus grande que la probabilité pour qu'un mot se trouve dans une liste courte.

Avec un algo de hachage qui construit une table peu homogène, le nombre moyen d'itérations pour trouver un mot sera plus élevé qu'avec un algo qui donne une table parfaitement homogène.
Au contraire, avec une table parfaitement homogène, toutes les cases ont la même probabilité de pointer sur la liste contenant le mot recherché. On doit donc chercher à minimiser le nombre moyen d'itérations pour trouver un mot dans tout ce bordel.


Voilà pourquoi mon critère est unique : l'écart type (qui prend en compte les cases vides, puisque celles-ci impliquent le fait que d'autres cases sont trop pleines). La table idéale, donc l'algo idéal, produit un écart type de zéro.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

96

Au contraire, avec une table parfaitement homogène, toutes les cases ont la même probabilité de pointer sur la liste contenant le mot recherché. On minimise donc le nombre moyen d'itérations pour trouver un mot dans tout ce bordel. Avec un algo de hachage qui construit une table peu homogène, le nombre moyen d'itérations pour trouver un mot sera plus élevé qu'avec un algo qui donne une table parfaitement homogène.

C'est exactement a quoi servent les infos que donne les tableaux que j'ai généré...
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

97

Et tu n'es pas d'accord que c'est exactement à quoi sert la seule info donnée par ma moulinette : l'écart type ? (plus il tend vers zéro, plus la table est homogène)
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

98

Ce n'est qu'une info parmis tant d'autre l'ecart type, et l'info est trop general pour savoir quel est exactement le pbm (par ex)
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

99

Oui, là on est d'accord smile

C'est vrai que tes résultats sont intéressants comme je l'ai déjà dit. J'avais pas vu ça comme ça, mais c'est vrai qu'ils indiquent les faiblesses des algos. C'est très utile pour construire un bon algo de manière empirique. Mais j'ai pas le courage et j'ai pas la prétention de faire mieux que DJBHash smile

Mon but c'est de savoir quel algo est le meilleur pour homogénéiser la table, c'est à dire pour égaliser les tailles des listes chainées, donc égaliser les probabilités de trouver un mot dans chaque liste, donc minimiser la probabilité qu'un mot se trouve dans une liste longue, donc minimiser le temps de recherche moyen. L'écart type suffit, non ?

Si vous avez d'autres propositions d'algos pour alimenter le topic, allez-y smile
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

100

Thibaut (./95) :
Y'a un pb. Tu as fait bosser mon code sur une table de quelle taille ? Tu as pris en compte les cases vides ?
J'ai rien dit ! Tu as fait bosser ma moulinette avec HASH_TABLE_SIZE= 256 et on a quasiment les mêmes variances. Y'a pas de pb.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

101

Godzil (./96) :
Au contraire, avec une table parfaitement homogène, toutes les cases ont la même probabilité de pointer sur la liste contenant le mot recherché. On minimise donc le nombre moyen d'itérations pour trouver un mot dans tout ce bordel.Avec un algo de hachage qui construit une table peu homogène, le nombre moyen d'itérations pour trouver un mot sera plus élevé qu'avec un algo qui donne une table parfaitement homogène.

C'est exactement a quoi servent les infos que donne les tableaux que j'ai généré...

Ben non, la seule info vraiment utile dans ton tableau c'est LCL, mais elle ne donne la performance que dans le pire des cas : c'est une mesure intéressante, mais c'est pas forcément représentatif du comportement de l'algorithme dans tous les cas ; généralement, on préfère avoir une idée du cas moyen, i.e. on veut connaître la taille moyenne de chaque case pondérée par le poids relatif qu'elle a (donc en fait c'est le moment d'ordre 2 de la taille des cases, qui est égale à la variance à une constante près).
Thibaut (./95) :
Voilà pourquoi mon critère est unique : l'écart type (qui prend en compte les cases vides, puisque celles-ci impliquent le fait que d'autres cases sont trop pleines). La table idéale, donc l'algo idéal, produit un écart type de zéro.

Un écart type proche de zéro exigerait une adaptation de la fonction de hash aux données qui lui sont fournies ; ce n'est pas le cas d'une "vraie" fonction de hash, qui idéalement donne des cases dont la taille suit une distribution de Poisson... Donc l'écart-type théorique devrait être la racine carrée de la moyenne. On peut savoir si une fonction de hash n'est pas idéale : si son écart-type mesuré est très différent de la racine carrée de la moyenne ^^ (erreur relative très supérieure à 1/sqrt(256))
(par contre tes chiffres pour la variance correspondent pas du tout, tu es sûr que c'est bien la variance que tu calcules ? parce que dans le pire des cas [fonction de hash constante] on peut avoir une variance de 4000^2/256 = 62500, mais certainement pas 230000 ; et puis évidemment même 1472 ça reste bcp pour une fonction de hash correcte)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

102

Ben Godzil a les mêmes que moi smile
C'est quoi la distribution de Poisson ?
Et le moment d'ordre 2 ? (grin dsl)
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

103

c'est normal il a le même programme triso ça veut pas dire que c'est effectivement la variance, il y a sûrement un facteur constant de différence -- essaye d'afficher la table des fréquences, tu verras que ça correspond pas à la variance calculée ^^

et http://en.wikipedia.org/wiki/Poisson_distribution trioui

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

104

Non, je veux dire : dans son programme, il a rajouté le calcul de la variance pour chaque algo et il a trouvé (quasiment) les mêmes variances que moi pour un hash modulo 256.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

105

(n'ayant pas mon cours de stats, j'ai plus ou moins utilisé le meme algo que toi ^^ si ce n'est que je travail sur des doubles et pas des ints)
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

106

Pollux : Pourquoi "triso" ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

107

(bon j'ai pas les sources modifié aec moi la sad) (quoique je vais tenter de passer par le vpn... a voir) je posterais les sources modifié ici
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

108

Thibaut (./104) :
Non, je veux dire : dans son programme, il a rajouté le calcul de la variance pour chaque algo et il a trouvé (quasiment) les mêmes variances que moi pour un hash modulo 256.

ah tiens j'avais lu 230000 et pas 23000, hem dehors
et j'avais pas vu non plus que godz avait rajouté les variances dehors^2
bref, les bonnes fonctions sont bien celles où AVG <~ VAR happy
Thibaut (./106) :
Pollux : Pourquoi "triso" ?

parce que je croyais que tu parlais des résultats qu'il avait eu avec ton programme cheeky

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

109

En fait la liste que j'ai sert a mettre a mal le hasheurs (d'ou peut etre les resultats sur stupidHash) en gros c'est construit sous la forme
for (i=0; i < 4000; i++)
printf("%04d%s%04d", 4000-i, "qqchose" i);

(en gros) mais je vais ajouter la possibilitée d'utiliser un fichier externe pour pouvoir tester avec d'autres sources...
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

110

Bon alors les variances sont correctes d'après toi ?
Et c'est bien elles uniquement qui renseignent sur l'homogénéité de la table ?

Et si j'ai bien compris, si la variance est inférieure à la moyenne, ça veut dire que l'algo est mauvais ?
("On peut savoir si une fonction de hash n'est pas idéale : si son écart-type mesuré est très différent de la racine carrée de la moyenne")
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

111

- oui
- oui
- ben non, ça veut juste dire qu'il est particulièrement bien adapté aux données fournies, mais c'est pas forcément un inconvénient si c'est bien avec ce style de données qu'on va l'utiliser smile (par contre ça veut dire qu'il va être vulnérable face à un attaquant : si par exemple un algorithme réussit à réduire la variance dans le cas d'un dictionnaire en séparant les mots de A-H et de I-Z, en appliquant une fonction de hash à 128 valeurs dans le premier cas et une autre fonction de hash à 128 valeurs dans le second cas, ce qui donne 256 valeurs au total, alors la variance sera 2x moindre mais en contrepartie si on veut indexer seulement le premier tome d'un dictionnaire alors la fonction de hash se comportera très mal [variance de l'ordre de 10x plus élevée])
(cela dit c'est pas parce qu'une fonction a un écart-type très proche de la moyenne qu'elle n'est pas vulnérable non plus, hein ; c'est une condition nécessaire mais pas suffisante)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

112

Bon alors les variances sont correctes d'après toi ?
- oui
Alors l'algo à la con est très bon sur un hash modulo 256 smile Il produit une variance de 62 sur le fichier megamix.txt (6656 mots), face à l'algo DJBHash qui produit une variance de 60. La différence est négligeable alors que le gain en vitesse est intéressant.

Qu'en penses-tu ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

113

que l'algo DjbHash n'est pas fait pour être utilisé mod 256, utilise ./58 à la place ^^

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

114

Utilise APHash wink
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

115

Why ?
Pollux : C'est le même non !?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

116

Pour la fonction donnée par Godzil, il y a écrit PRIME pour le modulo, donc c'est normal que la performance soit pourrie si tu utilises une puissance de 2, qui aux dernière nouvelles n'était forcément pas un nombre premier (sauf 2, qui est une très mauvaise taille pour une table de hachage gni)...

Pour la fonction de Java, voici la version de OpenJDK:
    /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

(https://openjdk.dev.java.net/source/browse/openjdk/jdk/trunk/j2se/src/share/classes/java/lang/String.java?rev=249&view=markup).
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

117

Thibaut (./115) :
Why ?
Pollux : C'est le même non !?

essaye et tu verras tongue comme expliqué dans ./65 ça n'a rien à voir de calculer mod 256 et de calculer mod 257 en essayant d'éviter le cas hash=256 ^^

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

118

(suffit de regarder les tables pour 256 & 257 ^^)

en piqure de rappel :

-------------------------------------------------------------------------------- 
Table size : 256 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR 
 0      RSHash          124     1       32      224      17.86   87.50   15.62  944.67 
 1      PJWHash         201     1       150     106      37.74   41.41   15.62  1207.43 
 2      ELFHash         201     1       150     106      37.74   41.41   15.62  1207.43 
 3      BKDRHash        127     1       81      175      22.86   68.36   15.62  938.22 
 4      SDBMHash        1842    1       159     97       41.24   37.89   15.62  15926.27 
 5      DJBHash         900     2       215     41       97.56   16.02   15.62  8468.13 
 6      DEKHash         220     2       167     89       44.94   34.77   15.62  1112.35 
 7      BPHash          1099    1       234     22      181.82    8.59   15.62  8419.93 
 8      FNVHash         47      1       3       253      15.81   98.83   15.62  188.27 
 9      APHash          24      1       0       256      15.62  100.00   15.62   16.36 
10      StpdHash        1800    1       245     11      363.64    4.30   15.62  23000.37 
11      ThibHash        200     1       195     61       65.57   23.83   15.62  1380.19 
-------------------------------------------------------------------------------- 
Table size : 257 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%       AVG     VAR 
 0      RSHash          24      2       0       257      15.56  100.00   15.56   10.40 
 1      PJWHash         175     1       40      217      18.43   84.44   15.56  572.92 
 2      ELFHash         175     1       40      217      18.43   84.44   15.56  572.92 
 3      BKDRHash        25      1       0       257      15.56  100.00   15.56   16.60 
 4      SDBMHash        28      1       0       257      15.56  100.00   15.56   23.80 
 5      DJBHash         22      1       0       257      15.56  100.00   15.56    5.56 
 6      DEKHash         39      1       0       257      15.56  100.00   15.56   41.10 
 7      BPHash          50      7       69      188      21.28   73.15   15.56  198.57 
 8      FNVHash         32      1       0       257      15.56  100.00   15.56   16.42 
 9      APHash          28      1       0       257      15.56  100.00   15.56   15.69 
10      StpdHash        1800    1       246     11      363.64    4.28   15.56  22911.82 
11      ThibHash        200     1       196     61       65.57   23.74   15.56  1375.76 


(d'ailleurs, c'est tres marrant a un ou deux exception tous sauf StupidHash et ThibHash sont bcp plus efficace en 257 que 256 ^^) Il ny a que APHash ui a l'air de pratiquement toujours bien s'en sortir, mais il a l'air assez lourd a mettre en oeuvre...

Je teste ça ici, et je posterais demain, je vais faire quelque test de rapidité pour chaques methodes de hash...
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

119

Godzil (./118) :
d'ailleurs, c'est tres marrant a un ou deux exception tous sauf StupidHash et ThibHash sont bcp plus efficace en 257 que 256
Je crois que c'est normal. J'ai cru comprendre sur wikipedia que les algos de hachage produisent des tables beaucoup plus équilibrées quand leur dimension est un nombre premier. D'où la recommandation que Pollux me fait je pense.

Pollux: OK smile Seulement, est-ce que le temps perdu dans la division par 257 justifie le gain de variance que cela apporte ?
Je vais comparer l'algo modulo 256 avec l'algo modulo 257 sur 6656 mots pour voir le gain d'homogénéité.

A ce propos, y'a un truc qui me surpend, c'est la variance énorme qu'obtient Godzil pour les modulos 256. Il faudrait voir sur une "vraie" liste de mots s'il en est de même (il a dit que sa moulinette est prévue pour vraiment faire cracher leurs tripes aux algos, chose qui ne correspond pas à la pratique smile)
Sur la grande liste de mots anglais megamix.txt, on obtient une variance de 60, au lieu de 8468 pour sa liste extrémiste ! (papa t'a jamais dit que l'extrémisme c'est pas bien ??)
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

120

Pollux (./55) :
euh la façon dont tu utilises hach_wkp est loin d'être optimale, puisque tu calcules modulo une puissance de 2 ; le mieux serait soit de calculer modulo 257, soit si la qualité de hachage actuelle te suffit d'optimiser cette fonction en une fonction plus rapide qui renvoie le même résultat :(...)
Est-ce que je peux combiner tes deux propositions ? (algo optimisé en vitesse & modulo 257), ce qui nous donne ça :
int hach_wkp_pollux_257(const char *str)
{
    unsigned int hash = 5381; // DJB Hash
    unsigned int hash5 = 0;
    const char *s;

    for (s = str; *s; s++) {
        hash5+= hash;
        hash+= *s;
    }
    hash= hash + (hash5<<5);

    while (hash % 257 == 256)
        hash/= 257;

    return (hash % 257);
}

?

(je pose la question car j'avoue que je n'ai pas compris ton optimisation, pour moi la raison qui fait que l'algo de départ et ta version optimisée sont équivalentes reste obscure)
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.