De retour d'un élément à partir d'un TreeSet à l'aide de la recherche binaire

Dans TreeSet il existe une méthode appelée contient que renvoie la valeur true si un élément est dans le jeu. Je suppose que cette méthode utilise les binaires de recherche et de ne pas parcourir tous les éléments dans l'ordre croissant. Suis-je le droit?

J'ai un TreeSet qui contient les objets d'une classe qui utilise la Chaîne de deux variables d'instance pour le distinguer des autres objets de la même classe. Je veux être en mesure de créer une méthode qui permet de rechercher le TreeSet en comparant les objets de deux variables d'instance (à l'aide de méthodes get, bien sûr) avec les deux autres variables de type String et s'ils sont égaux, le retour de l'élément. Si les variables d'instance sont à moins d'aller vers le premier élément dans le sous-arbre droit ou s'ils sont supérieurs de recherche dans le sous-arbre gauche etc. Est-il un moyen de faire cela?

Je sais que je pourrais juste stocker les objets dans une liste de tableaux et d'utiliser les binaires de recherche pour trouver l'objet, mais ce ne serait pas aussi rapide que la simple recherche de la TreeSet.

Comment savez-vous de la recherche binaire dans un ArrayList n'est pas aussi rapide? Avez-vous essayé?
Je veux dire en passant les éléments de la TreeSet à une nouvelle liste de tableaux à chaque fois que je dois rechercher un élément et le retour c'est lent.
ah, oui, qui aurait certainement être très lent. Mais si vous construisez d'abord la définir, puis de rechercher à plusieurs reprises, le tri et le binaire de la recherche d'un ArrayList pourrait être assez rapide.
Que faire si une variable d'instance est plus grande que son homologue et l'autre est moins que son homologue? Comment devrait-tri?
Manaster: Les Objets sont triés en premier lieu par l'une des Chaînes, puis l'autre. Tout comme une liste de noms d'abord triées sur le nom puis le prénom.

OriginalL'auteur exent | 2011-04-05

  1. 6

    Plutôt que d'utiliser un TreeSet, vous pouvez stocker vos objets dans un TreeMap<Foo, Foo> ou TreeMap<FooKey, Foo> (si vous ne pouvez pas créer facilement un nouveau Foo chaque fois que vous voulez la recherche). Sets ne sont pas vraiment destinés à la recherche.

    Pour la FooKey exemple, FooKey serait une simple immuable classe qui contient simplement les deux Strings et est Comparable. Trouver la valeur de Foo pour deux Strings serait alors une simple question de treeMap.get(new FooKey(firstString, secondString)). Ce n'est bien sûr utiliser l'arbre transversal vous voulez trouver la valeur.

    Qui ressemble à une bonne méthode. Merci.

    OriginalL'auteur ColinD

  2. 14
    set.tailSet(obj).first();

    fait ce que vous voulez.

    OriginalL'auteur greg

  3. 2

    Vous devez soit mettre en œuvre Comparable sur votre objet ou de la création d'un Comparateur de classe que vous passez à l'époque TreeSet est construit. Cela vous permet de souligner votre entrée personnalisée logique de comparaison et de laisser le TreeSet ne optimisé de son magasin/search chose.

    Bien sûr, je vais mettre en œuvre Comparable sur l'Objet. C'est la raison pour laquelle je suis à l'aide d'un ensemble trié. Mais comment ce retour de l'élément, je suis à la recherche d'?
    Essayez de TreeMap au lieu de TreeSet.

    OriginalL'auteur Konstantin Komissarchik

  4. 1

    Une chose que je me demandais pourquoi vous souhaitez rechercher dans un ensemble trié? Si vous voulez être en mesure d'effectuer une itération dans l'ordre ainsi que de recherche rapidement, vous pourriez bénéficier de stocker vos objets dans deux structures de données. L'un comme votre SortedSet<Foo> et puis aussi un HashMap<FooKey,Foo> similaire à ce que ColinD mentionné. Ensuite, vous obtenez de la constante de temps des recherches au lieu de log(n) sur le TreeMap. Vous avez une réduction de peine d'avoir à écrire sur les deux structures, et une mémoire de ressources peine d'avoir les deux structures de données, mais vous avez optimisé votre accès aux données.

    Également si la mémoire les ressources sont limitées, et vos cordes sont vraiment ce qui différencient les objets, alors vous pouvez simplement mettre en œuvre hashcode() et equals() sur votre objet Foo puis il suffit d'utiliser à la fois comme la clé et la valeur (comme HashMap<Foo,Foo>. L'inconvénient, c'est que vous avez à construire une Foo à l'appel de la lecture.

    Le maintien de deux structures contenant les mêmes données est quelque chose que j'aimerais éviter si possible, pas tellement à cause de la mémoire ou les coûts de l'exécution de l'écriture à la fois, mais en raison de la nécessité d'assurer dans votre code que les deux structures sont conservées dans de synchronisation à tout moment. Cela dit, à l'aide d'un HashMap pour les recherches est certainement préférable. L'OP n'a pas dit pourquoi ils ont besoin d'un triées de la structure, donc peut-être qu'ils n'ont pas réellement et juste pensé que ce serait le plus efficace.

    OriginalL'auteur Justin Waugh

  5. 0

    Vous eu la réponse sur l'utilisation de comparables ou de comparaison, mais j'ai pensé que je dirais que vous êtes de droite qui contient() effectue une recherche binaire, bien que vous ne devriez pas besoin de connaître ces détails

    J'ai besoin de connaître ces détails, parce que je veux choisir la méthode la plus efficace possible.
    En général, vous ne devriez pas connaître les détails de la façon dont un particulier de la mise en œuvre d'une interface dans le JDK est mis en œuvre. Vous ne pouvez pas garantir qu'il en sera toujours ainsi. C'est pourquoi il est derrière une interface.
    Mais dans ce cas je ne sais pas si binaire de recherche ou de la recherche séquentielle. C'est une grande différence.
    Vous devriez regarder la performance garantit que le JDK collections. Par exemple, TreeMap états "Cette application offre la garantie log(n) coût du temps pour la containsKey, get, put et remove opérations". C'est le log(n) le temps que vous voulez, pas binaire de recherche (la recherche binaire s'applique spécifiquement aux triés fondé sur l'indice des structures comme des tableaux et des Listes, arbres).
    J'ai pensé qu'il était aussi appelé binaire de recherche pour l'arbre de recherche la méthode que j'ai décrite.

    OriginalL'auteur Justin Waugh