LINUX.ORG.RU

Посоветуйте структуру данных


0

0

Нужно придумать БД с записями типа "ключ = значение", где ключи -- это строки, состоящие из фиксированного числа символов, значения -- обычные числа. Также нужно держать БД целиком в оперативной памяти (тут я что-то слышал про T-деревья). Операции на БД -- добавление, поиск.

Может кто-нибудь посоветует наиболее подходящую структуру данных? Скорость важна.


Если данных не много и добавление чаще поиска -- хеш-таблицы Поиск чаще добавления -- сбалансированные деревья

SQLite, по-моему, умеет работать в памяти, если в качестве файла указать :memory:

Dr_ZLO
()
Ответ на: комментарий от Dr_ZLO

> Если данных не много и добавление чаще поиска -- хеш-таблицы Поиск чаще добавления -- сбалансированные деревья

А вы слышали, что при хорошей хеш-функции сложность поиска в хэш-таблице O(1), а в сбалансированном дереве - O(log_2(n))?

ЗЫ: Для хэш-таблиц в худшем случае сложность поиска - O(N), но ЕМНИП это будет только в случае плохой хэш-функции.

ЗЗЫ: если структура изменяется достаточно редко, то вместо деревьев можно использовать отсортированные массимы и двоичный поиск.

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

В среднем сложность поиска в хеш-таблице при хорошей хеш-функции (n/размер_хеш_таблицы)/2

>в сбалансированном дереве - O(log_2(n))

в самом диком случае

Dr_ZLO
()
Ответ на: комментарий от Dr_ZLO

>В среднем сложность поиска в хеш-таблице при хорошей хеш-функции (n/размер_хеш_таблицы)/2

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

anonymous
()
Ответ на: комментарий от Dr_ZLO

> в самом диком случае

в самом типичном случае. В сбалансированном дереве большинство узлов -- листья и их приближенные

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

Хорошо, скажу по-другому: сложность поиска в avl не хуже log_2(n), rb 2*log_2(n) и в _любом_ случае нет провалов производительности как у хешей с O(n).

Dr_ZLO
()
Ответ на: комментарий от anonymous

> Гонево про O(1) - это если данных меньше, чем слотов.

А изменить размер таблицы тебе религия запрешает?

> С таким же успехом можно для индексирования выделить сразу массив размерностью, равной максимальному значению индекса, а потом гордо говорить, что в нем поиск O(1)

И в ряде случаев это будет хорошим решением.

Begemoth ★★★★★
()

кстати, нашел такую интересную структуру данных -- T-дерево:

http://en.wikipedia.org/wiki/T-tree

но с поиском ее реализации туго :(

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