30

nan mais on ne met que les branches de l'arbre qui mènent effectivement à un mot... Et on rajoute ces branches au fur et à mesure qu'on ajoute des mots dans la base
Les droits inaliénables du troll :
1) le droit d'avoir raison
2) le droit d'être péremptoire
3) le droit de ne pas lire
4) le droit de ne pas répondre
5) le droit d'être de mauvaise foi
6) Autant pour moi / Faignant / Vivent Tintin et Milou

31

Oui, mais au bout de 10240 mots (par exemple) de 5 lettres en moyenne, l'arbre doit être assez monstrueux. Imagine si on ne place que ces 3 mots de 3 lettres : abc, xyy, uvw.

On a la racine : 256*4 octets
Puis, pour la lettre a, on crée un noeud afin d'y placer le b : 256*4 octets
Puis, on y crée un neud, relié au b, pour y placer le c : 256*4 octets
Pour chaque mot on retrouve cette situation. Résultat : 3x3x256x4= 9 ko.

9 ko pour 3 pauvres mots, c'est pas super smile Et comme le but du topic c'est de retrouver rapidement un mot dans un grand nombre de mots (1000 ?), qui feraient 5 lettres en moyenne, c'est même pas la peine... à moins que la TI89 ait quelques millions de Go cachés quelque part smile

J'ai repensé tout à l'heure à ce que disait onur dans le post ./13. C'est vrai qu'on pourrait réfléchir à une méthode de hachage qui tiendrait compte des lettres les plus utilisées.

Les lettres les plus utilisées, lorsqu'elles sont rencontrées, modifieraient beaucoup la valeur du hash, afin de disperser (répartir) le plus possible dans la table les mots qui les contiennent (car ils sont le plus nombreux).
Les lettres les moins utilisées auraient par conte un effet de "concentration" du hash, car les mots les contenant sont moins nombreux.

Je ne sais pas si c'est judicieux, et surtout je ne sais pas (encore) comment on pourrait concrétiser cette belle théorie.
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.

32

Mais non l'arbre est comme ça, pour trois mots abc, xyy et uvw :

       / a - b - c
Racine - x - y - y
       \ u - v - w

Il ne prend aucune place. Enfin ok, ça dépend comment tu stockes tes affaires, si tu mets des slots vides pour les branches qui n'existent pas...



Au bout de 10240 mots, l'arbre a 10240 feuilles. Et au maximum 5*10240 nœuds (si les mots font cinq lettres) ; probablement moins.
Les droits inaliénables du troll :
1) le droit d'avoir raison
2) le droit d'être péremptoire
3) le droit de ne pas lire
4) le droit de ne pas répondre
5) le droit d'être de mauvaise foi
6) Autant pour moi / Faignant / Vivent Tintin et Milou

33

Thibaut (./31) :
Imagine si on ne place que ces 3 mots de 3 lettres : abc, xyy, uvw.

On a la racine : 256*4 octets
Puis, pour la lettre a, on crée un noeud afin d'y placer le b : 256*4 octets
Puis, on y crée un neud, relié au b, pour y placer le c : 256*4 octets Pour chaque mot on retrouve cette situation. Résultat : 3x3x256x4= 9 ko.

- à la racine : a, x, u => 3 cases
- profondeur 1 : a=>b, x=>y, u=>v => 3 cases
- profondeur 2 : ab=>c, xy=>y, uv=>w => 3 cases
=> 3*3 = 9 cases
9*4 = 36 octets ?

En gros, en ne stockant que ce dont tu as besoin, et non toutes les possibilités imaginables.

en dépliant l'algo, ça donnerait, étape par étape, quelque chose de ce genre (implémentation très naïve ^^) :
$tree = array();

// abc
$tree['a'] = array();
$tree['a']['b'] = array();
$tree['a']['b']['c'] = array();

// xyy
$tree['x'] = array();
$tree['x']['y'] = array();
$tree['x']['y']['y'] = array();

// xsd
$tree['x']['s'] = array();
$tree['x']['s']['d'] = array();

// uvw
$tree['u'] = array();
$tree['u']['v'] = array();
$tree['u']['v']['w'] = array();


soit un arbre en sortie qui ressemble à ça :
array
  'a' => 
    array
      'b' => 
        array
          'c' => 
            array
              empty
  'x' => 
    array
      'y' => 
        array
          'y' => 
            array
              empty
      's' => 
        array
          'd' => 
            array
              empty
  'u' => 
    array
      'v' => 
        array
          'w' => 
            array
              empty
