Dans les arbres, il y a une méthode appelée contient qui retourne true si un élément est dans l'ensemble. Je suppose que cette méthode utilise une recherche binaire et ne pas itérale à travers tous les éléments de l'ordre croissant. Ai-je raison?
J'ai un arbre d'art contenant des objets d'une classe qui utilise deux variables d'instance de chaîne pour le distinguer des autres objets de la même classe. Je souhaite pouvoir créer une méthode qui recherche dans les arbres en comparant les objets deux variables d'instance (en utilisant des méthodes de cours) avec deux autres variables de chaîne et si elles sont égales, renvoyez l'élément. Si les variables d'instance sont inférieures à accéder au premier élément du sous-arbre de droite ou si elles sont plus grandes recherchées dans le sous-arbre de gauche, etc. Y a-t-il un moyen de faire cela?
Je sais que je pouvais simplement stocker les objets dans une arraylist et utiliser la recherche binaire pour trouver l'objet, mais cela ne serait pas aussi rapide que de rechercher le rayon.
5 Réponses :
Vous devez soit implémenter comparable sur votre objet, soit créer une classe de comparaison distincte que vous passez au moment de la construction du temps. Cela vous permet d'intervenir votre logique de comparaison personnalisée d'entrée et de laisser le Streetet faire son magasin / recherche optimisé.
Bien sûr, je vais mettre en œuvre comparable sur l'objet. C'est toute la raison pour laquelle j'utilise un ensemble de tri. Mais comment cela va-t-il renvoyer l'élément que je recherche?
Essayez Treemap au lieu de Arbreset.
Vous avez la réponse à propos de l'utilisation de comparable / comparable, mais je pensais que j'ajouterais que vous avez raison qui contient () fait une recherche binaire, bien que vous ne devriez pas avoir besoin de connaître ces détails
J'ai besoin de connaître ces détails car je veux choisir la méthode la plus efficace possible.
Vous ne devriez généralement pas connaître les détails de la mise en œuvre d'une implémentation particulière d'une interface dans la JDK. Vous ne pouvez pas garantir que ce sera toujours comme ça. C'est pourquoi c'est derrière une interface.
Mais dans ce cas, je ne savais pas si la recherche binaire a été utilisée ou une recherche séquentielle. Cela fait une grande différence.
@exent: Vous devriez examiner les garanties de performance que les collections JDK font. Par exemple, Treemap états "Cette implémentation fournit un journal garanti (n) Coût de temps pour le Contains de contient , obtenez , mettre et supprimer opérations ". C'est la durée de journalisation que vous souhaitez, pas de recherche binaire (la recherche binaire s'applique spécifiquement pour trier des structures à base d'index tels que des tableaux et des listes, pas des arbres).
@Colind Je pensais que c'était également appelé la recherche binaire de la méthode de recherche d'arbres que j'ai décrite.
@exent: L'arbre lui-même est une sorte d'arbre de recherche binaire. Je suppose que vous pourriez vous référer à la recherche de "recherche binaire", mais cela me semble légèrement bizarre depuis que lorsque vous recherchez, vous voyez simplement la structure déjà construite de l'arbre de manière très simple.
Plutôt que d'utiliser un pour le arbreset , vous pouvez stocker vos objets dans un Treemap TREEMAP FOO à chaque fois que vous souhaitez rechercher). définir s ne sont pas vraiment destinés à la recherche.
FOOKEY Exemple, FOOKEY serait une classe immuable simple qui contient simplement la chaîne s et est comparable < / code>. Trouver la valeur de FOO pour deux String S serait alors une question simple de Treeemap.get (nouveau fookyy (premier produit, second)) . Cela utilise bien sûr l'essai d'arbre que vous souhaitez trouver la valeur.
Cela ressemble à une excellente méthode. Merci.
Une chose que je me demandais est la raison pour laquelle vous souhaitez rechercher dans un ensemble de tri? Si vous souhaitez pouvoir itérer dans l'ordre ainsi que la recherche rapide, vous pouvez bénéficier de stocker vos objets dans deux structures de données distinctes. Une comme votre Aussi si les ressources de mémoire sont contraintes et que vos chaînes sont vraiment ce que différencier les objets, vous pouvez simplement implémenter triée hashmap hashcode () et égale () sur votre objet < code> foo et simplement les utiliser comme la clé et la valeur (comme hashmap FOO pour appeler le getter.
Le maintien de deux structures contenant les mêmes données est quelque chose que j'éviterais si possible, pas tellement à cause de la mémoire ou de la performance des coûts d'écriture aux deux, mais en raison de la nécessité d'assurer dans votre code que les deux structures sont maintenues à toutes les périodes. Cela dit, en utilisant un hashmap pour rechercher est certainement préférable. L'OP n'a pas dit pourquoi ils avaient besoin d'une structure triée, alors peut-être qu'elles ne le font pas et ne pensaient simplement que ce serait le plus efficace.
set.tailSet(obj).first(); does what you want.
Comment connaissez-vous la recherche binaire dans un
ArrayList n'est pas aussi rapide? As-tu essayé?Je veux dire passer les éléments de l'arbre à une nouvelle arrayliste à chaque fois que je dois rechercher un élément et le retourner est lent.
Ah, oui, cela serait certainement très lent. Mais si vous construisez d'abord l'ensemble, puis recherchez-la plusieurs fois, puis le tri et la recherche binaire sur une arrayliste peut être assez rapide.
Et si une variable d'instance est supérieure à sa contrepartie et que l'autre est inférieure à sa contrepartie? Comment cela devrait-il trier?
@Carl Manaster: Les objets sont triés d'abord par l'une des cordes, puis l'autre. Tout comme une liste de noms serait trié d'abord sur le nom de famille, puis le prénom.