Cela est peut-etre plus un problème d'algorithmie, mais l'implementation des
Hashtable en Java a peut-être une influence sur la réponse, d'où le choix de
ce ng pour mon post.
Je dispose d'une structure arborescente classique, mais qui peut contenir
beaucoup d'elements (plusieurs centaines de milliers, voire quelques millions).
Je me pose la question de l'accès direct grâce à un identifiant à certaines
valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un
parcours en profondeur classique jusqu'à trouver l'element dont
l'identifiant m'a été fourni).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par
exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la
racine), ce qui me permet de descendre la hiérarchie pour retrouver cette
élement à partir de la racine et de l'identifiant rapidement.
- à la création de l'arbre, générer une hashtable qui fait le lien entre un
identifiant et l'element qui lui correspond.
La seconde méthode me semble plus "propre" que la première qui fait un peu
bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur des
collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est envisageable ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Noshi
On Thu, 13 Jan 2005 15:56:57 +0100, Hugo wrote:
Cela est peut-etre plus un problème d'algorithmie, mais l'implementation des Hashtable en Java a peut-être une influence sur la réponse, d'où le choix de ce ng pour mon post.
C'est en effet de l'algorithmie. Enfin bon ... je ne suis pas dévellopeur java. Je me base sur le C pour répondre (vu que le java n'est que du C light... ca devrait rester cohérent attention c'est un troll :))) )
Je dispose d'une structure arborescente classique, mais qui peut contenir beaucoup d'elements (plusieurs centaines de milliers, voire quelques millions).
Quel type d'arbre ? C'est quoi les éléments qu'on stocke dedans? (de nouveau je me base plus sur ma logique de programmation que sur l'implémentation des arbres en java. D'ailleurs si quelqu'un a un site qui explique bien ca ;) )
Je me pose la question de l'accès direct grâce à un identifiant à certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un parcours en profondeur classique jusqu'à trouver l'element dont l'identifiant m'a été fourni).
Il y aura toujours un accès en profondeur. Même si il est caché par les API.
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la racine), ce qui me permet de descendre la hiérarchie pour retrouver cette élement à partir de la racine et de l'identifiant rapidement.
Euh... Quel intêret de faire cela? Et surtout si l'arbre est équillibré vous allez remettre a jour tous les identifiants à chaque changement de noeud racine ?
- à la création de l'arbre, générer une hashtable qui fait le lien entre un identifiant et l'element qui lui correspond.
Autant ne pas créer d'arbre et tout balancer dans la hashtable alors...
La seconde méthode me semble plus "propre" que la première qui fait un peu bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur des collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est envisageable ?
Moi je ferais un arbre binaire trié et equillibré. 16 millions d'éléments ne demanderont que 23 récursion pour le parcours de l'arbre. Mais bon je sais pas comment fonctionnent les arbres en java. Ni si on peut faire le même genre de chose qu'en C avec des pointeurs...
HTH, -- Noshi
On Thu, 13 Jan 2005 15:56:57 +0100, Hugo wrote:
Cela est peut-etre plus un problème d'algorithmie, mais l'implementation des
Hashtable en Java a peut-être une influence sur la réponse, d'où le choix de
ce ng pour mon post.
C'est en effet de l'algorithmie.
Enfin bon ... je ne suis pas dévellopeur java. Je me base sur le C pour
répondre (vu que le java n'est que du C light... ca devrait rester cohérent
attention c'est un troll :))) )
Je dispose d'une structure arborescente classique, mais qui peut contenir
beaucoup d'elements (plusieurs centaines de milliers, voire quelques millions).
Quel type d'arbre ? C'est quoi les éléments qu'on stocke dedans?
(de nouveau je me base plus sur ma logique de programmation que sur
l'implémentation des arbres en java. D'ailleurs si quelqu'un a un site qui
explique bien ca ;) )
Je me pose la question de l'accès direct grâce à un identifiant à certaines
valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un
parcours en profondeur classique jusqu'à trouver l'element dont
l'identifiant m'a été fourni).
Il y aura toujours un accès en profondeur. Même si il est caché par les
API.
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par
exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la
racine), ce qui me permet de descendre la hiérarchie pour retrouver cette
élement à partir de la racine et de l'identifiant rapidement.
Euh... Quel intêret de faire cela? Et surtout si l'arbre est équillibré
vous allez remettre a jour tous les identifiants à chaque changement de
noeud racine ?
- à la création de l'arbre, générer une hashtable qui fait le lien entre un
identifiant et l'element qui lui correspond.
Autant ne pas créer d'arbre et tout balancer dans la hashtable alors...
La seconde méthode me semble plus "propre" que la première qui fait un peu
bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur des
collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est envisageable ?
Moi je ferais un arbre binaire trié et equillibré. 16 millions d'éléments
ne demanderont que 23 récursion pour le parcours de l'arbre. Mais bon je
sais pas comment fonctionnent les arbres en java. Ni si on peut faire le
même genre de chose qu'en C avec des pointeurs...
Cela est peut-etre plus un problème d'algorithmie, mais l'implementation des Hashtable en Java a peut-être une influence sur la réponse, d'où le choix de ce ng pour mon post.
C'est en effet de l'algorithmie. Enfin bon ... je ne suis pas dévellopeur java. Je me base sur le C pour répondre (vu que le java n'est que du C light... ca devrait rester cohérent attention c'est un troll :))) )
Je dispose d'une structure arborescente classique, mais qui peut contenir beaucoup d'elements (plusieurs centaines de milliers, voire quelques millions).
Quel type d'arbre ? C'est quoi les éléments qu'on stocke dedans? (de nouveau je me base plus sur ma logique de programmation que sur l'implémentation des arbres en java. D'ailleurs si quelqu'un a un site qui explique bien ca ;) )
Je me pose la question de l'accès direct grâce à un identifiant à certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un parcours en profondeur classique jusqu'à trouver l'element dont l'identifiant m'a été fourni).
Il y aura toujours un accès en profondeur. Même si il est caché par les API.
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la racine), ce qui me permet de descendre la hiérarchie pour retrouver cette élement à partir de la racine et de l'identifiant rapidement.
Euh... Quel intêret de faire cela? Et surtout si l'arbre est équillibré vous allez remettre a jour tous les identifiants à chaque changement de noeud racine ?
- à la création de l'arbre, générer une hashtable qui fait le lien entre un identifiant et l'element qui lui correspond.
Autant ne pas créer d'arbre et tout balancer dans la hashtable alors...
La seconde méthode me semble plus "propre" que la première qui fait un peu bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur des collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est envisageable ?
Moi je ferais un arbre binaire trié et equillibré. 16 millions d'éléments ne demanderont que 23 récursion pour le parcours de l'arbre. Mais bon je sais pas comment fonctionnent les arbres en java. Ni si on peut faire le même genre de chose qu'en C avec des pointeurs...
HTH, -- Noshi
Hervé AGNOUX
A ma connaissance, il faut une règle de tri, comme le dit Noshi, (je pense que l'on peut voir votre 5/44/3 comme une sorte de règle de tri, et utiliser un java.util.TreeMap.
Si vous êtes dans un cas simple, et que vous voulez être très rapide, vous pouvez utiliser un HashMap en négociant les choses avec le hashcode et le equals. Mais dans ce cas c'est inutile de faire de l'algorytmie, réfléchissez plutot au calcul du hascode.
Dans vos explications, il n'est pas très clair de savoir si vous êtes dans le cas clef=valeur, où si vos noeuds sont constitués uniquement de valeurs. Mefiez-vous que les hashmap et hashtree c'est pour clef=valeur. Sinon vous avez le TreeSet.
Avec la librairie commons collections de apache, vous disposez de nouvelles possibilités : http://jakarta.apache.org/commons/collections/
Hugo wrote:
Cela est peut-etre plus un problème d'algorithmie, mais l'implementation des Hashtable en Java a peut-être une influence sur la réponse, d'où le choix de ce ng pour mon post.
Je dispose d'une structure arborescente classique, mais qui peut contenir beaucoup d'elements (plusieurs centaines de milliers, voire quelques millions).
Je me pose la question de l'accès direct grâce à un identifiant à certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un parcours en profondeur classique jusqu'à trouver l'element dont l'identifiant m'a été fourni).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la racine), ce qui me permet de descendre la hiérarchie pour retrouver cette élement à partir de la racine et de l'identifiant rapidement.
- à la création de l'arbre, générer une hashtable qui fait le lien entre un identifiant et l'element qui lui correspond.
La seconde méthode me semble plus "propre" que la première qui fait un peu bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur des collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est envisageable ?
-- Hervé AGNOUX http://www.diaam-informatique.com
A ma connaissance, il faut une règle de tri, comme le dit Noshi, (je pense
que l'on peut voir votre 5/44/3 comme une sorte de règle de tri, et
utiliser un java.util.TreeMap.
Si vous êtes dans un cas simple, et que vous voulez être très rapide, vous
pouvez utiliser un HashMap en négociant les choses avec le hashcode et le
equals. Mais dans ce cas c'est inutile de faire de l'algorytmie,
réfléchissez plutot au calcul du hascode.
Dans vos explications, il n'est pas très clair de savoir si vous êtes dans
le cas clef=valeur, où si vos noeuds sont constitués uniquement de valeurs.
Mefiez-vous que les hashmap et hashtree c'est pour clef=valeur. Sinon vous
avez le TreeSet.
Avec la librairie commons collections de apache, vous disposez de nouvelles
possibilités : http://jakarta.apache.org/commons/collections/
Hugo wrote:
Cela est peut-etre plus un problème d'algorithmie, mais l'implementation
des Hashtable en Java a peut-être une influence sur la réponse, d'où le
choix de ce ng pour mon post.
Je dispose d'une structure arborescente classique, mais qui peut contenir
beaucoup d'elements (plusieurs centaines de milliers, voire quelques
millions).
Je me pose la question de l'accès direct grâce à un identifiant à
certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire
*pas* un parcours en profondeur classique jusqu'à trouver l'element dont
l'identifiant m'a été fourni).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par
exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la
racine), ce qui me permet de descendre la hiérarchie pour retrouver cette
élement à partir de la racine et de l'identifiant rapidement.
- à la création de l'arbre, générer une hashtable qui fait le lien entre
un identifiant et l'element qui lui correspond.
La seconde méthode me semble plus "propre" que la première qui fait un peu
bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur
des collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est
envisageable ?
A ma connaissance, il faut une règle de tri, comme le dit Noshi, (je pense que l'on peut voir votre 5/44/3 comme une sorte de règle de tri, et utiliser un java.util.TreeMap.
Si vous êtes dans un cas simple, et que vous voulez être très rapide, vous pouvez utiliser un HashMap en négociant les choses avec le hashcode et le equals. Mais dans ce cas c'est inutile de faire de l'algorytmie, réfléchissez plutot au calcul du hascode.
Dans vos explications, il n'est pas très clair de savoir si vous êtes dans le cas clef=valeur, où si vos noeuds sont constitués uniquement de valeurs. Mefiez-vous que les hashmap et hashtree c'est pour clef=valeur. Sinon vous avez le TreeSet.
Avec la librairie commons collections de apache, vous disposez de nouvelles possibilités : http://jakarta.apache.org/commons/collections/
Hugo wrote:
Cela est peut-etre plus un problème d'algorithmie, mais l'implementation des Hashtable en Java a peut-être une influence sur la réponse, d'où le choix de ce ng pour mon post.
Je dispose d'une structure arborescente classique, mais qui peut contenir beaucoup d'elements (plusieurs centaines de milliers, voire quelques millions).
Je me pose la question de l'accès direct grâce à un identifiant à certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un parcours en profondeur classique jusqu'à trouver l'element dont l'identifiant m'a été fourni).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la racine), ce qui me permet de descendre la hiérarchie pour retrouver cette élement à partir de la racine et de l'identifiant rapidement.
- à la création de l'arbre, générer une hashtable qui fait le lien entre un identifiant et l'element qui lui correspond.
La seconde méthode me semble plus "propre" que la première qui fait un peu bidouille, mais peut-etre est-elle beaucoup moins efficace, surtout sur des collections de données aussi grande.
Qu'en pensez vous ? Peut-être aussi qu'un troisième design est envisageable ?
-- Hervé AGNOUX http://www.diaam-informatique.com
Hugo
On 13/01/2005 21:05, Noshi wrote:
Quel type d'arbre ? C'est quoi les éléments qu'on stocke dedans? (de nouveau je me base plus sur ma logique de programmation que sur l'implémentation des arbres en java. D'ailleurs si quelqu'un a un site qui explique bien ca ;) )
L'arbre est un type de donnée particulier, assimilable à un arbre n-aire générique (noeud = [clé | propriétés | list des fils]) , qui m'est fournit. Il ne fait pas partie des librairies standards. Et les données sont de type clé=valeur
Je me pose la question de l'accès direct grâce à un identifiant à certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un parcours en profondeur classique jusqu'à trouver l'element dont l'identifiant m'a été fourni).
Il y aura toujours un accès en profondeur. Même si il est caché par les API.
Justement je n'ai pas envie d'utiliser ce genre de méthode, et je reflechissais à un accès (plus ou moins) direct à la réference (lire pointeur) d'un noeud à partir de son identifiant (sa clé donc).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la racine), ce qui me permet de descendre la hiérarchie pour retrouver cette élement à partir de la racine et de l'identifiant rapidement.
Euh... Quel intêret de faire cela? Et surtout si l'arbre est équillibré vous allez remettre a jour tous les identifiants à chaque changement de noeud racine ?
Non. En fait je me rends compte que je n'ai pas était assez clair dans mon explication (nez dans le guidon, pas de recul, tout ca...). L'arbre ne subit pas de modification hiérarchique au cours de sa vie. Disons que c'est un arbre en lecteur seul, sauf que je peux tagger les noeuds.
Et il faut que je traite des requetes du type "tel noeud (dont je ne connais uniquement la clé, mais *pas* la reference) dont etre tagger avec telle valeur.
Il me faut donc retrouver ce noeud à partir de cette ID, si possible sans parcourir les 1.000.000 elements en cas de recherche négative.
Donc je voyais 2 solutions : des ID explicites ("/21/3/5"), ou une hashTable.
- à la création de l'arbre, générer une hashtable qui fait le lien entre un identifiant et l'element qui lui correspond.
Autant ne pas créer d'arbre et tout balancer dans la hashtable alors...
Sauf que j'ai besoin de garder la structure hiérarchique, notamment pour les traitements lors d'un mise a jour d'une valeur.
Moi je ferais un arbre binaire trié et equillibré. 16 millions d'éléments ne demanderont que 23 récursion pour le parcours de l'arbre. Mais bon je sais pas comment fonctionnent les arbres en java. Ni si on peut faire le même genre de chose qu'en C avec des pointeurs...
C'est sans doute une bonne idée, mais je ne peux malheureusement pas modifier le type de données qui m'est fournit.
Merci de vos remarques en tout cas. Je me dirige à priori vers l'utilisation d'ID explicite.
-- Hugo
On 13/01/2005 21:05, Noshi wrote:
Quel type d'arbre ? C'est quoi les éléments qu'on stocke dedans?
(de nouveau je me base plus sur ma logique de programmation que sur
l'implémentation des arbres en java. D'ailleurs si quelqu'un a un site qui
explique bien ca ;) )
L'arbre est un type de donnée particulier, assimilable à un arbre n-aire
générique (noeud = [clé | propriétés | list des fils]) , qui m'est fournit.
Il ne fait pas partie des librairies standards. Et les données sont de type
clé=valeur
Je me pose la question de l'accès direct grâce à un identifiant à certaines
valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un
parcours en profondeur classique jusqu'à trouver l'element dont
l'identifiant m'a été fourni).
Il y aura toujours un accès en profondeur. Même si il est caché par les
API.
Justement je n'ai pas envie d'utiliser ce genre de méthode, et je
reflechissais à un accès (plus ou moins) direct à la réference (lire
pointeur) d'un noeud à partir de son identifiant (sa clé donc).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par
exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la
racine), ce qui me permet de descendre la hiérarchie pour retrouver cette
élement à partir de la racine et de l'identifiant rapidement.
Euh... Quel intêret de faire cela? Et surtout si l'arbre est équillibré
vous allez remettre a jour tous les identifiants à chaque changement de
noeud racine ?
Non. En fait je me rends compte que je n'ai pas était assez clair dans mon
explication (nez dans le guidon, pas de recul, tout ca...).
L'arbre ne subit pas de modification hiérarchique au cours de sa vie. Disons
que c'est un arbre en lecteur seul, sauf que je peux tagger les noeuds.
Et il faut que je traite des requetes du type "tel noeud (dont je ne connais
uniquement la clé, mais *pas* la reference) dont etre tagger avec telle valeur.
Il me faut donc retrouver ce noeud à partir de cette ID, si possible sans
parcourir les 1.000.000 elements en cas de recherche négative.
Donc je voyais 2 solutions : des ID explicites ("/21/3/5"), ou une hashTable.
- à la création de l'arbre, générer une hashtable qui fait le lien entre un
identifiant et l'element qui lui correspond.
Autant ne pas créer d'arbre et tout balancer dans la hashtable alors...
Sauf que j'ai besoin de garder la structure hiérarchique, notamment pour les
traitements lors d'un mise a jour d'une valeur.
Moi je ferais un arbre binaire trié et equillibré. 16 millions d'éléments
ne demanderont que 23 récursion pour le parcours de l'arbre. Mais bon je
sais pas comment fonctionnent les arbres en java. Ni si on peut faire le
même genre de chose qu'en C avec des pointeurs...
C'est sans doute une bonne idée, mais je ne peux malheureusement pas
modifier le type de données qui m'est fournit.
Merci de vos remarques en tout cas. Je me dirige à priori vers l'utilisation
d'ID explicite.
Quel type d'arbre ? C'est quoi les éléments qu'on stocke dedans? (de nouveau je me base plus sur ma logique de programmation que sur l'implémentation des arbres en java. D'ailleurs si quelqu'un a un site qui explique bien ca ;) )
L'arbre est un type de donnée particulier, assimilable à un arbre n-aire générique (noeud = [clé | propriétés | list des fils]) , qui m'est fournit. Il ne fait pas partie des librairies standards. Et les données sont de type clé=valeur
Je me pose la question de l'accès direct grâce à un identifiant à certaines valeurs de l'arbre, de manière pas trop lourde (c'est à dire *pas* un parcours en profondeur classique jusqu'à trouver l'element dont l'identifiant m'a été fourni).
Il y aura toujours un accès en profondeur. Même si il est caché par les API.
Justement je n'ai pas envie d'utiliser ce genre de méthode, et je reflechissais à un accès (plus ou moins) direct à la réference (lire pointeur) d'un noeud à partir de son identifiant (sa clé donc).
Je voyais deux méthodes pour l'instant :
- choisir un identifiant qui m'indique l'arborescence à parcourir (par exemple "/5/44/3" pour dire le 3eme fils du 44 fils du 5eme fils de la racine), ce qui me permet de descendre la hiérarchie pour retrouver cette élement à partir de la racine et de l'identifiant rapidement.
Euh... Quel intêret de faire cela? Et surtout si l'arbre est équillibré vous allez remettre a jour tous les identifiants à chaque changement de noeud racine ?
Non. En fait je me rends compte que je n'ai pas était assez clair dans mon explication (nez dans le guidon, pas de recul, tout ca...). L'arbre ne subit pas de modification hiérarchique au cours de sa vie. Disons que c'est un arbre en lecteur seul, sauf que je peux tagger les noeuds.
Et il faut que je traite des requetes du type "tel noeud (dont je ne connais uniquement la clé, mais *pas* la reference) dont etre tagger avec telle valeur.
Il me faut donc retrouver ce noeud à partir de cette ID, si possible sans parcourir les 1.000.000 elements en cas de recherche négative.
Donc je voyais 2 solutions : des ID explicites ("/21/3/5"), ou une hashTable.
- à la création de l'arbre, générer une hashtable qui fait le lien entre un identifiant et l'element qui lui correspond.
Autant ne pas créer d'arbre et tout balancer dans la hashtable alors...
Sauf que j'ai besoin de garder la structure hiérarchique, notamment pour les traitements lors d'un mise a jour d'une valeur.
Moi je ferais un arbre binaire trié et equillibré. 16 millions d'éléments ne demanderont que 23 récursion pour le parcours de l'arbre. Mais bon je sais pas comment fonctionnent les arbres en java. Ni si on peut faire le même genre de chose qu'en C avec des pointeurs...
C'est sans doute une bonne idée, mais je ne peux malheureusement pas modifier le type de données qui m'est fournit.
Merci de vos remarques en tout cas. Je me dirige à priori vers l'utilisation d'ID explicite.