avatar
Tutorial C (TI-89/92+/v200) - Articles Développement Web (PHP, Javascript, ...)
« What is the sound of Perl? Is it not the sound of a wall that people have stopped banging their heads against? » - Larry Wall

34

OK. Après, faut voir comment on implémente ça. Si on veut créer les noeuds que lorsqu'un mot correspondant existe, il faut alors les structurer sous forme de liste chainée. On aurait alors une recherche en O(n) combinée à une recherche linéraire.
Est-ce vraiment avantageux par rapport à un hachage suivi d'une recherche linéaire ?
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.

35

(cross combo x2)

Thibaut> Certes la structure est plus lourde qu'une table de hachage mais c'est optimisable.

Par exemple, j'ai mis des tableaux de 256 mais si tu utilise des identificateurs sans casse tu peux te restreindre à [a-z_0-9] soit 37 caractères et diminuer la consommation. Tu peux aussi utiliser une liste au lieu d'un tableau et là tu as la situation décrite par Hippo (mais tu as des perfs moins bonnes).

Ensuite, tu prends un mauvais exemple en te limitant à 3 chaînes car plus tu as de chaînes plus tu as de partage et donc la conso par chaîne diminue avec le nombre. Une idée aussi c'est de limiter la hauteur de l'arbre en remplaçant les feuilles par des tables de hachage sur la fin de la clef à partir d'une certaine hauteur, tu auras donc un morceau de dico ayant en fait une consommation raisonnable puisque très partagé et tu allègeras le temps dans les sous tables de hachage car elles seront moins surchargées. Bien sûr c'est plus dur à coder.

Ah, au fait, si tu veux stocker 10240 clefs de 5 caractères dans une table de hachage tu as par élément : la clef, un pointeur vers cette clef, un pointeur vers la valeur et un pointeur vers l'élément suivant, soit 10240x(6+4+4+4) = ~180k ce qui est déjà mort sur Ti grin.
avatar
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

36

ben déjà il faudrait avoir plus d'infos sur le pb : est-ce qu'on peut ajouter/modifier/enlever des éléments ?

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

37

Ah oui c'est vrai que si on a tous les mots au départ y'a d'autres pistes, mais s'il a décidé d'utiliser une table de hachage je suppose que c'est pour une utilisation dynamique...
avatar
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

38

Même pour une utilisation dynamique ça peut être potable, par exemple dans xpack y a une table de hachage pour retrouver où était telle paire d'octet smile (le nb d'entrées est borné par la taille de la fenêtre de compression donc ça simplifie les choses, mais on peut aussi se débrouiller dans le cas général)

Ah et puis ça c'est faux :
BookeldOr (./35) :
Ah, au fait, si tu veux stocker 10240 clefs de 5 caractères dans une table de hachage tu as par élément : la clef, un pointeur vers cette clef, un pointeur vers la valeur et un pointeur vers l'élément suivant, soit 10240x(6+4+4+4) = ~180k ce qui est déjà mort sur Ti grin.

Déjà y a pas forcément besoin de pointeurs vers la clé ni vers la valeur, et ensuite on peut éviter le pointeur vers l'élément suivant en stockant dans la valeur de hash suivante jusqu'à ce qu'on trouve une case libre (c'est ce que fait xpack, qui a des clés et des valeurs de 2 octets donc un pointeur doublerait la taille grin), donc déjà 10240x6 = 60k [+ de la marge pour que ça reste performant + l'éventuelle mémoire pour les valeurs] c'est plus raisonnable happy

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

39

Merci pour tes précisions BookeldOr, j'y vois beaucoup plus clair smile
Pollux : On dit qu'on n'a pas besoin de retirer les éléments.
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.

40

Pollux (./38) :
Déjà y a pas forcément besoin de pointeurs vers la clé ni vers la valeur, et ensuite on peut éviter le pointeur vers l'élément suivant en stockant dans la valeur de hash suivante jusqu'à ce qu'on trouve une case libre (c'est ce que fait xpack, qui a des clés et des valeurs de 2 octets donc un pointeur doublerait la taille biggrin.gif ), donc déjà 10240x6 = 60k [ de la marge pour que ça reste performant l'éventuelle mémoire pour les valeurs] c'est plus raisonnable smile2.gif


Mais si ta table est mal dimmentionné, des qu'elle est pleine c'est fini tu peut plus ajouter d'élements, alors qu'une table de hashage chainé, meme si c'est un poil moins efficace, le nombre d'élement est "infini")
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.

41

Voilà, ma moulinette est terminée... Je base mon classement sur les écarts types qu'elle a calculés :


