LINUX.ORG.RU

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


0

0

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

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


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

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

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

Dr_ZLO ()
Ответ на: Re: Посоветуйте структуру данных от Dr_ZLO

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

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

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

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

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

Begemoth ★★★★★ ()
Ответ на: Re: Посоветуйте структуру данных от Dr_ZLO

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

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

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

anonymous ()
Ответ на: Re: Посоветуйте структуру данных от dilmah

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

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

Dr_ZLO ()
Ответ на: Re: Посоветуйте структуру данных от anonymous

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

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

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

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

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

Begemoth ★★★★★ ()

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

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

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

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

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