Trouver la position de l'élément dans une Java TreeMap
Je suis en train de travailler avec un TreeMap de Chaînes TreeMap<String, String>
, et de l'utiliser pour mettre en œuvre un Dictionay de mots.
Je puis avoir une collection de fichiers, et voudrais créer une représentation de chaque fichier dans l'espace vectoriel (espace de mots) défini par le dictionnaire.
Chaque fichier doit avoir un vecteur représentant avec des propriétés suivantes:
- vecteur doit avoir la même taille que le dictionnaire
- pour chaque mot contenues dans le fichier, le vecteur doit avoir un 1 dans la position correspondant à la position du mot dans le dictionnaire
- pour chaque mot ne figurant pas dans le fichier, le vecteur doit avoir un -1 dans la position correspondant à la position du mot dans le dictionnaire
Donc, mon idée est d'utiliser un Vector<Boolean>
de mise en œuvre de ces vecteurs. (Ce mode de représentation des documents dans une collection est appelé Modèle Booléen - http://www.site.uottawa.ca/~diana/csi4107/L3.pdf)
Le problème, je suis confronté dans la procédure de création de ce vecteur est que j'ai besoin d'un moyen de trouver la position d'un mot dans le dictionnaire, quelque chose comme ceci:
String key;
int i = get_position_of_key_in_Treemap(key); <--- purely invented method...
1) existe t'il une méthode comme ça je peux l'utiliser sur un TreeMap?Si non pourriez-vous fournir un peu de code pour m'aider à mettre en œuvre par moi-même?
2) Est-il un itérateur sur TreeMap (c'est par ordre alphabétique sur les touches) que j'ai peut obtenir la position?
3)Finalement, dois-je utiliser une autre classe pour mettre en œuvre le dictionnaire?(Si vous pensez qu'avec les Arborescences je ne peux pas faire ce dont j'ai besoin) Si oui, lesquelles?
Merci d'avance.
LA PARTIE RAJOUTÉE:
Solution proposée par dasblinkenlight semble bien, mais le problème de la complexité (linéaire, avec la dimension de dictionnaire en raison de la copie de clés dans un tableau), et l'idée de le faire pour chaque fichier n'est pas acceptable.
Toutes les autres idées pour mes questions?
Oublié..C'est un TreeMap mais le deuxième paramètre de modèle n'est pas important pour la question que je me pose.Je vais le modifier.
OriginalL'auteur Matteo | 2011-12-14
Vous devez vous connecter pour publier un commentaire.
Une fois que vous avez construit votre arbre de carte, copie de ses triés clés dans un tableau, et l'utilisation
Tableaux.binarySearch
pour rechercher l'index en O(logN). Si vous avez besoin de la valeur, faire une recherche sur la carte originale, trop.Edit: c'est la façon dont vous la copie de clés dans un tableau
copy its sorted keys into an array
comment faites-vous cela?J'ai ajouté un exemple de la façon dont il peut être fait à la réponse.
thks, je vais vérifier ça tout de suite!
J'ai vu votre procédure, mais il a coûté N (copie de clés dans un tableau), et il n'est pas envisageable de le faire pour chaque fichier. Une autre idée? Existe t'il une méthode comme ça je peux l'utiliser sur un TreeMap? Est-il un itérateur sur TreeMap (c'est par ordre alphabétique sur les touches) que j'ai peut obtenir la position? Dois-je utiliser une autre classe pour mettre en œuvre le dictionnaire?
Vous n'avez pas besoin de le faire pour chaque fichier: vous le faites une fois pour votre dictionnaire
TreeMap
, et de garder ce tableau entre la lecture des fichiers. P. S. je suis désolé, je n'ai pas de découvrir ton post jusqu'à aujourd'hui, parce que vous n'avez pas mis @dasblinkenlight en face d'elle.OriginalL'auteur dasblinkenlight
Il n'y a pas mise en œuvre dans le JDK. Bien que
TreeMap
itère naturel de commande de clés, ses structures de données internes sont toutes basées sur les arbres et de ne pas les tableaux (rappelez-vous queMaps
ne commandez pas de touches, par définition, en dépit de l'usage très fréquent de cas).Cela dit, vous avez un choix à faire car il n'est pas possible d'avoir O(1) temps de calcul pour la comparaison des critères à la fois pour l'insertion dans le
Map
et laindexOf(key)
de calcul. Cela est dû au fait que l'ordre lexicographique n'est pas stable dans une structure de données mutable (par opposition à l'ordre d'insertion, par exemple). Un exemple: une fois que vous insérez la première paire clé-valeur (entrée) dans la carte, sa position sera toujours un. Toutefois, selon la deuxième clé insérée, la situation peut changer à mesure que la nouvelle clé peut être "plus" ou "plus bas" que celui de laMap
. Vous pouvez certainement mettre en maintenir et mettre à jour une liste indexée des touches lors de l'insertion de l'opération, mais vous aurez O(n log(n)) pour vos opérations d'insertion (besoin de commander à nouveau un tableau). Que pourrait être souhaitable ou non, selon votre accès aux données des modèles.ListOrderedMap
etLinkedMap
dans Apache Commons deux viennent proche de ce que vous avez besoin, mais s'appuient sur l'ordre d'insertion. Vous pouvez vérifier leur mise en œuvre et de développer votre propre solution du problème avec peu d'effort modéré, je crois (qui doit être juste une question de remplacement de laListOrderedMap
interne de sauvegarde de tableau avec une liste triée -TreeList
dans Apache Commons, par exemple).Vous pouvez également calculer l'index vous-même, en soustrayant le nombre d'éléments qui sont plus bas que la clé donnée (qui doit être plus rapide qu'une itération dans la liste de recherche de votre élément, dans le cas le plus fréquent - que vous n'êtes pas comparer n'importe quoi).
OriginalL'auteur lsoliveira
Une solution alternative serait d'utiliser
TreeMap
'sheadMap
méthode. Si le mot existe dans leTreeMap
, puis lesize()
de sa tête la carte est égal à l'indice du mot dans le dictionnaire. Il est peut-être un peu de gaspillage par rapport à mes autres questions, par.Ici est de savoir comment vous code en Java:
Ici est la sortie produite par le programme:
OriginalL'auteur dasblinkenlight
Je tiens à tous vous remercier pour les efforts que vous mettez dans la réponse à mes question, ils ont tous été très utile et en prenant le meilleur de chacun d'eux m'a fait venir jusqu'à la solution que j'ai réellement mis en œuvre dans mon projet.
Ce que je crois être la meilleure des réponses à mes questions sont les suivantes:
2) Il n'y a pas un Itérateur défini sur les Arborescences comme @Isoliveira sais:
et que j'ai trouvé dans cette SORTE de réponse Comment effectuer une itération sur un TreeMap?, la seule façon pour itérer sur les éléments d'un
Map
est d'utilisermap.entrySet()
et utiliser des Itérateurs définie surSet
(ou une autre classe avec les Itérateurs).3), Il est possible d'utiliser un
TreeMap
à mettre en œuvre Dictionnaire, mais ce sera garantuee une complexité de O(logN) pour trouver l'indice d'un mot (coût d'une recherche dans une Structure d'Arbre de Données).À l'aide d'un
HashMap
avec la même procédure à la place de complexité O(1).1) Il n'existe aucune méthode. La seule solution est de mettre en œuvre intégralement.
@Paul a déclaré
hypothèse de solution c'est qu'une fois que le Dictionnaire est créé, il ne sera pas modifié par la suite: de cette façon, la position d'un mot sera toujours le même.
Donner cette hypothèse, j'ai trouvé une solution qui permet de construire le Dictionnaire avec une complexité O(N) et après assure la possibilité d'obtenir l'indice d'un mot avec le constat de temps O(1) dans la recherche.
J'ai défini dans le Dictionnaire comme un
HashMap
comme ceci:String
représentant le mot figurant dans le DictionnaireObject
d'une classe crééeWordStruct
où
WordStruct
classe est définie comme ceci:et me permet de garder la mémoire de n'importe quel attribut j'aime en couple avec l'entrée de mot du Dictionnaire.
Maintenant je remplir dictionnaire itération sur tous les mots contenus dans tous les fichiers de ma collection:
Une fois HashMap est rempli dans l'ordre que j'ai utiliser la méthode indiquée par @dasblinkenlight à l'ordre une fois pour toutes avec la complexité O(N)
Et à partir de maintenant pour avoir la position d'index dans alphatebetic ordre du mot dans le dictionnaire de la seule chose nécessaire est de l'acces c'est variable
DictionaryPosition
:depuis word est savoir vous avez juste besoin d'y accéder et cela a des coûts à volume constant dans un
HashMap
.Merci encore et Iwish vous tous un Joyeux Noël!!
OriginalL'auteur Matteo
J'ai eu le même problème. Alors j'ai pris le code source de java.util.TreeMap et écrit IndexedTreeMap. Il implémente mon propre IndexedNavigableMap:
La mise en œuvre est basée sur la mise à jour du nœud de poids dans le rouge-noir arbre lorsqu'il est modifié. Le poids est le nombre de nœuds enfants en dessous d'un nœud donné, en plus de soi - même. Par exemple, lorsqu'un arbre est tourné vers la gauche:
updateWeight simplement les mises à jour des poids jusqu'à la racine:
Et quand nous avons besoin de trouver l'élément à l'index ici est la mise en œuvre qui utilise des pondérations:
Également très pratique de trouver l'indice d'une clé:
Je vais mettre en œuvre IndexedTreeSet bientôt, en attendant vous pouvez utiliser le jeu de clés de IndexedTreeMap.
Mise à jour: IndexedTreeSet est mis en œuvre maintenant.
Vous pouvez découvrir le résultat de ce travail à https://github.com/geniot/indexed-tree-map
OriginalL'auteur Vitaly Sazanovich
Je suis d'accord avec Isolvieira. Peut-être la meilleure approche serait d'utiliser une structure différente de TreeMap.
Toutefois, si vous voulez toujours aller avec le calcul de l'indice des clés, une solution serait de compter le nombre de touches sont plus bas que la clé que vous recherchez.
Voici un extrait de code:
OriginalL'auteur
Avez-vous pensé à rendre les valeurs dans votre
TreeMap
contenir la position de votre dictionnaire? Je suis à l'aide d'unBitSet
ici pour mon fichier de détails.Cela ne fonctionne pas presque aussi bien que mon autre idée ci-dessous.
Ici la construction de l'détails du fichier consiste en une seule recherche dans le
TreeMap
pour chaque mot dans le fichier.Si vous avez l'intention d'utiliser le
value
dans le dictionnaireTreeMap
pour quelque chose d'autre, vous pouvez toujours composer avec unInteger
.Ajouté
De penser à elle, si le
value
domaine de laMap
est réservé pour quelque chose, vous pouvez toujours utiliser les touches spéciales permettant de calculer leur propre position dans leMap
et à agir comme desString
s à des fins de comparaison.NB: Suppose qu'une fois que
getPosition()
a été appelé, le dictionnaire n'est pas changé.OriginalL'auteur OldCurmudgeon
Je vous suggère d'écrire un SkipList pour stocker votre dictionnaire, car cela offrira encore de O(log N) les recherches, l'insertion et le retrait tout en étant capable de fournir un index (arbre implémentations peuvent généralement pas de retour d'un index étant donné que les nœuds ne sais pas, et il y aura un coût pour les garder à jour). Malheureusement, l'implémentation java de ConcurrentSkipListMap ne fournit pas un indice, de sorte que vous devez mettre en place votre propre version.
Obtenir l'index d'un élément de O(log N), si vous voulait à la fois l'indice et la valeur sans en faire 2 recherches ensuite, vous devez renvoyer un objet wrapper tenant à la fois.
OriginalL'auteur Trevor Freeman