La fonction de Godzil (./5) et la mienne (./25) donnent des résultats horribles (la table de hachage obtenue n'est pas du tout homogène).

La fonction de wikipedia semble très très bonne (./9) smile

La meilleure, de peu, semble être la fonction le hachage la plus simple qu'on puisse inventer :
int hash_toutcon(const char *string)
{
    unsigned int result;

    result= 0;

    do {
        result+= *string;
    } while (*string++ != 0);

    return (result % 256);
}

cheeky

Je fais d'autres tests et je vous tiens au courant.
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.

42

43

C'est fascinant smile C'est la fonction la plus simple et la plus rapide de toutes qui donnerait le meilleur résultat !

(c'est à confirmer, car il y a un petit bug dans ma moulinette, mais il devrait changer très peu les résultats quand j'aurai trouvé son origine, étant donné que la proportion de mots qu'il affecte reste négligeable et que toutes les fonctions testées sont logées sous son enseigne)
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.

44

Oui mais elle a un désavantage énorme : deux mots avec les mêmes lettres dans un ordre différent sont en collision... (enfin ça dépend ce que tu veux faire avec...)
Les droits inaliénables du troll :
1) le droit d'avoir raison
2) le droit d'être péremptoire
3) le droit de ne pas lire
4) le droit de ne pas répondre
5) le droit d'être de mauvaise foi
6) Autant pour moi / Faignant / Vivent Tintin et Milou

45

Hippo : oui mais en pratique ça arrive très peu souvent les anagrammes. Les fichiers de texte en anglais qui sont dans l'archive de la moulinette et avec lesquels tu peux la faire bosser, qui sont donc des cas pratiques, donnent cette fonction gagnante.
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.

46

Voilà, le bug est corrigé ! C'était un oubli débile de ma part. Source : topics/103443-efficacite-dun-algorithme-de-hachage-de-chaines-de-caracteres#0
Sa correction ne change pas le classement.


Par contre, l'efficacité des algos est mieux discernée :

4) On s'aperçoit que la pire fonction est celle de Godzil (./5) (bizarre quand même)
3) Après, bien meilleure mais pas la meilleure, arrive la mienne (./25)
2) Puis, largement devant, arrive celle de wikipedia (./9)
1) Et enfin, la gagnante, c'est la fonction de hash toute con (./41)
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.

47

je pense que celle de godzil a un bug, val et tmp devraient être unsigned (et puis je vois pas l'intérêt du test de signe à la fin si la fonction marchait correctement confus par contre quand elle marche pas correctement elle renvoie 0 pour la moitié des mots de plus de 6 caractères, c'est un peu con grin)

note aussi que tu compares des fonctions case-sensitive à des fonctions case-insensitive, c'est pas une très bonne idée ^^

Godzil (./40) :
Mais si ta table est mal dimmentionné, des qu'elle est pleine c'est fini tu peut plus ajouter d'élements, alors qu'une table de hashage chainé, meme si c'est un poil moins efficace, le nombre d'élement est "infini")

Si si c'est possible du moment qu'elle est pas trop fragmentée, il suffit juste de faire un petit scan en O(n+(n_utilisées-n_chaînes)*temps_de_hachage) où n_utilisées est le nb de cellules utilisées et n_chaînes est le nb de groupes de cellules consécutives utilisées ^^ (donc pour peu qu'on utilise un realloc() lent comme celui d'ams ça ralentira pas forcément bcp)

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

48

note aussi que tu compares des fonctions case-sensitive à des fonctions case-insensitive, c'est pas une très bonne idée ^^
Note que la seule fonction insensible à la casse, c'est celle de wikipedia. L'algo est peut-être conçu pour ne donner de bons résultats que pour *s compris entre certaines bornes (d'où le lowchar).

Dans tous les cas, cette fonction donne un excellent résultat telle qu'elle est.
Si l'on rendait les autres fonctions insensibles à la casse, leur résultat empirerait (puisque l'ensemble de valeurs possibles pour *s diminuerait).

Pour la fonction de Godzil, si vous voulez la corriger et refaire les tests, à vous l'honneur smile Moi j'ai eu une réponse à ma question, je sais maintenant ce que je vais choisir dans tout ce binz de fonctions.

Au fait PpHd, peux-tu nous passer une implémentation de ta fonction ? J'aimerais bien tester son efficacité.
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.

49

Voilà, j'ai viré le tolower de la fonction de wikipedia. Elle arrive maintenant légèrement devant la fonction à la con.
Bizarre ce tolower quand même. Why it ? Porque ?
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.

