Структура данных с эффективными манипуляциями и поиском по ключу и индексу
Я ищу структуру данных с функциональностью, например. OrderedDictionary в.NET, то есть ассоциативная коллекция (то есть та, которая связывает ключ со значением), которая поддерживает порядок элементов (так же, как и обычный List делает).
Он должен иметь быстрый поиск по индексу и ключу. Он также должен иметь быструю операцию "добавления" (вставка нового элемента в конце) и быстрое удаление элементов с любым индексом (на основе индекса или ключа).
OrderedDictionary в.NET использует хеш-таблицу и массив для хранения своих элементов, если я не ошибаюсь. Следовательно, получение индекса на основе ключа (или наоборот) - это O(n), и, конечно, удаление элемента из середины массива - это O(n), плюс добавленный поиск индекса из ключ, если удалить ключом.
Мой вопрос: существует ли более эффективная структура данных, которая удовлетворяет моим условиям, или это действительно лучший вариант для меня?
4 ответа
Я думаю, что вы можете сделать это с двумя красно-черными деревьями: деревом поиска ключей для хранения ключей, упорядоченных функцией сравнения, и деревом поиска индексов, с ключами в произвольном порядке, как в списке. Каждый узел поиска по индексу должен иметь поле "размер" - красно-черное дерево может выполнять поиск по индексу, если поле "размер" включено в каждый узел. См., Например, реализацию RedBlackTreeSet в библиотеке C5 Generic Collection.
Каждая запись в дереве поиска ключей нуждается в указателе на соответствующую ему запись в дереве поиска индекса. Как и указатели левого и правого узлов, дерево поиска индекса будет нуждаться в родительском поле указателя, чтобы позволить Навигация сверху, а также сверху вниз.
Всего для каждого ключа требуется шесть указателей: обычные левый и правый указатели в обоих узлах, плюс указатель от узла-ключа-поиска на узел-индекса-поиска, а также указатель родителя в каждом из элементов поиска по индексу -nodes. Вам также понадобится указатель в каждом узле, чтобы указать на сохраненное значение.
Операции:
Append - Операция добавления вставит ключ в оба дерева - один раз в дерево поиска ключей, в положение, определенное функцией сравнения, и снова в крайнее правое положение дерева поиска индекса. Вставка в красно-черное дерево является логарифмической временной операцией.
Поиск по ключу - это делается в дереве поиска ключей, используя функцию сравнения, чтобы найти правильную позицию - O(log(n))
Поиск по индексу - это можно сделать в поле поиска по индексу, как указано выше - O(log(n))
Получить индекс из ключа - сначала ищите ключ в дереве поиска ключей O(log(n)). Следуйте указателю через дерево поиска по индексу. Следуйте указателям от родителей до корневого узла (O(log(n)) для сбалансированного дерева). Используйте поля 'size' на пути вверх, чтобы определить индекс ключа. - O(log(n)) в целом.
Удалить по индексу - поиск элемента в дереве поиска по индексу. Удалить из дерева поиска по индексу. Найдите найденный ключ в дереве поиска ключей. Удалить из дерева поиска ключей. Все операции O(log(n)), поэтому удаление - O(log(n)) в целом.
Удалить по ключу - используйте "Получить индекс из ключа", чтобы получить индекс ключа. Удалить по индексу из дерева поиска по индексу. Удалить по ключу из дерева поиска ключей. O(log(n)) в целом.
Эта структура также поддерживает вставку O (log (n)) в любую произвольную позицию, а не только в конце.
Расходы на хранение, очевидно, значительны, но остаются O(n). Временная сложность отвечает всем требованиям.
К сожалению, я не знаю ни о какой реализации этой структуры.
Обновление: мне приходит в голову, что вы можете объединить дерево с хеш-таблицей, чтобы получить O(1) поиск ключа. Вместо того, чтобы иметь два дерева, как я предлагал выше, используйте хеш-таблицу для поиска по ключам и сбалансированное дерево статистики заказов для поиска по позициям, как указано выше, но слоты в хеш-таблице содержат указатели на узлы сбалансированного дерева для выполнения поиска get-list-position-by-key. Поиск по ключевым словам теперь O(1), а все остальное остается в среднем O(ln(n)). Конечно, теперь вы получаете случайный штраф за повторное хеширование (как и в любой хеш-таблице).
OrderedDictionary соответствует вашим требованиям на самом деле.
Ваш анализ OrderedDictionary неверен. Это на самом деле O(1) для поиска на основе ключей и O(1) для индекса в соответствии с этим.
Даже простой анализ дает вам O(1) поиск по ключу или индексу. Массивы обеспечивают доступ O(1), а хэш-таблицы обеспечивают доступ O(1).
Вставить / удалить немного сложнее, но с учетом амортизированного анализа все равно O(1)
В статье утверждается, что это O (n) для вставки и удаления. По крайней мере, это не относится к вставке, поскольку амортизированный анализ позволяет просто увеличить "стоимость" вставки данного элемента с 1 до 2. При вставке элемента, требующего изменения размера массива, вторая половина стоимости используется для оплаты стоимость копирования. Окончательная вставка займет больше времени, но ее значение O(1) все еще амортизируется, и расхождение обнаруживается только в том случае, если вы измените размер массива, что маловероятно.
Может быть, вы найдете что-то интересное здесь в Библиотеке C5 Generic Collection для C# (со страницы 233)
Вы можете использовать сбалансированное бинарное дерево поиска, например, ссылку, просто для определения TreeNode вы должны добавить свои ключи, но проблема в том, что элемент не O(1), а O(log(n)) как по ключам, так и по индексу (на самом деле индекс не является частью TreeNode, относительно можно найти), но все операции O(log(n)) и является самым быстрым известным способом, основанным на методах сравнения.