Discussion :

[bollo]

J'ai vu le sujet test sur un tableau.

Je voudrais faire un tel test sur un hashage, j'ai donc essayé ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
my %leNouveauHash=(
'AT2G21600' => '005794',
'AT2G39940' => '009867',
'AT3G13320' => '009705',
'AT4G17090' => '016161',
'AT5G50920' => '009570',
'AT4G02780' => '009507',
'AT2G37170' => '005886');
 
my $nbr = %leNouveauHash; 
print	"nombre d'elements : ".$nbr."\n";

la console me repond :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
nombre d'elements : 6/8

Ma question : mais pourquoi ? Qu'est ce que ca veut dire ?

[2Eurocents]

Je voudrais faire un tel test sur un hashage, j'ai donc essayé ça :
...

la console me repond :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
nombre d'elements : 6/8

Ma question : mais pourquoi ? Qu'est ce que ca veut dire ?

Cela veut dire qu'un hachage de retourne pas son nombre d'éléments lors de son évaluation en contexte scalaire. Il retourne "autre chose" qui est plus en rapport avec la fonction de hachage, pour ce que j'en connais.

Tu remarqueras que ce "autre chose" croit par palliers lors de l'ajout d'éléments dans le hachage. Le dénominateur reste constant pendant plusieurs ajouts, puis augmente sur un ajout donné, puis reste constant, etc.

Pour connaître le nombre d'éléments d'un hachage, il vaut mieux compter les clefs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

my $nbr = keys (%leNouveauHash);

Bon Perl.

[bollo]

Pour connaître le nombre d'éléments d'un hachage, il vaut mieux compter les clefs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

my $nbr = keys (%leNouveauHash);

Bon Perl.

Surprenant !

C'est une philosophie totalement différente de java, moi qui cherchais une méthode qui s'appliquait à mon hashage et qui retournerait sa taille (comme par exemple size.%leNouveauHash ou length.%leNouveauHash)

merci.

[Jedai]

Le "6/8" signifie qu'il y a 6 emplacements occupés, dans un hash de 8 emplacements. Pour comprendre ça, il faut comprendre comment fonctionne la structure de données : une table de hashage est en fait un bête tableau, dont le fonctionnement est assuré par ce qu'on appelle une fonction de hashage. Une fonction de hashage prend en argument une chaîne de caractère et retourne un nombre. Lorsqu'on stocke un élément dans une table de hashage, la fonction de hashage est appliqué à la clé, et renvoie un nombre N, on stocke alors la valeur à l'index N dans le tableau. Lorsqu'on veut récupérer la valeur, on fournit la clé à la fonction de hashage, qui redonne le même nombre N que la première fois, et on peut extraire directement la valeur à la Nème place du tableau.
Evidemment, il y a un petit problème : l'ensemble des clé est potentiellement infini, et notre tableau est fini, donc il y a un risque de collisions : deux clés peuvent donner le même nombre. Dans ce cas, il y a plusieurs solutions, l'une étant de stocker la nouvelle valeur dans l'emplacement libre suivant, et de marquer son emplacement normal pour indiquer où on l'a vraiment mis. Une autre solution fréquemment adopté (je crois que Perl fait comme ça) est de stocker dans les emplacements du tableau non pas la valeur directement, mais plutôt une liste chaînée de couple clé/valeur.
Bien sûr, le tableau de la table de hashage ne doit être ni trop grand (on gâche de la place), ni trop petit (trop de collisions : ralentissement important de la structure)... A priori, Perl fonctionne par puissance de 2, ses hashs font d'abord 4 emplacements, puis 8, 16,... Un peu comme lorsqu'on doit mettre au point un tableau extensible (multiplier par deux la taille lorsqu'il n'y a plus de place permet d'obtenir une complexité d'insertion amortie constante).

La fonction de hashage doît avoir certaines caractéristiques pour provoquer un minimum de collisions, et au jour d'aujourd'hui, il vaut mieux s'en remettre à une fonction générique mise au point par des professionnels (comme celle de Perl bien sûr).


(Par ailleurs ce concept n'est pas vraiment limité au chaîne de caractère pour les clés, on peut utiliser n'importe quel type de donnée, même si Perl ne propose que les string par défaut, mais c'est le cas le plus courant, et on peut toujours s'y ramener)

(NB : on peut préallouer une table de hashage si on a une idée du nombre d'élément qu'on va y mettre, cela épargne à Perl d'effectuer des redimensionnements inutiles. Pour ce faire, on utilise cet idiôme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

keys %mon_hash = $nombre_d_element_maximum;

Et Perl alloue automatiquement un tableau de taille égale à la puissance de 2 immédiatement supérieure )

--
Jedaï

[2Eurocents]

Le "6/8" signifie qu'il y a 6 emplacements occupés, dans un hash de 8 emplacements.

C'est aussi ce que je croyais jusqu'à ce que je teste ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

perl -e '%h=(a=>1, b=>2, c=>3, d=>4, e=>6, f=>5, g=>6, h=>1, m=>5, k=>3, l=>12, p=>5);$n=%h;print "$n\n";'

Il y a bien 12 clés dans le hachage, mais la valeur retournée est 8/16.

C'est pour cela que je qualifiait d' "autre chose" le retour de l'évaluation en scalaire du hachage.

Je souscris en tous point à l'explication de Jedaï sur la taille du "tableau" exprimée au dénominateur, mais la première valeur ne correspond pas directement au nombre d'emplacements occupés.

[Jedai]

Si justement, relis mon explication : le fait qu'il y ait un nombre d'emplacements occupés inférieur au nombre d'éléments stockés est dû aux collisions dans le hash. Note d'ailleurs que cela est déjà apparent dans l'exemple de bollo puisqu'il stocke 7 éléments et a un retour de 6/8.
(par ailleurs, vérification faite, le hash minimum fait 8 emplacements)

--
Jedaï

[Jedai]

Par ailleurs, si vous êtes curieux, vous pouvez utiliser Devel:eek pour obtenir plus de renseignement sur vos hashs.
Entre autre il donne une information assez intéressante qui est le nombre de listes chaînées d'une profondeur donnée dans le hash. On constate que l'algorithme se comporte très bien et que les chaînes restent courtes.

--
Jedaï

[2Eurocents]

Si justement, relis mon explication

Merci de me mettre les points sur les i. Je n'avais pas envisagé toutes les conséquences de ton explication.

C'est bien plus clair, maintenant (avec un peu de chance, ça va faire baisser mon score au "test de pureté Perl", parce que pour le moment, avec mes 97%, je suis un peu juste )