Сохраняющая ранг структура данных, отличная от std :: vector?
Я столкнулся с приложением, в котором мне нужно спроектировать контейнер, который имеет произвольный доступ (или, по крайней мере, лучше, чем O (n)), имеет недорогие (O (1)) вставки и удаления, и сохраняет данные в соответствии с порядком (рангами). ) указано при вставке.
Например, если у меня есть следующий массив:
[2, 9, 10, 3, 4, 6]
Я могу позвонить удалить по индексу 2 удалить 10 и я также могу позвонить вставить в индекс 1, вставив 13.
После этих двух операций у меня будет:
[2, 13, 9, 3, 4, 6]
Числа хранятся в последовательности, и для операций вставки / удаления требуется индексный параметр, чтобы указать, куда нужно вставить номер или какой номер следует удалить.
У меня вопрос: какие структуры данных, помимо связанного списка и вектора, могут поддерживать что-то подобное? Я склоняюсь к отвал который отдает приоритет следующему доступному индексу. Но я видел кое-что о Fusion Tree быть полезным (но больше в теоретическом смысле).
Какие структуры данных дадут мне наиболее оптимальное время работы при сохранении потребления памяти? Я играл с хеш-таблицей, сохраняющей порядок вставки, но до сих пор она не удалась.
Причина, по которой я выбрасываю использование std :: vector прямо, заключается в том, что я должен создать что-то, что превосходит вектор в терминах этих основных операций. Размер контейнера может вырасти до сотен тысяч элементов, поэтому о сдвигах в std :: vector не может быть и речи. Те же самые проблемные строки со связанным списком (даже если он связан дважды), при его переходе к заданному индексу в худшем случае потребовалось бы O (n / 2), которое округляется до O (n).
Я думал о двойном связанном списке, который содержал указатели «Голова», «Хвост» и «Средний», но я чувствовал, что это будет не намного лучше.
Решение
В основном, чтобы иметь возможность вставлять и удалять в произвольной позиции, вы можете использовать связанные списки. Они позволяют O (1) вставить / удалить, но только при условии, что вы уже нашли позицию в списке, куда вставить. Вы можете вставить «после заданного элемента» (то есть, учитывая указатель на элемент), но вы не можете так же эффективно вставить «по заданному индексу».
Чтобы иметь возможность вставлять и удалять элемент по его индексу, вам потребуется более продвинутая структура данных. Существуют как минимум две такие структуры, о которых я знаю.
Один веревка структура, которая доступна в некоторых расширениях C ++ (SGI STL, или в GCC через #include <ext/rope>). Это позволяет для O (log N) вставить / удалить в произвольной позиции.
Другой структурой, допускающей вставку / удаление O (log N), является неявная цепочка (неявное декартово дерево), некоторую информацию можно найти по адресу http://codeforces.com/blog/entry/3767, Treap с неявными ключами или же https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.
Неявный treap также может быть изменен, чтобы позволить находить в нем минимальное значение (а также поддерживать гораздо больше операций). Не уверен, может ли веревка справиться с этим.
UPDФактически, я предполагаю, что вы можете адаптировать любое O (log N) двоичное дерево поиска (такое как AVL или красно-черное дерево) для вашего запроса, преобразовав его в схему «неявного ключа». Общая схема такова.
Представьте себе двоичное дерево поиска, которое в каждый данный момент хранит последовательные числа 1, 2, …, N в качестве своих ключей (N — количество узлов в дереве). Каждый раз, когда мы меняем дерево (вставляем или удаляем узел), мы пересчитываем все сохраненные ключи, чтобы они по-прежнему имели значение от 1 до нового значения N. Это позволит вставлять / удалять в произвольной позиции, поскольку ключ теперь является позицией , но это потребует слишком много времени для обновления всех ключей.
Чтобы избежать этого, мы не будем явно хранить ключи в дереве. Вместо этого для каждого узла мы будем хранить количество узлов в его поддереве. В результате, всякий раз, когда мы идем от корня дерева вниз, мы можем отслеживать индекс (позицию) текущего узла — нам просто нужно сложить размеры поддеревьев, которые у нас есть слева. Это позволяет нам, учитывая К, найдите узел, который имеет индекс К (то есть, который является k-м в стандартном порядке дерева двоичного поиска), в O (log N) время. После этого мы можем выполнить вставку или удаление в этой позиции, используя стандартную процедуру двоичного дерева; нам просто нужно обновить размеры поддерева всех узлов, измененных во время обновления, но это легко сделать за O (1) времени на каждый измененный узел, поэтому общее время вставки или удаления будет O (log N), как в оригинальное двоичное дерево поиска.
Таким образом, этот подход позволяет вставлять / удалять / получать доступ к узлам в данной позиции за O (log N), используя любое O (log N) двоичное дерево поиска в качестве основы. Конечно, вы можете хранить дополнительную информацию («значения»), которая вам нужна, в узлах, и вы даже можете рассчитать минимум этих значений в дереве, просто сохранив минимальное значение поддерева каждого узла.
Тем не менее, вышеупомянутые трэп и веревка являются более продвинутыми, поскольку они также позволяют выполнять операции разделения и слияния (взятие подстроки / подмассива и объединение двух строк / массивов).
Другие решения
Рассмотрим список пропусков, который может реализовывать операции линейного ранга времени в своем «Индексируемый» изменение.
Для алгоритмов (псевдокод), см. Пропустить список поваренной книги, Пью.
Может случиться так, что к методу дерева двоичного поиска «неявный ключ», описанному выше @Petr, проще добраться, и он может даже работать лучше.