TreeMap и итераторы
От: f95.2  
Дата: 18.05.20 19:04
Оценка:
Добрый вечер.

Я хочу взять сбалансированное двоичное дерево, и делать с ним вот какие вещи:
1. Найти элемент по ключу, и, если элемент имеет "плохое" значение, то заменить его.
2. Найти элемент по ключу, и заменить значение этого элемента и парочки соседей с каждой стороны.

Вроде бы не должно быть проблем:
В первом случае находим элемент, запоминаем указатель/итератор и с ним работаем. Т.е. тут надо сделать один поиск.
Во втором — также находим элемент, запоминаем указатель/итератор, после чего по стандартному алгориму обход дерева находим соседей.

В джаве есть встроенное сбалансированное дерево TreeMap, но я не вижу у него подходящих методов.
Поиск по ключу есть (get/replace), но он возвращает значение. Чтобы заменить элемент в дереве, нужно делать еще один поиск.
Также вроде бы нет возможности взять соседний элемент, надо делать еще один поиск.
Да, в худшем случае взятие соседнего элемента имеет логарифмическую сложность, как и поиск по ключу,
но ведь далеко не каждый случай худший.

Я просто не вижу нужных методов, или их действительно нет по какой-то причине?
Re: TreeMap и итераторы
От: bzig  
Дата: 18.05.20 19:55
Оценка:
F2>Поиск по ключу есть (get/replace), но он возвращает значение. Чтобы заменить элемент в дереве, нужно делать еще один поиск.

merge — в любом Map теперь есть


F2>Я просто не вижу нужных методов, или их действительно нет по какой-то причине?


TreeMap реализует интерфейс https://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html, там есть нужные методы
Re[2]: TreeMap и итераторы
От: f95.2  
Дата: 18.05.20 21:04
Оценка:
Здравствуйте, bzig, Вы писали:

B>merge — в любом Map теперь есть

Спасибо. Не заметил его

B>TreeMap реализует интерфейс https://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html, там есть нужные методы

И что это за методы?
Там есть пачка методов, которые возвращают Map.Entry — но от этой entry нет никакой навигации.
Еще есть ceilingEntry/floorEntry, но они принимают значение ключа, а не итератор, а значит, делают обычный логарифмический поиск.
Re[3]: TreeMap и итераторы
От: PZI  
Дата: 18.05.20 21:32
Оценка:
Здравствуйте, f95.2, Вы писали:

F2>делают обычный логарифмический поиск.


А может и не делают
Re: TreeMap и итераторы
От: · Великобритания  
Дата: 18.05.20 22:18
Оценка:
Здравствуйте, f95.2, Вы писали:

f> Я хочу взять сбалансированное двоичное дерево, и делать с ним вот какие вещи:

А дешевые добавления|удаления эл-тов тебе тоже нужны?

f> 1. Найти элемент по ключу, и, если элемент имеет "плохое" значение, то заменить его.

f> 2. Найти элемент по ключу, и заменить значение этого элемента и парочки соседей с каждой стороны.

f> Вроде бы не должно быть проблем:

f> В первом случае находим элемент, запоминаем указатель/итератор и с ним работаем. Т.е. тут надо сделать один поиск.
Это вроде просто floorEntry(key).setValue(newVal)

f> Во втором — также находим элемент, запоминаем указатель/итератор, после чего по стандартному алгориму обход дерева находим соседей.

Если я правильно понял, можно найти интервал и его обработать: subMap(key-1, true, key+1, true)
avalon/2.0.6
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[4]: TreeMap и итераторы
От: · Великобритания  
Дата: 18.05.20 22:20
Оценка:
Здравствуйте, PZI, Вы писали:

PZI> F2>делают обычный логарифмический поиск.

PZI> А может и не делают
Делают. Впрочем логарифм очень маленький... на перформанс может и не повлиять.
avalon/2.0.6
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[5]: TreeMap и итераторы
От: PZI  
Дата: 18.05.20 22:41
Оценка:
Здравствуйте, ·, Вы писали:

·>Делают. Впрочем логарифм очень маленький... на перформанс может и не повлиять.


Ну, я про то, что поиск идет не по значениям ключей. И сложность там вроде О(1) в итоге, не логарифм.
Давно я правда этими глупостями не занимался, может что и забыл.
Re[3]: TreeMap и итераторы
От: bzig  
Дата: 19.05.20 01:49
Оценка:
F2>И что это за методы?

