Der Rückkehr ein element aus einem TreeSet mit binärer Suche

In TreeSet gibt es eine Methode namens enthält, die true zurückgibt, wenn ein element in der Menge. Ich gehe davon aus, dass diese Methode verwendet binäre Suche und nicht die Iteration über alle Elemente in aufsteigender Reihenfolge. Bin ich im Recht?

Ich habe ein TreeSet mit Objekten einer Klasse verwendet zwei String-Instanz-Variablen zur Unterscheidung von anderen Objekten der gleichen Klasse. Ich möchte in der Lage sein, um eine Methode zu erstellen, dass die Suche nach dem TreeSet durch den Vergleich der Objekte zwei Instanzvariablen (mit get-Methoden natürlich) mit zwei anderen String-Variablen, und wenn Sie gleich sind, das element zurückgegeben werden. Wenn die Instanz-Variablen sind weniger als gehen auf das erste element im rechten Teilbaum oder wenn Sie größer sind, Suche im linken Teilbaum etc. Gibt es eine Möglichkeit, dies zu tun?

Ich weiß, ich könnte nur speichern der Objekte in einer ArrayList, und verwenden Sie die binäre Suche auf das Objekt, aber das wäre nicht so schnell, wie nur die Suche im TreeSet.

Wie wissen Sie, binäre Suche in einem ArrayList nicht so schnell? Haben Sie versucht,?
Ich meine der übergabe der Elemente aus dem TreeSet zu einer neuen ArrayList jedes mal muss ich auf die Suche nach einem element und gibt es zurück ist langsam.
ah, ja, das wäre auf jeden Fall sehr langsam. Aber wenn Sie zuerst bauen die setzen, dann suchen Sie es mehrere Male, dann Sortieren und Binär suchen eine ArrayList es könnte sich herausstellen, Recht schnell.
Was ist, wenn eine Instanz-variable ist größer als sein Gegenstück, und der andere ist weniger als sein Gegenstück? Wie soll das Sortieren?
Manaster: Die Objekte sortiert sind zunächst durch eine der Zeichenketten und dann die andere. Ebenso wie eine Liste der Namen würde zuerst einmal geordnet werden, auf den Nachnamen und dann den Vornamen.

InformationsquelleAutor exent | 2011-04-05

6

Anstatt mit einer TreeSet könnten Sie speichern Ihre Objekte in einer TreeMap<Foo, Foo> oder TreeMap<FooKey, Foo> (falls nicht einfach erstellen Sie eine neue tatsächliche Foo jedes mal, wenn Sie wollen, suchen). Sets sind nicht wirklich vorgesehen für die Suche.

Für die FooKey Beispiel FooKey wäre eine einfache, unveränderliche Klasse, die gerade enthält die beiden Strings und ist Comparable. Finden Sie den Wert von Foo für zwei Strings wäre dann eine einfache Frage der treeMap.get(new FooKey(firstString, secondString)). Dies hat natürlich den Baum traversal Sie wollen, um den Wert zu finden.
- Das sieht aus wie eine tolle Methode. Danke.
InformationsquelleAutor ColinD
14
```
set.tailSet(obj).first();
```
tut, was Sie wollen.

InformationsquelleAutor greg
2

Sollten Sie entweder implementieren Vergleichbar auf Ihr Objekt oder erstellen Sie eine separate Comparator-Klasse, die Sie übergeben, in der TreeSet wird gebaut. Dadurch können Sie wieder einwerfen Ihre benutzerdefinierte Eingabe-Vergleich-Logik und lassen Sie die TreeSet seine optimierte store/search Sache.
- Natürlich werde ich umsetzen Vergleichbar auf das Objekt. Das ist der ganze Grund, warum ich bin mit einem sortierten set. Aber wie wird diese Rückkehr das element, ich bin auf der Suche nach?
- Versuchen TreeMap statt TreeSet.
InformationsquelleAutor Konstantin Komissarchik
1

Eine Sache, die ich Frage mich, warum Sie möchten, um die Suche in einem sortierten set? Wenn Sie wollen, um in der Lage zu Durchlaufen, um auch als lookup-schnell profitieren Sie möglicherweise von der Speicherung Ihrer Objekte in zwei separate Daten-Strukturen. Man wie Ihr SortedSet<Foo> und dann auch ein HashMap<FooKey,Foo> ähnlich zu dem, was "ColinD" erwähnt. Dann erhalten Sie Konstante Zeit-lookups statt log(n) auf der TreeMap. Sie haben ein schreiben der Strafe des schreiben zu müssen, um beide Strukturen, und eine Speicher-Ressource Strafe müssen die zwei Daten-Strukturen, aber Sie haben vollständig optimiert Ihr Zugriff auf die Daten.

Auch, wenn der Speicher-Ressourcen eingeschränkt sind, und Ihre Saiten sind wirklich was unterscheiden die Objekte, dann können Sie einfach implementieren hashcode() und equals() auf Ihr Objekt Foo und dann benutzen Sie einfach als beide den Schlüssel und den Wert (wie HashMap<Foo,Foo>. Der Nachteil dort ist, dass Sie haben, um zu konstruieren, ein Foo Aufruf der getter.
- Die Aufrechterhaltung der beiden Strukturen die gleichen Daten enthält ist etwas, was ich vermeiden würde, wenn möglich, nicht so viel, weil der Speicher oder Leistung Kosten schriftlich an beide, aber wegen der Notwendigkeit der Gewährleistung in Ihrem code, dass beide Strukturen sind immer in sync zu allen Zeiten. Das heißt, mit einem HashMap für lookups ist sicherlich vorzuziehen. Der OP hat nicht gesagt, warum Sie brauchten, um eine sortierte Struktur, so dass man Sie eigentlich gar nicht und dachte nur, das wäre der effizienteste.
InformationsquelleAutor Justin Waugh
0

Hast du die Antwort über vergleichbare/Komparator, aber ich dachte, ich würde hinzufügen, dass Sie im Recht sind, dass contains() wird eine binäre Suche, allerdings sollten Sie nicht brauchen, um zu wissen, die details
- Ich muss wissen, diese details, weil ich wollen, wählen Sie die effektivste Methode möglich.
- Sie sollten in der Regel nicht wissen, die details, wie eine bestimmte Implementierung einer Schnittstelle in das JDK implementiert ist. Sie können nicht garantieren, dass es immer so sein wird. Deshalb ist es hinter einer Schnittstelle.
- Aber in diesem Fall wusste ich nicht, ob binäre Suche verwendet wurde oder sequentielle Suche. Das ist ein großer Unterschied.
- Sie sollten sich auf die performance garantiert, dass die JDK-collections machen. Zum Beispiel TreeMap Staaten "Diese Implementierung bietet garantierte log(n) Zeit Kosten für die containsKey, get, put und remove Operationen". Es ist log(n) Zeit, die Sie wollen, nicht binäre Suche (binary search gilt insbesondere bei sortierten index-basierten Strukturen wie arrays und Listen, nicht Bäume).
- Ich dachte, es war auch die sogenannte binäre Suche nach dem Baum-such-Methode, die ich beschrieben.
- Der Baum selbst ist eine Art von binären Suchbaum. Ich denke, man könnte verweisen auf die Suche, wie "binäre Suche", aber es scheint etwas komisch zu mir, seit Sie bei der Suche, du bist einfach nur durchqueren die bereits gebaute Struktur des Baumes in einer sehr straightfoward Art und Weise.
InformationsquelleAutor Justin Waugh

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.