50

t'as regardé la jvm?

au moins dans classpath:
http://www.google.fr/codesearch?hl=fr&q=+classpath+String.java+show:UBWIvy4f1Ws:7dr-BbDnUfg:evllEXD0CUw&sa=N&cd=4&ct=rc&cs_p=ftp://ftp.gnu.org/gnu/classpath/classpath-0.92-generics.tar.gz&cs_f=classpath-0.92-generics/java/lang/String.java#first
 /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

51

Pollux (./47) :
je pense que celle de godzil a un bug, val et tmp devraient être unsigned (et puis je vois pas l'intérêt du test de signe à la fin si la fonction marchait correctement confus.gif par contre quand elle marche pas correctement elle renvoie 0 pour la moitié des mots de plus de 6 caractères, c'est un peu con biggrin.gif )


C'est pas le code original, (copie main papier->clavier) et je sais plus pourquoi, c'est moi qui avait ajouté le test a la fin.. Et les tests que j'avais fait donnais pourtant de bon resultat mais bon grin

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.

52

squalyl (./50) :
t'as regardé la jvm?au moins dans classpath

Voilà, c'est testé smile Très bon résultat aussi ! Elle semble aussi efficace que la fonction de wikipedia sans tolower. C'est pas étonnant, car ce sont... les mêmes ! à un facteur près : l'une multiplie par 33, l'autre par 31.

Finalement je vais adopter une de celles-là ? Je sais pas trop... la fonction-à-la-con est à peine moins bonne et est beaucoup plus rapide.
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.

53

[edit du ./52] c'est par 33 que la fonction de wikipedia multiplie, pas par 32.

PS : Hippo, tu avais raison, c'est sans doute le fait que la fonction-à-là-con donne le même hash pour des anagrammes qui fait qu'elle est un peu moins bonne (entre autres).
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.

54

tu pourrais nous coller des résultats? non paske tout le monde peut pas l'exécuter là grin

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 :
int hach_wkp(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;
        }
        return (hash + hash5<<5) & 0xFF;
}

(tu peux même essayer avec d'autres valeurs que 5)

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

56

Ben je vais pas changer le modulo de la fonction de wikipedia, sinon elle serait plus comparable aux autres wink
Je vais essayer ta fonction pour vérifier qu'elle renvoie le même résultat que l'originale quelle que soit la chaîne. [edit] en effet.

squalyl : y'a les sources, totalement indépendantes de la plateforme, dans le zip 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.

57

En fait je suis en train de douter de ton test :

http://www.cse.yorku.ca/~oz/hash.html
lose lose
This hash function appeared in K&R (1st ed) but at least the reader was warned: "This is not the best possible algorithm, but it has the merit of extreme simplicity." This is an understatement; It is a terrible hashing algorithm, and it could have been much better without sacrificing its "extreme simplicity." [see the second edition!] Many C programmers use this function without actually testing it, or checking something like Knuth's Sorting and Searching, so it stuck. It is now found mixed with otherwise respectable code, eg. cnews. sigh. [see also: tpop]

unsigned long
hash(unsigned char *str)
{
unsigned int hash = 0;
int c;

while (c = *str++)
hash += c;

return hash;
}


Et puis tu fait un test sur UNE taille de table. Il faudrais le faire sur plusierus tailles..
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.

58

Thibaut (./56) :
Ben je vais pas changer le modulo de la fonction de wikipedia, sinon elle serait plus comparable aux autres wink

si si :
int hach_wkp(const char *str)
{
        unsigned int hash = 5381; // DJB Hash
        const char *s;
        for (s = str; *s; s++) {
                hash = ((hash << 5) + hash) + *s;
        }
        while (hash%257==256)
                hash /= 257;
        return hash%257;
}

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

59

D'ailleurs la fonction originale c'est celle la :
unsigned long
    hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;

        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return 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.

60

godzil ./57 : En virant le tolower de la fonction de wikipedia (mais qu'est-ce qu'il foutait là ce truc ?) la fonction à la con a perdu sa première place.
Mais il faut garder à l'esprit que je classe les fonctions selon les variances calculées sur les différentes tables. C'est un raccourci, une valeur qui résume toute une table, c'est un peu limite... Dans le détail, il y a peut-être de grandes différences entre les 2 fonctions gagnantes ? (fonction wikipedia et fonction à la con)

godzil ./59 : Ben c'est celle de wikipedia.

Pollux : Puisque la boucle précédent le return donnera toujours un hach inférieur à 256, on peut faire return hash%256 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.