Meilleur conteneur...

Le
MiXAO
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?

Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.

MiXAO
  • Partager ce contenu :
Vos réponses
Trier par : date / pertinence
Nico
Le #176972
Oui, ou alors un HashSet qui ne différencie pas la clé et l'objet.

Nicolas

"MiXAO" a écrit dans le message de
news:41fd2d70$0$11842$
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?

Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.

MiXAO


MiXAO
Le #176969
Nico wrote:
Oui, ou alors un HashSet qui ne différencie pas la clé et l'objet.


Ah oui, le HashSet, sympathique, justement, j'ai pas besoin de couple
clé/objet. merci de ton aide.

MiXAO

Johann Burkard
Le #176889
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?

Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.


J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:

-- 8< --
The HashCache is a collision-free hash table that only stores hash codes
from Objects, not the actual Objects themselves. This is useful when the
most frequent operation is <code>contains</code> (a O(1) operation in
the HashCache).
[...]
Performance results for 1 million <code>contains</code> invocations (@
2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:

HashCache: ~ 80 ms
java.util.TreeSet: ~ 265 ms
java.util.HashSet: ~ 350 ms
java.util.Hashtable: ~ 625 ms
java.util.ArrayList: ~ 850 ms
java.util.Vector: ~ 930 ms
-- >8 --

Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux
essayer.

[1]
Johann
--
X-Post über de.soc.netzkultur.umgangsformen und
de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen
(*Tönnes in
Nico
Le #176888
"Johann Burkard" news:41fd36fe$0$18561$
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?

Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.


J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:

-- 8< --
The HashCache is a collision-free hash table that only stores hash codes
from Objects, not the actual Objects themselves. This is useful when the
most frequent operation is <code>contains</code> (a O(1) operation in
the HashCache).
[...]
Performance results for 1 million <code>contains</code> invocations (@
2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:

HashCache: ~ 80 ms
java.util.TreeSet: ~ 265 ms
java.util.HashSet: ~ 350 ms
java.util.Hashtable: ~ 625 ms
java.util.ArrayList: ~ 850 ms
java.util.Vector: ~ 930 ms
-- >8 --

Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux
essayer.


Désolé, mais je comprends pas comment ca peut marcher.
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils
sont égaux.
Tu peux m'expliquer ?

Nicolas


Johann Burkard
Le #176881
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils
sont égaux.


Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si
tu as trop de collisions.

En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve
dans un Collection. Ou bien c'est ce que je pense.

Johann
--
X-Post über de.soc.netzkultur.umgangsformen und
de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen
(*Tönnes in
Nico
Le #176810
"Johann Burkard" news:41fd4d8b$0$18553$
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode
qu'ils


sont égaux.


Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si
tu as trop de collisions.

En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve
dans un Collection. Ou bien c'est ce que je pense.


D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode
donné.

Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la
méthode contains() avec un autre objet B (différent de A), il y a une très
faible chance (1 sur 2^64) que cette méthode retourne true.
Donc il y a des cas ou ta méthode ne marche pas.

Nicolas


Johann Burkard
Le #176807
Nico wrote:
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode
donné.


Mais si:

-- 8< --
protected boolean add(int code) {
int pos = Math.abs(code) % array.length;
if (array[pos] == code) {

/* Value is already in array, resizing not required. */

return false;
}

while (array[pos] != 0) {

/*
* Worst-case scenario: There is another element at the computed
position,
* the array needs resizing because we do not allow collisions in the
* HashCache.
*
* Find out at which size of the array all current hash codes can be
mapped
* to new buckets without producing collisions.
*/

grow();
pos = Math.abs(code) % array.length;

}

array[pos] = code;
++size;
return true;
}
-- >8 --

Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la
méthode contains() avec un autre objet B (différent de A), il y a une très
faible chance (1 sur 2^64) que cette méthode retourne true.


Euh, la chance est 1/2^32, pas 1/2^64 (_int_ hashCode()). En fait, c'est
que 1/2^31 (Math.abs(code)) dans le HashCache. Mais je peux pas éviter
ca - un HashCache ne contient les objets.

Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache
pour éliminer quelques percents des appels d'un autre Collection.

Johann
--
X-Post über de.soc.netzkultur.umgangsformen und
de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen
(*Tönnes in
fg
Le #177881

Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache
pour éliminer quelques percents des appels d'un autre Collection.



Au lieu de cela, je pense que tu peux modifier un peu ta classe :
-au lieu d'un tableau d'int, tu fais 1 tableau d'objets
-au lieu de stocker les hashcode (que tu ré-utilises dans ta méthode grow()
j'imagine, j'ai juste lu les messages, pas ta source), tu stockes les objets
(je ne pense pas que tout cela n'implique un important ralentissement, si
oui, oubliez mon message... mais ta classe restera approximative...)
-pour le test du "contains", tu vas à l'endroit concerné, s'il y a un objet,
tu testes cetObjet.equals(leParametre)

(en gros, tu refais la Hashtable, mais sans les LinkedList ;-) )

Je pense que tu peux retrouver exactement le même comportement avec la
Hashtable en jouant sur ses deux paramètres de constructeur.

Fred.

burma
Le #179129
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?

Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.

MiXAO


Dans jazzy, (correcteur orthographique dispo sur sourceforge), j'ai
écris une classe qui mappe, avec les nio, toutes les chaines dans un
fichier sur le disque et permet ensuite de les retrouver par dichotomie.

Cela nécessite une jdk 1.4+, c'est surement moins rapide qu'un hashset,
mais ca consomme également beaucoup moins de mémoire...

Emmanuel D.

Poster une réponse
Anonyme