Вопрос по структурам данных. Кто нибудь знает или может быть видел где нибудь структуру, позволяющую реализовать массив элементов, с возможностью быстрой вставки (добавления) и удаления элемента в любом месте массива и с возможностью быстрого доступа по индексу за время О(log2(n)), или быстрее? Естественно, структура должна быть самобалансирующейся за такое же время или быстрее.

Связные списки. Индексированные списки. Деревья.

В большинстве книжек в конце главы посвяшенной вашему вопросу есть что-то типа: "Реализация очереди/списка на базе массива". Да и в интернете полно примеров. В общем случае принципиальное отличие только выделении/отдаче памяти - в при добавлении элемента память не выделяется а элемент записывается по определенному индексу в массиве. Вся память выделяется на этапе инициализации.

Это сообщение отредактировал(а) Predator_2004 - 1.12.2010, 22:18

Доступ к элементам списка - за О(n) операций, деревья не поддерживают вставку по произвольному индексу, только по элементу. При чем тут "Реализация очереди/списка на базе массива", вообще не пойму...

А-а-а деревья!! Деревья - частный случай графов, а альтернативное представление графов - матрица смежности (двумерный массив).

Деревья не подходят, я же написал...

Видимо я совсем вымотался и плохо соображаю. Переформулируйте пожалуйста вопрос, так чтобы он содержал собственно какие структуры вы имеете ввиду, и все требования.

Однако... Хорошо. Нам нужна совершенно новая, нетипичная структура данных, которая бы обладала преимуществами как списка, так и обыкновенного массива. А именно, быстрый доступ по индексу (как у обычного массива), и быстрая вставка/удаление (как у списка). Список не подходит, т.к. имеет медленный доступ по индексу, а обыкновенный массив не подходит, т.к. при удалении элемента, скажем, из середины массива, требует сдвиг всех остальных элементов, что очень долго...

Ну так линейный массив плюс кластеризованный индекс. Это же ещё в DBF/NDX было реализовано... только на диске - а ты организуй в памяти.
Недостатки: увеличенный расход памяти (возможно наличие неиспользуемых блоков в массиве данных), необходимость периодического сжатия массива данных и перестроения массива индексов. Но зато вставка в произвольное место и поиск O(log2(N)) - как просили. Плюс можно, как в NTFS, вести битовую карту использования элементов в массиве - чтобы избегать быстрого распухания массива данных и частой необходимости сжимать его.
А если размер элементов массива невелик - то просто кластерное хранение. Правда, тогда и вставка будет как поиск - О(log2(N)), но зато не нужен массив-индекс.

Это сообщение отредактировал(а) Akina - 1.12.2010, 23:22

T42, 

Как раз таки массив можно реализовать поверх дерева



Полностью статья Декартовое дерево

Мне почему-то кажется, что задача должна решаться с привязкой к языку (языки ведь по-разному работают с паматью). Да и к задаче.

В общем же виде, у меня был такой вариант:

Нужен был "быстрый" массив с небольшим максимальным количеством членов, которые только могли быть добавлены за время работы программы. Я сделал два массива: один со значениями и еще один Boolean того же размера. При удалении члена, соответствуюшее Boolean значение менялось на False, а размер массива оставался прежним. Работало быстро.

Это сообщение отредактировал(а) _Y_ - 2.12.2010, 10:00

Я об этом говорил:

Всем большое спасибо за предложенные варианты. Решение вопроса находится в области деревьев с неявными индексами (ключами). Ближе всех оказался pathfinder, статья про декартовое дерево содержит один из вариантов решения задачи.

У меня было даже проще, чем ты описал. Т.к. количество элементов было небольшим, поиск "свободных" ячеек не производился. Новые элементы просто дописывались в хвост; при этом размер массива задавался заранее с запасом и имелся указатель на следующий элемент для записи. Ничего быстрее придумать не удалось.

А сколько дополнительной памяти автор готов пожертвовать для реализации этой структуры? Массив - самая экономная структура: только данные иду сплошным блоком в памяти. Списки, в зависимости от платформы ещё требуют один или два указателя (а это 4 или 8 байт) на каждый элемент. 

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

для добавления элемента он дописывается в конец массива, память выделяется блоками. - запись моментальна, но нужно ещё модифицировать дерево. 
для поиска - поиск по двоичному дереву. 
удаление - то же самое. Но физически элемент будет находиться в памяти, поэтому нужен ещё один массив индексов удалённых элементов. 
 из недостатков - если память забивается, или идёт очень интенсивные и равные потоки удаление -> добавление, то будет требоваться регулярная чистка и реиндексация, во время которых работа невозможна. 
Это для однопоточной работы.

короче есть куча нюансов:

одно или многопоточная реализация?
масштабируемость алгоритма в случае многопоточности.
величина (добавленные - удалённые) делить на (добавленные + удалённые) в единицу времени
допустимые затраты памяти.
если объём данных выходит за пределы ОЗУ, какой процент сдампленных на жёсткий диск данных.
и.т.п.
потому что какая бы ни была реализация, есть сильные и слабые стороны.