Структура данных, в которой можно быстро читать и удалять элементы из середины
Я желаю найти индексируемую структуру данных для которой будут быстро выполняться следующие операции для произвольного индекса i:
- Удаление:
del struct_obj[i] - Изменение:
struct_obj[i] = value - Чтение:
var = struct_obj[i]
То есть эта структура по своему "интерфейсу" должна примерно соответствовать структуре list из питона, но при этом иметь возможность быстрого удаления из середины. Взамен я готов пожертвовать скоростью чтения и изменения, а также вообще возможностью добавления новых элементов.
Пример работы структуры:
a = struct([3, 2, 4, 1, 5])
a[2] = 0 # a: [3, 2, 0, 1, 5]
b = a[3] # a: [3, 2, 0, 1, 5], b: 1
del a[1] # a: [3, 0, 1, 5]
a[3] = 1 # a: [3, 0, 1, 1]
Хранить в этой структуре я планирую 32-битные целые числа (-10^9 <= a[i] <= 10^9).
Реальной задачей, в которой такая структура может быть полезна, является классическая "считалка на выбывание": в кольце стоят N детей, пронумерованных по часовой стрелке от 1 до N. После этого из круга выходит каждый K-тый ребенок, в каком порядке они все выйдут?
Пример для задачи: N = 5, K = 3, ответ: 3, 1, 5, 2, 4.
Я знаю, что в качестве структуры мне подходит декартово дерево по неявному ключу, которое с точки зрения интерфейса взаимодействия очень похоже на динамический массив, но с логарифмической сложностью всех основных операций.
Я хочу узнать, есть ли более эффективные/простые в реализации структуры данных, отвечающие моим требованиям.
При этом я понимаю, что питон - это как раз тот язык, в котором не пишутся велосипеды на каждый чих, а используются проверенные реализации практически для всего. Поэтому я прошу вас поделиться ссылками на готовые реализации структур, о которых вы напишете в своем ответе.
Ответы (1 шт):
Теоретически известно, что для операций Изменение и Чтение самая эффективная по времени реализация - это массив, для которого доступ по индексу - О(1). Даже для словарей все на много медленнее, так как по сути словарь это сначала поиск по значению ключа и только потом само чтение или изменение. А поиск по значению ключа - это всякие ухищрения, например, через отдельные индексы (как при реализации реляционных баз данных).
С другой стороны, известно, что для массивов операции Вставки и Удаления - наиболее медленные и трудоемкие, так как требуют смещения всех элементов после вставляемого/удаляемого, да еще и отслеживания размеров.
С третьей стороны для списков (не списков Python, а списков как Абстрактного Типа Данных) Поиск (и соответственно Изменение и Чтение) - крайне медленные операции, однако Удаление и Вставка - быстрые, т.е. все что надо - просто "перебросить" указатели. АТД-список можно реализовать не только через однонаправленные ссылки, но и через двунаправленные, еще больше ускорив Удаление и Вставку. Но не Поиск, Чтение, Изменение.
Любая другая реализация это в конечном итоге некий компромис между одним и вторым способом предатавления (Например список Python - отличный пример такого компромиса).
Неявное бинарное дерево - это отнюдь не универсальная структура, а структура для хранения упорядоченных данных. Т.е. "запаковав" данные в дерево, вы теряете некоторую информацию, например, порядок поступления данных. Это весьма частный случай общей задачи и его можно использовать только тогда, когда между значениями хранимым элементов можно ввести отношения "больше-меньше. (а вы не сказали, что вы собираетесь работать только с упорядоченными данными, значит - исходим из общего случая).
Все сказанное приводит к мысли, что нет и быть не может структуры для представления, изменения и доступа для универсальных данных. Поэтому в курсах, в которых рассматриваются структуры обычно очень усилино подчеркивается, что выбор структуры может быть осуществлен только в жесткой привязке к семантике предметной области и с учетом (вернее - взаимоучетом) алгоритмов дальнейшей обработки.
Что касается "готовых реализаций" - то они есть, хотя и не очень распространены, с моей точки зрения именно потому, что часто проще для конкретной, своей задачи написать реализацию самому, чем разбираться в чужом коде, написанным часто с академическими целями.
Тем не менее - если очень надо, попробуйте поискать вот тут, может что-то и попойдет:
https://treelib.readthedocs.io/en/latest/
https://gist.github.com/irachex/3922705
http://python.algorithmexamples.com/web/data_structures/binary_tree/treap.html
http://www.grantjenks.com/wiki/random/python_treap_implementation