Discussion :

[Zwiter]

Bonjour,
Pourriez vous me confirmer que par définition, une table de hashage génère de la collision ?
Je reprends un code qui génère une collision avec String.hashCode()
Merci
Z.

[Nico02]

Oui les tables de hachages génèrent des collisions. Il y a plusieurs moyen de les gérer.

Cdt.

[Zwiter]

Je pense que je vais bypasser la table de hash. Moins rapide et plus gorumand en mémoire, mais moins de code a re-écrire.
merci encore
Z.

[thelvin]

On rappellera que HashSet et HashMap sont parfaitement au courant de l'existence des collisions et les gèrent très bien, sans qu'on ait besoin de faire quoi que ce soit.

Les tables de hachage c'est typiquement le genre de trucs qu'on apprend à l'école pour comprendre que c'est pas de la magie, puis qu'on a plus jamais besoin de toucher parce que l'ordi fait ça à notre place.

[Zwiter]

thelvin : Le programme que je relis utilise java.lang.String.hashCode(). Tu essais de me dire que Java a une fonction qui entre en jeu lors des collisions ? En tout cas, elle ne fonctionne pas dans mon programme, a moins que le concepteur ai oublié la partie sensée gérer ces rares cas.
Merci
Z.

[thelvin]

Il s'en sert comment de String.hashCode() ?
Pourquoi est-ce qu'il l'appelle lui-même au lieu de juste utiliser un HashSet ou un HashMap qui n'ont aucun problème avec les collisions ?

Je sais bien que dans des cas très spécialisés ça peut arriver d'en avoir besoin. Mais il faut toujours en douter a priori.

[Zwiter]

il construit un string, puis le passe a hashCode :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
	private static StringBuilder hashString = new StringBuilder();
	private static final String fmt = "%02x";
	public int hashCode(){
		if(!sorted()) sortData();
 
		hashString.setLength(0);
		hashString.append(String.format(fmt, getDataLong(dndGlobals.mom, dndGlobals.A)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.dad, dndGlobals.A)));		
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o1, dndGlobals.A)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o2, dndGlobals.A)));
 
		hashString.append(String.format(fmt, getDataLong(dndGlobals.mom, dndGlobals.C)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.dad, dndGlobals.C)));		
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o1, dndGlobals.C)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o2, dndGlobals.C)));
 
		hashString.append(String.format(fmt, getDataLong(dndGlobals.mom, dndGlobals.G)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.dad, dndGlobals.G)));		
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o1, dndGlobals.G)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o2, dndGlobals.G)));
 
		hashString.append(String.format(fmt, getDataLong(dndGlobals.mom, dndGlobals.T)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.dad, dndGlobals.T)));		
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o1, dndGlobals.T)));
		hashString.append(String.format(fmt, getDataLong(dndGlobals.o2, dndGlobals.T)));
 
		return hashString.toString().hashCode();

Et la dessus, eclipse me dit que hashCode provient de String.hashCode()

[tchize_]

Bon, d'abord ça doit être l'implémentation la moins performante que j'ai vu de ma carrière de la méthode hashcode.
Ensuite, c'est une méthode hashcode qui a des effets de bord, ce n'est pas bon du tout (cf le sort datas)


Enfin, la question n'est pas comment tu génère ton hashCode, tu pourrais même faire un return -1 que ça ne changerais pas grand chose, mais à quoi tu l'utilise derrière!

Normalement, ce n'est jamais un problème que deux objets différents retournent le même hashcode. C'est même impossible à éviter. Un hashcode faire 32 bits, un objet stocke en général plus de 32 bits de données diverse intervenant dans le hashcode. Si t'arrive à faire tenir ça de manière unique dans 32 bits, félicitations, tu viens d'inventer un algorithme de compression révolutionnaire

On doit juste éviter que la fréquence des collisions soit trop élevée sous peine de grever les performance des HashMap et compagnie

Donc oui, les collisions existe, oui c'est normal, non tu n'a rien à faire pour les éviter en temps normal.

[tchize_]

et tiens, voilà un exemple d'implémentation correct de hashcode:

Code :

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

1
2
3
4
5
6
7
8
 
    final long prime = 31;
    long result = 1;
 
    for (int i : new int[]{dndGlobals.A,dndGlobals.C,dndGlobals.G,dndGlobals.T})
         for (int j : new int[]{dndGlobals.mom,dndGlobals.dad,dndGlobals.o1,dndGlobals.o2})
		result = prime * result + getDataLong(i,j);
    return (int)(result ^ (result >>32));

