Как бы вы реализовали OrderedDict — упорядоченый словарь? Структура данных, которая бы поддерживала операции словаря (или хэш таблицы) над парами ключ-значение, но также хранила бы и поддерживала их упорядоченность?
- получить значение по ключу
- убрать из структуры по ключу
- вставка в любое место новой пары (ключ-значение)
- найти место пары по ключу
Мне начинает казаться, что такой структуры, которая бы все это поддерживала более-менее эффективно (не за линию) просто нет. Как вы думаете?
Что еще за вставка в любое место новой пары? А чем не угодили деревья и списки с пропусками?
В деревьях и списках со вставками все отсортированно. А здесь нет.
Ааа, понял. Можно делать так: задавать позиции, как ключи в дереве, но позиции делать не реальные, а через промежуток. То есть 1-1, 2-10, 3-30 и т.д. Причем промежуток задавать в зависимости от количества элементов в дереве. В соседнем дереве соответственно хранить эту позицию. Раз в n (тоже зависит от количества элементов) запросов проводить перебалансировку дерева, то есть переназначать позиции, чтобы сохранять пропуски адекватными. Итого можно делать вставку в любое место. для этого нужно найти нужные промежуток и задать его середину в качестве ключа для нового элемента. Вроде все получается и амортизационно работает за O(log n)
Интересная идея. А можно по-подробнее про "позиции с промежутками 1-1б 2-10 и 3-30"? Или имелось ввиду "1-10, 11-20, 21-30"?
Я имел ввиду делать так, чтобы после перебалансировки сохранялся такой инвариант: возможность вставки между соседними элементами в дереве еще x элементов. Похоже, что x растет очень быстро, не могу с ходу сказать, чему оно будет равно. Типа пусть у нас есть дерево с k вершинами. Зададим между ними промежутки по, например, 16 позиций, тогда можно бесплатно (за O(log k)) вставить между любыми двумя элементами изначального дерева еще по 4 элемента. Если промежуток заполнился, то придется перестраивать дерево, поэтому нужно подумать, достаточно ли 16 для текущего размера дерева. Как вариант промежутки можно делать не целыми, тогда вставить можно будет больше без потери свойств, но потом все равно перестраивать из-за потерь точности.
Получается, что мы имеем соотношения:
ключ -> значениеключ -> позицияпозиция -> ключБерём три map'a, задача решена =)
upd. В данном случае это не верно)
А когда идет вставка новой пары в середину, то у половины пар меняется позиция.
Значит я неправильно понял, извиняюсь.
Но чем тогда не подходит декартово дерево + мэпы?
Порядок пар произвольный — неотсортированный. Не знаю как держать даже произвольно упорядоченный массив с нелинейными поиском и вставкой.
Неявное ДД позволяет выполнять вставку элемента в массив за логарифм. Если возьмём ещё мэп, хранящий по ключу указатель на соответствующую вершину в ДД, получим то, что надо. Разве нет?
если у вас есть указатель на вершину в неявном ДД, то можно узнать его позицию за логарифм? Я так понимаю, поднимаясь по указателю на родителя?
Ну если у меня есть указатель на вершину, то я могу узнать любую информацию про эту вершину, которую несёт в себе ДД =)
А потом типа храним родителя и когда поднимаемся вычисляем позицию. Замечательно)))
А что значит "найти место пары по ключу", если после произвольной вставки ("вставка в любое место новой пары (ключ-значение)") для нашей пары теперь может существовать более 1 позиции?
Позиция одна, но она может меняться от других вставок перед парой, например.
Всем спасибо за ответы :)
Сейчас нужно понять, стоит ли вообще ввязываться в написание такой фигни, и бенчмаркать на каких размеров это реально быстрее линейных проходов :)
А чем не подойдет любое балансированное дерево + хэш-таблица?
Хэш-Таблица по ключу дает значение + указатель на вершину в дереве. В дереве в каждой вершине хранится величина поддерева, вершины там лежат в произвольном порядке ключей (ну и там указатели на предка и сыновей).
Итого, по запросам:
1. Идем в хэш-таблицу O(1).
2. Из хэш-таблицы находим где висит вершина в дереве. Удаляем из хэш-таблицы и дерева O(logN).
3. В дереве ищем куда вставить вершину. Вставляем в дерево и хэш-таблицу O(logN).
4. По хэш-таблице находим где висит веришина в дереве. Поднимаемся по дереву, попутно накапливая сумму размеров поддеревьев слева O(logN).
Ну, тут же еще можно и по номеру получать пару (ключ,значение), например.
Это все вроде работает в предположении, что все ключи разные (если одинаковые, возможно, тоже можно разрулить).
Верно ли я понял условие задачи? Нигде ли я не накосячил?
Да, кажется MrDindows написал такое же выше с Декарткой :)
Да, вроде то же самое, только с чуть другими структурами. Не заметил — не обновил страницу перед тем как запостить свое решение.