Там есть tail/head, так что в одну сторону можно получить итерацию. В обе стороны — не вынесено в публичный интерфейс.

Так то у них есть непубличный метод getEntry, который возвращает непубличный TreeMap.Entry, а не Map.Entry. И есть пара непубличных методов successor/predecessor, который от этого TreeMap.Entry могут вперёд и назад ходить. Если прямо невтерпёж как эти методы нужны, то можно или через reflection их вызывать, но этот способ грозят уже окончательно убрать в будущих версиях или откопировать TreeMap целиком к себе и сделать методы публичными.
Re: TreeMap и итераторы
От: vsb Казахстан  
Дата: 19.05.20 07:29
Оценка:
Здравствуйте, f95.2, Вы писали:

F2>Я хочу взять сбалансированное двоичное дерево, и делать с ним вот какие вещи:

F2>1. Найти элемент по ключу, и, если элемент имеет "плохое" значение, то заменить его.

Map.get(key), Map.put(key, value)

F2>2. Найти элемент по ключу


Map.get(key)

F2>и заменить значение этого элемента


Map.put(key, value)

F2>и парочки соседей с каждой стороны.


NavigableMap.lowerKey(key), NavigableMap.higherKey(key), потом Map.put(key, value).
Re[6]: TreeMap и итераторы
От: · Великобритания  
Дата: 19.05.20 22:05
Оценка:
Здравствуйте, PZI, Вы писали:

PZI> ·>Делают. Впрочем логарифм очень маленький... на перформанс может и не повлиять.

PZI> Ну, я про то, что поиск идет не по значениям ключей. И сложность там вроде О(1) в итоге, не логарифм.
Ну методы берут на вход значение ключа, кроме этого там просто не по чему искать.

PZI> Давно я правда этими глупостями не занимался, может что и забыл.

Глупости, конечно. Вызов дважды (да хоть десять раз!) метода O(log(n)) имеет сложность O(10*log(n)) == O(log(n)) всё равно.
avalon/2.0.6
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[7]: TreeMap и итераторы
От: PZI  
Дата: 20.05.20 09:04
Оценка:
Здравствуйте, ·, Вы писали:

·>Ну методы берут на вход значение ключа, кроме этого там просто не по чему искать.

И начинают искать со сложностью O(log(n)) по всей мапе, да? И именно по значению ключа, а не "ищут" бакет по значению хеша ключа, да?
Или мы про ботаников-идиотов, которые заморачиваются со сложностью на мапе, но делают так, чтоб у них ключи возвращали одинаковый хеш?
Ну и почему ты решил, что там будет именно O(log(n)), а не O(n) тогда? Всегда ли жаба искала по бакету двоичным поиском?
В общем я думаю ты прекрасно понял о чем я, буквоедством заниматься — так себе заниятие.


PZI>> Давно я правда этими глупостями не занимался, может что и забыл.

·>Глупости, конечно. Вызов дважды (да хоть десять раз!) метода O(log(n)) имеет сложность O(10*log(n)) == O(log(n)) всё равно.

Я не про это.
Re[8]: TreeMap и итераторы
От: · Великобритания  
Дата: 20.05.20 13:21
Оценка:
Здравствуйте, PZI, Вы писали:

PZI> ·>Ну методы берут на вход значение ключа, кроме этого там просто не по чему искать.

PZI> И начинают искать со сложностью O(log(n)) по всей мапе, да? И именно по значению ключа, а не "ищут" бакет по значению хеша ключа, да?
В сабже — TreeMap, там нет никаких бакетов и хешей. Т.е. таки да, O(log(n)) по всей мапе. Или я что-то не знаю.

PZI> В общем я думаю ты прекрасно понял о чем я, буквоедством заниматься — так себе заниятие.

В том-то и дело, что не понял.
avalon/2.0.6
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[9]: TreeMap и итераторы
От: PZI  
Дата: 20.05.20 14:50
Оценка:
Здравствуйте, ·, Вы писали:

·>В сабже — TreeMap, там нет никаких бакетов и хешей. Т.е. таки да, O(log(n)) по всей мапе. Или я что-то не знаю.

офак, да. Что-то у меня хешмап на уме... Соррян, был не прав

·>В том-то и дело, что не понял.

да, мой косяк.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.