[Jimmy_]

Vous voulez éviter les collisions ?

Les algo de hashage cryptographique sont là pour ça , même si c'est pas garantie à 100% , les chances sont minces, voir très mince ...

[Zwiter]

Merci tchize_ pour tes commentaires. J'arrive aux même conclusions après avoir lus plusieurs articles sur la toile. Malheureusement, il me faut éviter les collisions. D'après moi, un entier est suffisant pour indexer tous les cas car il sera impossible d'avoir plus que 3 milliard de possibilités (la taille du génome humain).
Je comprends d'après le code non commenté (soupir...) que le hashCode sert uniquement a réduire le jeux de données en retirant les doublons
Je pense réécrire hashCode() en utilisant un index que j'incrémenterai au fur et a mesure. Il me faudra garder une table de correspondance qui prendra beaucoup de mémoire, pour gérer les doublons.
D'un autre coté, pourquoi garder un hashcode alors que je crois que les données A, C, G et T sont aussi conservées pour la phase suivante du programme... Je vais creuser cette voie la et voir si c'est faisable sans re-coder le programme au complet.

Merci de votre aide a tous. Je comprends mieux les hash !

[tchize_]

Malheureusement, il me faut éviter les collisions. D'après moi, un entier est suffisant pour indexer tous les cas car il sera impossible d'avoir plus que 3 milliard de possibilités (la taille du génome humain).

Vu que la population mondial est de 7 milliards d'individu, tu sous entendrais que j'ai un vrai jumeau quelque part.....


Je que tu te trompe dans tes calcul. Il y a 3 milliards de paires de base dans un génome humain. Ca faut 4 exposant 3 milliards de combinaisons possibles



Si tu suppose raisonnablement que chaque humain est unique (même les vrais jumeaux n'ont pas exactement le même génome, mutations spontanées etc jouant), il te faudrait au moins 7 milliards de combinaisons pour ne pas avoir de collision.....

Il me faudra garder une table de correspondance qui prendra beaucoup de mémoire, pour gérer les doublons.

Et tu la gère comment cette table? La seule structure d'association clé valeur performante sur de nombreuses données, c'est, autant que je sache, les tables de hashage pour lesquelles.... tu as besoin de calculer un hash


Faut voir (mais tu l'as toujours pas dit) comment tu gère tes hash. Normalement, le principe du hash est "si les hash sont identiques, alors on commence à comparer le contenu des données, ce qui est plus lent que juste le hash". On utilise les hash comme ça:

Code :

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

1
2
3
4
5
6
public boolean equals(Adn other){
   if (other.hashCode()==this.hashCode())
       // vérifier tout le contenu
   else
       return false;
}

[Zwiter]

tu aurais raison si je voulais faire tenir la population mondial dans un tableau. Mais je n'ai que 3 individues a chaque run du programme, et chaque run est indépendant. De plus, le but du hash est de rassembler sous un meme id des cas similaires de couverture des bases a une position données :
ex : chromosome 1 position 123456:
mere : 20 A, 0 C, 0 G, 0 T
pere : 18 A, 0 C, 0 G, 0 T
mere : 22 A, 0 C, 0 G, 0 T

Si au chromosome 5 position 456789, j'ai la meme répartition : je rassemble les 2 pour faire mes calculs. J'economise le temps d'un calcul. Mais je garde quelque part l'information : ce hash correspond a la position chromosome 1 position 123456 et chromosome 5 position 456789 afin d'attribué la valeur calculé aux 2 positions. Je ne suis intéressé que par les positions ayant une valeur très élevée.

Ceci me permet de reduire par 200 le nombre de cas. Le calcul dure environ 2 heures (sur mes jeux de tests. plus de 5 jours sur les vrais données) donc le gain est très appréciable.

En terme de performance : le programme passe plus de temps a calculer que a compiler les données avant le calcul. Le hash étant un entier, si je reste avec un entier je n'ai pas besoin de répercuter ma transformation dans le reste du code.

N'hesite pas a critiquer mon résonnement, ca me permet d'avancer !
Si tu ne comprends pas ce que je veux faire, demande moi je me ferai un plaisir de decrire plus longuement le but du programme, et les données traiter.

merci du temps que tu m'accordes. J'apprecie beaucoup.
Z.

[tchize_]

Ok, c'est déjà plus clair. Je peux te proposer alors une solution simple si ton but et de calculer combien de chaque paire tu as à un endroit (donc en fait résumer l'information), et à supposer qu'il n'y a jamais plus de 255 paires de chaque type dans ton calcul. Tu peux faire ceci:


soient nA,nC,nG,nT le compte de chaque paire de base


int hash = nA&0xFF | ((nC&0xFF)<<8) | ((nG&0xFF)<<16) | ((nC&0xFF)<<32)


Si tu dois stocker o1, o2, mom et dad, comme dans ton exemple précédent, il n'y a pas le choix, il faudra passer par une paire de long pour garantir l'absence de collision.

[Zwiter]

Merci de tes idées, mais c'est aussi une partie du probleme : le séquencage n'est pas uniforme sur tout le génome : il peut y avoir des positions avec plus de 10k pour une base.

QUestion stupide : penses tu que ce que je propose de faire (un id incrémenté a chaque nouvelle combinaisons des [3 individu X 4 nucléotides]) ne soit pas viable ?

Merci encore une fois !
Z.

[tchize_]

La question c'est, si tu travaille avec un ID par combinaison, quelles seront tes performances? Il y aura combien de combinaison de codes? En plus de la mémoire qui risque d'être occupée par ta table d'Ids, il y aura le problème de son temps d'accès pour y trouver un élément!

Difficile à dire tant qu'on ne sait pas à quoi vont servir ces ids après!

[Zwiter]

voici les etpaes du pogramme :
1) preparation des données. Grace au hashcode les combinaisons uniques sont identifiées et ecrites dans un fichier 'compressé'. Un autre fichier décompressé associe chaque position du genome (et non chaque combinaison) a l'id correspondant a sa combinaison. Ainsi il y a 2 fichiers : un fichier avec id unique et combinsaison unique, et un fichier avec position (unique) et id (non unique) et combinsaison (non unique)
2) calculs sur le fichier compressé
3) lien entre les resultats par id, et le fichier de position afin de donner a chaque position son score.

