| Accueil de l'archive | Service proposé par Hervé AGNOUX |
Date sent: Thu, 02 Mar 2000 16:21:50 +0100
From: Andre Schaaff <Andre.Schaaff@loria.fr>
Organization: LORIA
To: "java@u-strasbg.fr" <java@u-strasbg.fr>,
"javaqc@sorengo.com" <javaqc@sorengo.com>
Subject: comparaison
Send reply to: java@u-strasbg.fr
Bonjour,
c'est sans doute une question très bête :
d'un point de vue rapidité, vaut-il mieux utiliser un treeSet ou une
Hashtable ?
merci
From: Olivier Dedieu <Olivier.Dedieu@inria.fr> Date sent: Thu, 2 Mar 2000 17:50:56 +0100 (MET) To: java@u-strasbg.fr Copies to: "javaqc@sorengo.com" <javaqc@sorengo.com> Subject: Re: comparaison Send reply to: java@u-strasbg.fr > Bonjour, > > c'est sans doute une question très bête : > d'un point de vue rapidité, vaut-il mieux utiliser un treeSet ou une > Hashtable ? Tout dépend de tes données et du type d'operation que tu compte faire (insertion, retrait, consultation, tri, ...) Le TreeSet t'assure de bonne perf quelque soit ce que tu fait (O(log(n))) et quelque soit les données que tu y met tu moment quelles sont comparables La Hashtable (ou HashSet) depend fortement du cout et de la distribution de la fonction de hash de tes données. Mais si t'en trouve une bonne, ca peut etre meilleure que TreeSet en consultation si tu as beaucoup de données O(1)). Un copain me disait que ce qu'il y a de mieux c'est une table de hash qui gere les collisions dans un TreeSet (par defaut c'est une liste chainée donc bonjour les perf qd ca distribue mal). Mais alors la il faut qd meme une assez bonne fonction de hash et des données comparables (au sens java.lang.Comparable). Mais j'ai toujours pas trouvé le temps de l'écrire ;-) a+ --------------------------------------------------------------- Olivier Dedieu - (INRIA - Bull / WebTools - Pharos) Web: http://www-sor.inria.fr/~dedieu JavaChannel: http://pharos.inria.fr/Java/ Pharos team: http://webtools.dyade.fr/pharos/ ---------------------------------------------------------------
Send reply to: "Thibaut Fagart" <tfagart@soleri.com> From: "Thibaut Fagart" <tfagart@soleri.com> To: <java@u-strasbg.fr> Subject: Re: comparaison Date sent: Thu, 2 Mar 2000 18:19:12 +0100 ----- Message d'origine ----- De : Olivier Dedieu <Olivier.Dedieu@inria.fr> À : <java@u-strasbg.fr> Cc : <javaqc@sorengo.com> Envoyé : jeudi 2 mars 2000 17:50 Objet : Re: comparaison > > > > > Bonjour, > > > > c'est sans doute une question très bête : > > d'un point de vue rapidité, vaut-il mieux utiliser un treeSet ou une > > Hashtable ? > > Tout dépend de tes données et du type d'operation que tu compte faire > (insertion, retrait, consultation, tri, ...) > > Le TreeSet t'assure de bonne perf quelque soit ce que tu fait > (O(log(n))) et quelque soit les données que tu y met tu moment quelles > sont comparables > > La Hashtable (ou HashSet) depend fortement du cout et de la > distribution de la fonction de hash de tes données. Mais si t'en > trouve une bonne, ca peut etre meilleure que TreeSet en consultation si > tu as beaucoup de données O(1)). > > Un copain me disait que ce qu'il y a de mieux c'est une table de hash > qui gere les collisions dans un TreeSet (par defaut c'est une liste > chainée donc bonjour les perf qd ca distribue mal). Mais alors la il > faut qd meme une assez bonne fonction de hash et des données comparables > (au sens java.lang.Comparable). Mais j'ai toujours pas trouvé le temps > de l'écrire ;-) > > a+ Et pourquoi pas gerer les collisions dans une autre HashMap? > > --------------------------------------------------------------- > Olivier Dedieu - (INRIA - Bull / WebTools - Pharos) > Web: http://www-sor.inria.fr/~dedieu > JavaChannel: http://pharos.inria.fr/Java/ > Pharos team: http://webtools.dyade.fr/pharos/ > --------------------------------------------------------------- > > > > >
From: Olivier Dedieu <Olivier.Dedieu@inria.fr> Date sent: Thu, 2 Mar 2000 18:38:24 +0100 (MET) To: "Thibaut Fagart" <tfagart@soleri.com> Copies to: <java@u-strasbg.fr> Subject: Re: comparaison Send reply to: java@u-strasbg.fr > Et pourquoi pas gerer les collisions dans une autre HashMap? Quelles serait la fonction de hash ? ca ne peut pas etre la meme. Mais effectivement des algo bien connu sur la gestion des collisions dans les tables de hash (hashage linaire (je cherche une autre place), quadartique (un autre place en faisant des sauts exponentiel), rehachage (utilisation d'une 2e fonction de hash), aleatoire, ...) Pour plus d'info: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html quelques livres: http://pharos.inria.fr/Programming/search?term=s1:26&history=history0%3DsimpleMode%253Don%2526kind%253Dcomplete%2526term%253Ds1%25253A548%2526keyword.s1%253A548%253Don a+ -- --------------------------------------------------------------- Olivier Dedieu - (INRIA - Bull / WebTools - Pharos) Web: http://www-sor.inria.fr/~dedieu JavaChannel: http://pharos.inria.fr/Java/ Pharos team: http://webtools.dyade.fr/pharos/ ---------------------------------------------------------------
From: Olivier Dedieu <Olivier.Dedieu@inria.fr> Date sent: Fri, 3 Mar 2000 08:39:27 +0100 (MET) To: java@u-strasbg.fr Copies to: Thibaut Fagart <tfagart@soleri.com> Subject: Re: comparaison Send reply to: java@u-strasbg.fr > Sur le hashage, ya rien a re-inventer (AMHA). Voir le PerfcetHash chez > GNU; adapter le code a Java et hop ! Ya une litterature enorme a ce > sujet... Sur le hachage en particulier non. Sur les fonctions de hash et les algo de recherche en particulier si. Si les clés sont de taille important et offre une certaine regularité (p. ex. les URL d'un meme site), il y a des fonctions qui ne marche pas du tout. J'en ai fait les frais avec celle de java.util.Hashtable. Elle fait son calcul sur les 8 premiers caractères et apres et elle rebondit tous les 16 caractères. Du coup, comme les clés sont assez simialires, le nombre de collision est TRES elevé (ca m'a fait perdre 1 semaine pour comprendre pourquoi mon bench me donner des resultats merdique). Bref, si sur ce coup j'avais utiliser un HashMap/TreeMap plutot que Hashtable, j'aurai gagné. Mieux encore si on avait des classes d'automates (j'en ai trouvé en Java mais leur impl n'est pas performante, trop d'allocation). a+ --------------------------------------------------------------- Olivier Dedieu - (INRIA - Bull / WebTools - Pharos) Web: http://www-sor.inria.fr/~dedieu JavaChannel: http://pharos.inria.fr/Java/ Pharos team: http://webtools.dyade.fr/pharos/ ---------------------------------------------------------------
Date sent: Fri, 3 Mar 2000 07:49:22 +0000 ( )
From: Michel Marcon <cmic@cetu.equipement.gouv.fr>
To: Olivier Dedieu <Olivier.Dedieu@inria.fr>
Copies to: Thibaut Fagart <tfagart@soleri.com>, java@u-strasbg.fr
Subject: Re: comparaison
Send reply to: java@u-strasbg.fr
Sur le hashage, ya rien a re-inventer (AMHA). Voir le PerfcetHash chez
GNU; adapter le code a Java et hop ! Ya une litterature enorme a ce
sujet... cmic
On Thu, 2 Mar 2000, Olivier Dedieu wrote:
>
> > Et pourquoi pas gerer les collisions dans une autre HashMap?
>
> Quelles serait la fonction de hash ? ca ne peut pas etre la meme. Mais
> effectivement des algo bien connu sur la gestion des collisions dans les
> tables de hash (hashage linaire (je cherche une autre place),
> quadartique (un autre place en faisant des sauts exponentiel), rehachage
> (utilisation d'une 2e fonction de hash), aleatoire, ...)
>
> Pour plus d'info:
> http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html
>
> quelques livres:
> http://pharos.inria.fr/Programming/search?term=s1:26&history=history0%3D
> simpleMode%253Don%2526kind%253Dcomplete%2526term%253Ds1%25253A548%2526ke
> yword.s1%253A548%253Don
>
> a+
>
> --
> ---------------------------------------------------------------
> Olivier Dedieu - (INRIA - Bull / WebTools - Pharos)
> Web: http://www-sor.inria.fr/~dedieu
> JavaChannel: http://pharos.inria.fr/Java/
> Pharos team: http://webtools.dyade.fr/pharos/
> ---------------------------------------------------------------
>
>
>
>
>
>
==================================
Michel Marcon Sysadmin UNIX & WNT
"J'ai planifié ma fin pour ce millénaire.
Et vous ?"
BigScheduler...
===================================
Ministere de l'Equipement CETU (Centre d'Etudes des Tunnels)
Web site http://www.equipement.gouv.fr/cetu/
Tel +33 (0)4 7214-3408 Fax +33 (0)4 7214-3430
Date sent: Fri, 03 Mar 2000 17:14:12 +0100 From: Laurent Rouvet <laurent@roovay.com> To: java@u-strasbg.fr Subject: Re: comparaison Send reply to: java@u-strasbg.fr Olivier Dedieu wrote: > > Hashtable, j'aurai gagné. Mieux encore si on avait des classes > d'automates (j'en ai trouvé en Java mais leur impl n'est pas > performante, trop d'allocation). Qu'appeles-tu des classes d'automates ? Que veux-tu dire ?
From: Olivier Dedieu <Olivier.Dedieu@inria.fr> Date sent: Fri, 3 Mar 2000 17:40:14 +0100 (MET) To: java@u-strasbg.fr Subject: Re: comparaison Send reply to: java@u-strasbg.fr > > Olivier Dedieu wrote: > > > > Hashtable, j'aurai gagné. Mieux encore si on avait des classes > > d'automates (j'en ai trouvé en Java mais leur impl n'est pas > > performante, trop d'allocation). > > Qu'appeles-tu des classes d'automates ? Que veux-tu dire ? Pour simplifier, les automates sont des graphes d'état dont les arcs sont étiquetés par des lettres. Ce sont des structures de données tres efficace pour gerer de gros volume de données textuels et pour y faire des recherches. C'est par exemple utiliser pour la recherche textuelle par expression reguliere (grep, Perl, OROMatcher, ...). Les patternes de recherches (p. ex. qque chose du genre abc([d-g].*[^xyz]+)\s+\S+) sont matérialisé par un automate a qui ont soumet le texte a analyser. Quelques pointeurs (dont l'excellent bouquin de M. Crochemore): http://pharos.inria.fr/Programming/search?term=s1:1035 a+ --------------------------------------------------------------- Olivier Dedieu - (INRIA - Bull / WebTools - Pharos) Web: http://www-sor.inria.fr/~dedieu JavaChannel: http://pharos.inria.fr/Java/ Pharos team: http://webtools.dyade.fr/pharos/ ---------------------------------------------------------------
Date sent: Fri, 03 Mar 2000 17:49:52 +0100 From: Laurent Rouvet <laurent@roovay.com> To: java@u-strasbg.fr Subject: Re: comparaison Send reply to: java@u-strasbg.fr Olivier Dedieu wrote: > > > > > Olivier Dedieu wrote: > > > > > > Hashtable, j'aurai gagné. Mieux encore si on avait des classes > > > d'automates (j'en ai trouvé en Java mais leur impl n'est pas > > > performante, trop d'allocation). > > > > Qu'appeles-tu des classes d'automates ? Que veux-tu dire ? > > Pour simplifier, les automates sont des graphes d'état dont les arcs > sont étiquetés par des lettres. Ce sont des structures de données tres > efficace pour gerer de gros volume de données textuels et pour y faire > des recherches. C'est par exemple utiliser pour la recherche textuelle > par expression reguliere (grep, Perl, OROMatcher, ...). Les patternes de > recherches (p. ex. qque chose du genre abc([d-g].*[^xyz]+)\s+\S+) sont > matérialisé par un automate a qui ont soumet le texte a analyser. Merci, pour l'explication... Mais, je me suis mal exprime. Ma question porte sur l'utilisation que tu penses en faire. Quel rapport avec les Hashtables ? Enfait, tu proposes une idee (d'utilisation) que je ne comprends pas. ;-)
From: Olivier Dedieu <Olivier.Dedieu@inria.fr> Date sent: Fri, 3 Mar 2000 18:00:14 +0100 (MET) To: java@u-strasbg.fr Subject: Re: comparaison Send reply to: java@u-strasbg.fr > Merci, pour l'explication... > Mais, je me suis mal exprime. Ma question porte sur l'utilisation > que tu penses en faire. Quel rapport avec les Hashtables ? > Enfait, tu proposes une idee (d'utilisation) que je ne comprends pas. > ;-) Si dans ta hashtable les clés sont des String, les automates sont une bonne alternative: 1) ils te font gagner de la place (en gros ils factorisent les prefixes et les suffixes communs des String), 2) ils peuvent augmenter les perf de consultation (un simple parcourt de la chaine recherché) 3) Les insertions sont a peu pres aussi rapide que les consultations (pas de pb de collision) 4) ils te permettent de recherche avec des prefixes de clé (e.g. quelles sont toutes les entrées qui commencent par 'http://java.sun.com/') a+ --------------------------------------------------------------- Olivier Dedieu - (INRIA - Bull / WebTools - Pharos) Web: http://www-sor.inria.fr/~dedieu JavaChannel: http://pharos.inria.fr/Java/ Pharos team: http://webtools.dyade.fr/pharos/ ---------------------------------------------------------------
Date sent: Fri, 03 Mar 2000 18:25:32 +0100 From: Laurent Rouvet <laurent@roovay.com> To: java@u-strasbg.fr Subject: Re: comparaison Send reply to: java@u-strasbg.fr Olivier Dedieu wrote: > > Si dans ta hashtable les clés sont des String, les automates sont une > bonne alternative: Il semble que la solution simple consite a utilise une TreeMap ? C'est un peu moins performant, mais... de beaucoup...? > 1) ils te font gagner de la place (en gros ils factorisent les > prefixes et les suffixes communs des String), Ok, peut-etre 30% de la table des key (sur une grosse table). non ? > > 2) ils peuvent augmenter les perf de consultation (un simple parcourt > de la chaine recherché) Ok, le hashtable est plus rapide que le Tree. Mais dans ton cas (je suppose Pharos) l'utilisation d'une TreeMap du JDK 1.2 serait-il possible ? > > 3) Les insertions sont a peu pres aussi rapide que les consultations > (pas de pb de collision) La, la TreeMap me semble aussi bien. > > 4) ils te permettent de recherche avec des prefixes de clé > (e.g. quelles sont toutes les entrées qui commencent par > 'http://java.sun.com/') De meme avec TreeMap. non ? Conclusion une simple TreeMap ne serait-ce pas suffisant ?