Discussion :

[rockley]

Bonjour

J'ai

Code :

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

1
2
3
4
 
String s = "toté";
int sr = s.hashCode();
System.out.println(sr);

Ce qui donne 3566256.

Peut-on inverser les choses.
Passer 3566256 et obtenir toté ?

[adiGuba]

Salut,


Non ce n'est pas possible.
Que veux-tu faire précisément ?


a++

[-gma-]

Bonjour,

Non tu ne peux pas. C'est le principe d'une fonction hash, ce qu'elle n'est qu'à une seule direction (ou surjective pour reprendre le vocabulaire mathématique).

D'ailleurs tu peux théoriquement avoir plusieurs String qui auront pour hashCode 3566256. Et c'est logique puisque tu peux avoir beaucoup plus de String différentes que de valeurs de int en Java.

[rockley]

C'est pour un moteur de recherche.

Je dois stoker 3 valeurs.
Nom du texte
mot
valeur pondéral ( nb d'itération du mot cherchée / nb de mots d'un texte).

Dans mes bases, au lieu de stoker des string en trois colonne, ça donne
hashcode de : Nom du texte
hashcode de mot + valeur pondéral (>= 0 et < 1 (je vérifie que le texte n'est pas composé d'un même mot)).

Donc je stocke un int et un double sur 2 colonnes. Aussi rapide à indexer qu'avec des String mais 10 fois plus rapide dans les recherches.

Je voulais savoir si à partir des bases je pouvais retrouver les mots et faire des stat. par exemple.

[adiGuba]

Si tu as un index sur tes clefs, je pense que cela doit être aussi rapide avec les String.


a++

[tchize_]

et n'oublie pas de gérer les colissions de tes hash. Le hash est un moyen très rapide de trouver dans quel coin se trouve la donnée, mais il faut y ajouter la string complete pour retirer toute ambiguité. On associe à un String un hashcode, mais a un hashcode on associe une Liste de strings!

[rockley]

mais a un hashcode on associe une Liste de strings!

Et je suppose qu'on ne peux pas connaitre la liste de Strings.

Pour info, le moteur de recherche ne comporte "que" les 260 000 mots de la langue française. Les doublons sur si peu de mots doivent être rare.

Code :

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

1
2
System.out.println(Integer.MAX_VALUE);
=2.147.483.647

Pour le moteur de recherche, il est en java, et la base de donnée, c'est hsqldb.
Du coup on peut l'exécuter sur différent OS, et la BD est intégrée.
Et pour que la DB reste de taille raisonnable, je préfère stoker des Int et Double, car ça prend moi de place.

Je voulais faire un truc petit, puissant et multi-plateforme.

[adiGuba]

Pour info, le moteur de recherche ne comporte "que" les 260 000 mots de la langue française. Les doublons sur si peu de mots doivent être rare.

Et si tu as des doublons tu fais quoi ? Tu supprimes le mot de la langue française ???


a++

[tchize_]

Et je suppose qu'on ne peux pas connaitre la liste de Strings.

C'est à toi de la maintenir au fur et à mesure que tu génère tes hashcode.
Si tu veux chercher "rapidement" à partir des hashcode, il faudrait ceci dans ta DB:

Code :

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

id (unique), hashcode (indexé), nom (String), autres données dont tu as besoin

et mettre dans tes requetes

Code :

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

where hashcode=..... and nom=......

Maintenant, en général, quand tu indexe un colonne de type "string", la DB fait déjà ce genre d'optimisation pour toi :/

Pour info, le moteur de recherche ne comporte "que" les 260 000 mots de la langue française. Les doublons sur si peu de mots doivent être rare.

Je te trouve extrèmement optimiste. En passant un dicitonnaire de ~230.000 mots ici, je trouve déjà 25 collisions (donc 50 mots à problème).

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
Map<Integer,String> existant = new HashMap<Integer, String>();
		Map<Integer,Integer> collisions = new HashMap<Integer, Integer>();
		Reader r = new InputStreamReader(new FileInputStream("/tmp/dico.txt"), "iso-8859-1");
		BufferedReader br = new BufferedReader(r);
		String mot = null;
		int detected = 0;
		while ((mot = br.readLine())!=null) {
			int hash = mot.hashCode();
			if (collisions.containsKey(hash)) {
				collisions.put(hash, collisions.get(hash)+1);
				System.out.printf("collision pour %s/%s: %X\n",mot,existant.get(hash),hash);
				detected++;
			}
			else
				collisions.put(hash, 0);
			existant.put(hash, mot);
		}
		System.out.println("Nombre de collisions détectées: "+detected);

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
 
collision pour affirme/affinée: BF1994E2
collision pour affirmes/affinées: 241907D1
collision pour confirme/confinée: DD6BF1A5
collision pour confirmes/confinées: D012436E
collision pour démastiquerait/currys: AF9610CC
collision pour es/aï: CAE
collision pour esclaffées/afflouée: 24421F2D
collision pour germent/gaîment: FB74DAB2
collision pour gym/gué: 191BB
collision pour gyms/gués: 30A618
collision pour hannetonneras/boudeur: 42C58A6
collision pour hibernèrent/civilisasse: C44755E1
collision pour lerche/laîche: BE0FFBE7
collision pour liserassions/dépareillé: A5026849
collision pour mesa/maïa: 3315E6
collision pour mesas/maïas: 62FA74D
collision pour mess/maïs: 3315F8
collision pour outillerait/marchant: E48DCC4
collision pour parme/panée: 65819F9
collision pour relançassiez/pneumothorax: 72D1331E
collision pour révolutionnons/esthétisée: 1F753C93
collision pour ses/saï: 1BC61
collision pour solidifié/développerait: AF60A0A8
collision pour surclasserait/bactéricide: E5EA2D57
collision pour visualisé/baffâtes: 8383C9BF
Nombre de collisions détectées: 25

Et pour que la DB reste de taille raisonnable, je préfère stoker des Int et Double, car ça prend moi de place.

Un dictionnaire de 260.000 mots, ca représente environ 6M dans la base de données, à tout casser. Le gain n'a pas de sens.

[rockley]

Merci pour votre aide.

C'est vrai que je pense que je me suis fait un peu emporté par mes rêves d'optimisation.
Et l'anecdote, c'est que j'ai poussé le vice jusqu'à mettre des ++i au lieu de i++ dans mes boucles, pour économiser une copie.

[adiGuba]

C'est vrai que je pense que je me suis fait un peu emporté par mes rêves d'optimisation.
Et l'anecdote, c'est que j'ai poussé le vice jusqu'à mettre des ++i au lieu de i++ dans mes boucles, pour économiser une copie.

Franchement : Arrêtes de penser "optimisation" ! Sinon tu vas finir par faire une usine à gaz illisible pour pas grand chose.


Tu gagnerais nettement plus à améliorer la lisibilité de ton code et son organisation.

Tant que tu n'as pas détecté des points morts dans ton code, il est inutile de vouloir optimisé. C'est même contre productif



a++

[tchize_]

j'ai poussé le vice jusqu'à mettre des ++i au lieu de i++ dans mes boucles, pour économiser une copie.

pour info c'est totalement inutile, la plupart des CPU faisant ces deux opérations en un seul cycle sur un registre