La limitation des ids est donc a l'étape 1, qui est deja bien longue car chacun des 3 fichiers font 260G. Mais c'est l'étape 2 qui dure le plus longtemps : environ 10 fois plus longue que l'étape 1.

C'est bourrin, c'est pourri, mais c'est plus rapide d'utiliser le programme ainsi que de le refaire.

Pour la mémoire, je pense que ca fontionnera. J'ai acces a 2 machines avec 48G.

Une idée encore me vient : pourquoi avoir un id : je ne garde en memoire que les combinaisons trié, et je réecris l'etape 3 pour faire le lien via les combinaisons et non via les ids. Je sauve l'ecriture du fichier non compressé qui fait en gros la somme de la taille des 3 fichiers initiaux

[tchize_]

Effectivement, pour associer un Id unique à chaque combinaison, ca va consommer. Ta table de correspondance pourrais consommer, a priori, ~260G
Sans parler du temps de recherche....


Par contre, ce que tu peux peut-être faire, sans avoir à changer des masses ton algorithme.

Si j'ai bien compris, une "combinaison" unique, pour toi, c'est un ensemble de, par exemple 450A, 1247C, 447G, 369T.
Donc pour les besoins de ton algo, AACATG et TCAGAA, c'est la même chose?


tu pourrais associer à chaque combinaison une série de 4*16bits, donc 64 bits, que tu stockerais dans un long, et utiliser ça comme identifieur.

On est plus trop dans le problème de java, mais plutot dans de l'algorithmique. Je sais qu'il existe des structure et des montages spécifiques pour gérer les chaines génomiques, mais là tu aura probablement plus de chance dans la section algo du forum

[Zwiter]

Très intéressant, mais je pourrais avoir un nombre dépassant les 16 bits. ceci dit, l'intérêt pour nous d'une telle position est très limitée. Je pense implémenter cette solution.

Est ce que tu sais si java permet de stocker facilement des données binaires, genre dépassant le 'long'.
merci énormément.
Z.

[tchize_]

ben long[]

Sinon il y a bien les bigNumber, mais pour ton cas, ça va pas être bon. Trop lourd en calcul.