Discussion :

[kolodz]

Bonjour,

Afin d'optimiser un des mes algorithmes, il m'est nécessaire de mettre en "cache" le résultat de certains calcules. Afin de pouvoir, reprendre le résultat directement.

Afin de réduire au maximum le set de résulta, il m'est nécessaire d'avoir une fonction de hash particulière. Les spécifications de celle-ci doivent être :

• Pas de collision de hash
• Les rotation circulaires donne le même hash.

Les données générant le hash sont 4 nombres allant de 0 à 22 (ou manquant). Il m'est donc facile de passé à une représentation de string d'une longueur de 4

abcd
bcda
cdab
dabc

Toutes autres variations doivent donner un autre hash.

bc
cb

Le sens ayant une importance. (Ici c'est le cas où je n'ai que 2 des nombres.)

J'ai réalisé une première recherche par rapport à ce problème est j'ai trouvé une réponse intéressante, mais incomplète. (Car, il y a des collisions de hash)

Code java :

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class test {
	static int a;
	static int b;
	static int Hash(String s)
	{
	    int H = 0;
	    if (s.length() > 0)
	    {
	        //any arbitrary coprime numbers
	        a = 61;
	        b = 89;
 
	        //an array of Euclid-Fermat sequences to generate additional coprimes for each duplicate character occurrence
	        int[] c = new int[0xFF];
 
	        for (int i = 1; i < c.length; i++)
	        {
	            c[i] = i + 1;
	        }
 
	        //for i=0 we need to wrap around to the last character
	        H = NextPair(s.toCharArray()[s.length() - 1], s.toCharArray()[0],c);
 
	        //for i=1...n we use the previous character
	        for (int i = 1; i < s.length(); i++)
	        {
	            H ^= NextPair(s.toCharArray()[i - 1], s.toCharArray()[i], c);
	        }
	    }
 
	    return H;
	}
 
	static int NextCoprime(char letter, int[] table ){
		return table[letter] = (table[letter] - letter) * table[letter] + letter;
	}
	static int NextPair(char letterX, char LetterY, int[] table){
		return a * NextCoprime(letterX, table) * letterX + b * LetterY;
	}
 
	public static void main(String[] args) throws FileNotFoundException {	
 
		System.out.println(Hash("abcd"));
		System.out.println(Hash("bcda"));
		System.out.println(Hash("cdab"));
		System.out.println(Hash("dabc"));
		// cas problèmatique dans mon set de donnée :
		System.out.println("problème 1 :"+Hash("mqe ")+" "+Hash("bor"));
		System.out.println("problème 2 :"+Hash("fql ")+" "+Hash("kfr"));
		System.out.println("problème 3 :"+Hash("ngi ")+" "+Hash("hpc"));
		System.out.println("problème 4 :"+Hash("kib ")+" "+Hash("ikb"));
		}
}

199052
199052
199052
199052
problème 1 :2058518 1917362
problème 2 :1855590 1991362
problème 3 :1279850 1150890
problème 4 :1136810 1266474

Note : Par variation des valeurs a et b, j'arrive à ne pas avoir de collision dans mon cas particulier. Cependant, avoir une solution propre au problème m'intéresse. (Si je change mon Set je n'ai rien d'assuré)

Cordialement,
Patrick Kolodziejczyk.
source :
http://stackoverflow.com/questions/8...rences-in-java

Edit : Contenu de la taille de mon set : 6280e entrées sans permutation circulaire, 1570 avec (/4)
Je suis passé à un hash plus simple :

Code java :

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

1
2
3
	static int Hash(int a, int b, int c,int d) {
		return ((a<< 18)+(b<< 12)+(c<< 6)+d);
	}

Sachant que l'int java est sur 32 bits et que les valeurs sont stockable sur 6 bits (0 à 63).

Faute de mieux pour le moment.

[dinobogan]

Reprenons les hypothèses : tu cherches à calculer un nombre unique pour une chaîne donnée. A une chaîne correspond un seul nombre de 32 bits (ou hash) et à un hash correspond zéro ou une seule chaîne.
Toutes tes chaînes sont composées de quatre caractères maximum, chaque caractère allant de 0 à 22.
22 en binaire s'écrit sur 5 bits. Puisque tes chaînes ne dépasseront jamais 4 caractères, le hash sera sur 5 * 4 = 20 bits maximum.
Une solution possible consiste à transformer chaque caractère en sa valeur sur 5 bits et coller les bits dans un entier 32 bits.
Avec cette méthode, tu es assuré d'avoir un hash unique pour chaque chaîne.

[kolodz]

C'est ce que j'ai fait. Mais, j'aurai aimé avoir un hash identique pour l'ensemble des permutation circulaire. Cela pour réduire le temps de recherche dans ma liste.

[anapurna]

salut
dans ce cas là tu fait un tri croisant ou décroissante sur tes mots de 4 caractère et le tour est jouer

[kolodz]

Cela ne va pas changer le fait que mon tableau est 4 fois plus grand que ce qu'il devrait.

[anapurna]

salut

??? Quel que soit la combinaison de ta chaine de 4 caractere tu auras une le unique a rentré dans ton hash donc tu va forcement reduire celui-ci

je m'explique tu passe en paramètre une de ces combinaison

"abcd"
"bcda"
"cdab"
"dabc"

dans ton hash selon le choix de tri que tu as décidè
pour l'exemple je prend le tri croissant je passerai toujours la même et unique clé
"abcd"

donc tu divise par 4 le set de tes chaine de 4 caractère c'est quand même pas négligeable ... non ?

[tbc92]

Je me limite aux cas de type abcd. Restera donc à régler les cas de type ab ou ba.

Si recense toute les combinaisons , ça donne 23*23*23*23 , soit 279841
Et si on recense les combinaisons de type abcd (a<b<c<d), on tombe à 8855 combinaisons
Tu peux donc construire un 1° tableau T[23,23,23,23] qui pointe vers un nombre entre 1 et 8855.
Puis un tableau de 8855 chaines, ou 8855 structures ... je n'ai pas forcément suivi ce que tu mettais dans cette structure.

[kolodz]

Bonjour,

Merci pour vos réponses !
@tbc92 : J'ai retenu ta solution et l'implémentation fonctionne parfaitement !
Après mon premier essai, j'ai constaté une amélioration de performance d'environ 100 par rapport à la version sans le cache.

De 296 000 éléments traités en 3 minutes à 254 000 000 éléments traités en 30 minutes.

L’empreinte mémoire de l'application passe d’environ 10Mo en mémoire à 50 Mo. (A noter que c'est l'allocation maximal de la VM, l’application tourne à environ 30Mo utilisé.)

Le gain est colossal. Je réaliserai probablement un billet sur mon blog par rapport ça.

Cordialement,
Patrick Kolodziejczyk.

Edit : Voici le lien vers le billet parlant du résultat :
http://www.developpez.net/forums/blo...che-matriciel/