Возврат элемента из TreeSet с помощью бинарного поиска

В TreeSet есть метод contains, который возвращает true, если элемент находится в наборе. Я предполагаю, что этот метод использует бинарный поиск и не перебирает все элементы в порядке возрастания. Я прав?

У меня есть TreeSet, содержащий объекты класса, который использует две переменные экземпляра String, чтобы отличать его от других объектов того же класса. Я хочу иметь возможность создать метод, который выполняет поиск в TreeSet, сравнивая объекты с двумя переменными экземпляра (конечно, используя методы get) с двумя другими строковыми переменными, и если они равны, возвращайте элемент. Если переменные экземпляра меньше, чем перейти к первому элементу в правом поддереве или если они больше, поиск в левом поддереве и т. д. Есть ли способ сделать это?

Я знаю, что могу просто хранить объекты в ArrayList и использовать бинарный поиск для поиска объекта, но это будет не так быстро, как простой поиск в TreeSet.


java arraylist binary-search treeset
person exent    schedule 05.04.2011    source источник
comment
Откуда вы знаете, что бинарный поиск в ArrayList не такой быстрый? Ты пытался?   -  person Fred Foo    schedule 06.04.2011
comment
Я имею в виду передачу элементов из TreeSet в новый ArrayList каждый раз, когда мне нужно искать элемент и возвращать его медленно.   -  person exent    schedule 06.04.2011
comment
ах, да, это определенно было бы очень медленно. Но если вы сначала создадите набор, а затем выполните поиск несколько раз, то сортировка и бинарный поиск ArrayList могут оказаться довольно быстрыми.   -  person Fred Foo    schedule 06.04.2011
comment
Что, если одна переменная экземпляра больше, чем ее аналог, а другая меньше, чем ее аналог? Как это должно быть?   -  person Carl Manaster    schedule 06.04.2011
comment
@Carl Manaster: объекты сортируются сначала по одной из строк, а затем по другой. Точно так же, как список имен будет отсортирован сначала по фамилии, а затем по имени.   -  person exent    schedule 06.04.2011

Ответы (5)


arrow_upward
6
arrow_downward

Вместо использования TreeSet вы можете хранить свои объекты в TreeMap<Foo, Foo> или TreeMap<FooKey, Foo> (если вы не можете легко создавать новый фактический Foo каждый раз, когда хотите выполнить поиск). Set на самом деле не предназначены для поиска.

Для примера FooKey FooKey будет простым неизменяемым классом, который просто содержит два String и является Comparable. Тогда найти значение Foo для двух String будет просто вопросом treeMap.get(new FooKey(firstString, secondString)). Это, конечно, использует обход дерева, который вы хотите найти значение.

person ColinD    schedule 05.04.2011
comment
Это похоже на отличный метод. Спасибо. - person exent; 06.04.2011

arrow_upward
15
arrow_downward 

set.tailSet(obj).first();

делает то, что вы хотите.

person greg    schedule 30.08.2011

arrow_upward
2
arrow_downward

Вы должны либо реализовать Comparable на своем объекте, либо создать отдельный класс Comparator, который вы передаете во время создания TreeSet. Это позволяет вам внедрить свою пользовательскую логику сравнения записей и позволить TreeSet выполнять свои оптимизированные функции хранения/поиска.

person Konstantin Komissarchik    schedule 05.04.2011
comment
Конечно, я собираюсь реализовать Comparable на объекте. Вот и вся причина, по которой я использую отсортированный набор. Но как это вернет элемент, который я ищу? - person exent; 06.04.2011
comment
Попробуйте TreeMap вместо TreeSet. - person Konstantin Komissarchik; 06.04.2011

arrow_upward
1
arrow_downward

Мне было интересно, почему вы хотите искать в отсортированном наборе? Если вы хотите иметь возможность выполнять итерации по порядку, а также быстро искать, вы можете извлечь выгоду из хранения ваших объектов в двух отдельных структурах данных. Один, как ваш SortedSet<Foo>, а затем еще и HashMap<FooKey,Foo>, похожий на то, что упоминал ColinD. Затем вы получаете поиск с постоянным временем вместо log (n) на TreeMap. У вас есть штраф за запись из-за необходимости записи в обе структуры и штраф за ресурсы памяти из-за наличия двух структур данных, но вы полностью оптимизировали свой доступ к данным.

Кроме того, если ресурсы памяти ограничены, а ваши строки действительно различают объекты, вы можете просто реализовать hashcode() и equals() на своем объекте Foo, а затем просто использовать их как ключ и значение (например, HashMap<Foo,Foo>). Предостережение заключается в том, что вы должны построить Foo для вызова геттера.

person Justin Waugh    schedule 06.04.2011
comment
Я бы по возможности избегал поддержки двух структур, содержащих одни и те же данные, не столько из-за затрат памяти или производительности на запись в обе, сколько из-за необходимости обеспечения в вашем коде того, чтобы обе структуры всегда синхронизировались. Тем не менее, использование HashMap для поиска, безусловно, предпочтительнее. ОП не сказал, зачем им нужна отсортированная структура, поэтому, возможно, они на самом деле этого не делают и просто подумали, что это будет наиболее эффективно. - person ColinD; 06.04.2011

arrow_upward
0
arrow_downward

Вы получили ответ об использовании сопоставимого/компаратора, но я подумал, что добавлю, что вы правы в том, что contains() выполняет двоичный поиск, хотя вам не нужно знать эти детали.

person Justin Waugh    schedule 05.04.2011
comment
Мне нужно знать эти детали, потому что я хочу выбрать наиболее эффективный из возможных методов. - person exent; 06.04.2011
comment
Как правило, вам не следует знать подробности того, как реализована та или иная реализация интерфейса в JDK. Вы не можете гарантировать, что так будет всегда. Вот почему он находится за интерфейсом. - person Justin Waugh; 06.04.2011
comment
Но в этом случае я не знал, использовался ли бинарный поиск или последовательный поиск. Это большая разница. - person exent; 06.04.2011
comment
@exent: вы должны посмотреть на гарантии производительности, которые дают коллекции JDK. Например, состояния TreeMap Эта реализация обеспечивает гарантированную стоимость log(n) времени для операций containsKey, get, put и remove. Вам нужно время log(n), а не бинарный поиск (бинарный поиск специально применяется к отсортированным структурам на основе индексов, таким как массивы и списки, а не к деревьям). - person ColinD; 06.04.2011
comment
@ColinD Я думал, что это также называется бинарным поиском для метода поиска по дереву, который я описал. - person exent; 06.04.2011
comment
@exent: само дерево представляет собой своего рода двоичное дерево поиска. Я думаю, вы могли бы назвать поиск в нем бинарным поиском, но мне это кажется немного странным, поскольку, когда вы ищете, вы просто пересекаете уже построенную структуру дерева очень прямолинейным образом. - person ColinD; 06.04.2011