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

Question

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

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

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

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

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

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

Является ли структура данных более подходящей для этого?

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

Howabout the Treemap? log (n) для описанных операций.

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

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

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

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