LINUX.ORG.RU

Реализуем ли на практике двухсвязный индексированный список?

 ,


0

1

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

Проблема в том, что из ассоциативных массивов элементы удаляются легко и просто, но при этом ассоциативные массивы нормально не итерируются по значению ключа, и в этом есть некая проблема на фоне того, что сам по себе доступ к элементам АМ осуществляется вычислением дорогостоящей хеш-функции.

Как себе представляю попытку решения проблемы созданием двухсвязного списка и к чему в итоге прихожу:

=== Есть служебная структура данных - перечислитель ===

Перечислитель представляет собой динамический массив смещений до элементов списка для быстрого поиска элемента за номером N.

Перечислитель скорее всего реализуется «на стеке», хотя мне ближе подход с malloc'ами статичных чанков и связыванием этих чанков через ещё одну надстроечную структуру. Проще говоря, такой вектор сам по себе должен быть динамически расширяемым. А как? Ну вот либо malloc'ом выделять чанк, а потом когда закончится - выделять новый и связывать со старым, либо... на этом мысль останавливается, потому что таки да, стек - это не абстракция, а тот же чанк в памяти и у стека тоже есть границы.

=== Есть собственно элементы двухсвязного списка ===

Каждый элемент списка содержит в себе: смещение предыдущего элемента, смещение до полезных данных элемента (payload), размер полезных данных, смещение последующего элемента, индекс текущего элемента.

=== Поиск элемента списка за номером N=3937 ===

Идём в служебную структуру данных - перечислитель, смотрим её заголовок:

ага, элементы с 0 по 2048-й - ищи по смещению такому-то. Не подходит, у нас 3937

следующая запись: элементы с 2048 до 4096 - ищи по смещению AUX_OFFSET

OK, нам подходит, у нас как раз N>2048 && N<4096

Вычисляем смещение до элемента перечислителя, содержащего указатель на элемент списка.

DLL_EL_OFFSET=QWORD(AUX_OFFSET+(3937-2048)*8)

Получили смещение до элемента списка - взяли данные, считав смещение до payload.

=== Удаление элемента из списка ===

Вот здесь мне нужно радостно удалить указатель на элемент списка из служебной структуры - и это становится некоторой проблемой, потому что для этого мне нужно циклически перекопировать всё содержимое вектора смещений до элементов списка, сдвинув всё его содержимое после удалённого значения несуществующего элемента вправо (в сторону меньших адресов). А это, мягко говоря, геморройноё занятие, потому что копирование памяти само по себе небыстрое, а тут мы имеем дело ещё и по сути со служебным списком - «динамическим массивом».

После непродолжительных раздумий напрашивается вывод о том, что дуализм двухсвязного списка, позволяющий представлять его и как просто вектор, и как список - невозможен без тупого перебора всех элементов списка вплоть до того. как будет найден нужный нам в рамках «парадигмы вектора» элемент N.

Т.е. списки хорошо итерируются влево-вправо, но вот как сделать так, чтобы можно было всё-таки находить просто элемент за номером N со скоростью O(1) (говоря не на птичьем языке - за время, «почти независящее» от этого самого N) ?

В общем, интересно есть ли библиотечные реализации двухсвязных списков, элементы которых можно быстро адресовать по индексу, делая минмальное количество телодвижений и уж точно не делая интенсивных переборов? Безусловно, поиск элемента N может быть более трудоёмким, нежели поиск 0-го, но хотелось, чтобы разница была минимальной, а не «равно максимизированной для всех», как это имеет место быть в случае ассоциативного массива.

P.S. И где-то там за горизонтом сам собой встаёт вопрос о том, а можно ли кешировать результат выполнения хеш-функции? Префиксным деревом, быть может?

★★★★★

Ответ на: комментарий от Sorcerer

B-tree? Всё равно же в итоге скорость поиска смещения до элемента будет весьма сильно отличаться от времени поиска в простом векторе...

И ещё деревьям нужно делать ребалансировку, тоже как-то нездорово.

Скопирую себе ссылку на всякий случай: https://github.com/c9s/Tree-Binary-XS/blob/master/lib/Tree/Binary/XS.pm

Вообще да, можно деревьями сделать...

DRVTiny ★★★★★ ()
Последнее исправление: DRVTiny (всего исправлений: 1)

Напиши, какую алгоритмическую сложность ты ожидаешь по основным операциям. Примерно как здесь здесь.

Crocodoom ★★★★★ ()
Ответ на: комментарий от DRVTiny

B+ tree. Но по памяти будет плюс, это да.

anonymous ()

Чем то напомнило списки с пропусками (Skip list)

Kuzz ★★★ ()

двухсвязный индексированный список

Называется deque

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

При удалении элементов из вектора он не перевыделяет память.

anonymous ()

skip-list, N-ary tree что-то в памяти всплывают :-) Да и списки это конечно здорово, но массивы всяко быстрее. Макс.быстрое удаление - просто отметить элемент удалённым.

а лучше делать как в СУБД - данные отдельно, ключи/индексы отдельно. По какому ключу надо итерироваться, по тому и идёшь.

А ещё лучше - берёшь сразу СУБД нужного масштаба и с ней работаешь не велосипедя :-)

MKuznetsov ★★★★★ ()

а нельзя просто помечать элемент, как удалённый, и реюзать эти элементы, а потом освобождать, например, весь пул, когда все элементы стали не нужны?

Iron_Bug ★★★★★ ()
Последнее исправление: Iron_Bug (всего исправлений: 2)

Откуда надо удалять элементы?

Только с начала и конца — std::deque

С любого места — любое дерево поиска с неявными ключами

f1u77y ★★★ ()
Ответ на: комментарий от Iron_Bug

Тогда для доступа по индексу будет нужна отдельная структура данных. Уж легче в явном виде удалять.

f1u77y ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.