Эффективная структура данных для быстрого произвольного доступа, поиска, вставки и удаления

Question

Я ищу структуру данных (или структуры), которая позволила бы мне хранить упорядоченный список целых чисел, без дубликатов, с индексами и значениями в одном диапазоне.

Мне нужно четыре основные операции, чтобы быть эффективными, в грубом порядке важности:

1. взятие значения из заданного индекса
2. нахождение индекса заданного значения
3. вставка значения по заданному индексу
4. удаление значения по заданному индексу

Используя массив, у меня есть 1 в O (1), но 2 - это O (N), а вставка и удаление дорогие (я полагаю, O (N)).

Связанный список имеет O (1) вставку и удаление (если у вас есть узел), но 1 и 2 - O (N), что сводит на нет выгоды.

Я попытался сохранить два массива a [index] = value и b [value] = index, которые превращают 1 и 2 в O (1), но превращают 3 и 4 в еще более дорогостоящие операции.

Есть ли структура данных, лучше подходящая для этого?

Answer 1

Я бы использовал красно-черное дерево для сопоставления ключей со значениями. Это дает вам O (log (n)) для 1, 3, 4. Это также поддерживает ключи в отсортированном порядке.

Для 2 я бы использовал хеш-таблицу для сопоставления значений с ключами, что дает производительность O (1). Он также добавляет O (1) для поддержания обновленной хэш-таблицы при добавлении и удалении ключей в красно-черном дереве.

Answer 2

Как насчет использования отсортированного массива с двоичным поиском?

Вставка и удаление происходит медленно. но, учитывая тот факт, что данные представляют собой простые целые числа, их можно оптимизировать с помощью вызовов memcpy (), если вы используете C или C ++. Если вы знаете максимальный размер массива, вы можете даже избежать выделения памяти во время использования массива, поскольку вы можете предварительно выделить его до максимального размера.

«Лучший» подход зависит от того, сколько предметов вам нужно хранить и как часто вам нужно будет вставлять / удалять по сравнению с поиском. Если вы редко вставляете или удаляете отсортированный массив с O (1), доступ к значениям, безусловно, будет лучше, но если вы часто вставляете и удаляете вещи, двоичное дерево может быть лучше, чем массив. При достаточно малом n массив, скорее всего, превосходит дерево в любом случае.

Если размер хранилища имеет значение, массив также лучше, чем деревья. Деревьям также необходимо выделять память для каждого элемента, который они хранят, и накладные расходы на выделение памяти могут быть значительными, поскольку вы храните только небольшие значения (целые числа).

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

Answer 3

Использовать вектор для доступа к массиву.

Использование карты в качестве индекса поиска для индекса в векторе.

• при заданном индексе извлекает значение из вектора O (1)
• учитывая ключ, используйте карту, чтобы найти индекс значения. O (LNN)
• вставьте значение , нажмите на вектор O (1) амортизированный, вставьте индекс в карта O (lnN)
• удалить значение , удалить с карты O (lnN)

Answer 4

Я не знаю, какой язык вы используете, но если это Java, вы можете использовать LinkedHashMap или подобную коллекцию. Он обладает всеми преимуществами Списка и Карты, обеспечивает постоянное время для большинства операций и имеет объем памяти слона. :)

Если вы не используете Java, идея LinkedHashMap, вероятно, все еще подходит для используемой структуры данных для вашей проблемы.

Answer 5

Как добиться 2 с RB-деревьями? Мы можем заставить их считать своих детей при каждой операции вставки / удаления. Это не делает эти операции длятся значительно дольше. Тогда спуститься по дереву, чтобы найти i-й элемент, можно за время log n. Но я не вижу реализации этого метода в Java или STL.

Answer 6

Мне очень нравятся сбалансированные бинарные деревья. Иногда они медленнее, чем хеш-таблицы или другие структуры, но они гораздо более предсказуемы; они обычно O(log n) для всех операций. Я бы предложил использовать Красно-черное дерево или AVL дерево .

Answer 7

Как насчет Treemap? log (n) для описанных операций.

Answer 8

Если вы работаете в .NET, то в соответствии с документами MS http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

• SortedDictionary и SortedList оба имеют O (log n ) для извлечения
• SortedDictionary имеет O (log n ) для операций вставки и удаления, тогда как SortedList имеет O ( n ).

Два отличаются по использованию памяти и скорости вставки / удаления. SortedList использует меньше памяти, чем SortedDictionary. Если SortedList заполняется сразу из отсортированных данных, это быстрее, чем SortedDictionary. Так что это зависит от ситуации, которая действительно лучше для вас.

Кроме того, ваш аргумент для связанного списка на самом деле недействителен, поскольку для вставки это может быть O (1), но вам нужно пройти по списку, чтобы найти точку вставки, поэтому это действительно не так.