Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
В зависимости от задач - нужны разные деревья [update] 17.04.06 12:58 Число просмотров: 2888
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 17.04.06 13:05 Количество правок: 1
|
> Насчёт деревьев, -- давно ведем с тобой эту дискуссию, ты
> не мог бы примерный код именно на Perl привести
> индексирования? Почему-то сишный пример, который ты мне
Если предполагается держать индекс в памяти, то самой дорогой операцией будет сравнение ключей и именно количество сравнений надо минимизировать. Для этого конечно отлично подойдут перловые хеши (если памяти много - минимум раза в три больше, чем нужно для хранения индексов), а если хочется деревьев, то насколько я знаю, самыми эффективными на данный момент являются RB-деревья (red-black trees). Самобалансирующиеся деревья бинарного поиска, гарантирующие логарифмическое время вставки/удаления/поиска для худшего случая.
http://en.wikipedia.org/wiki/Red_black_tree
Вот например его реализация
http://search.cpan.org/~bholzman/Tree-RedBlack-0.3/
Если же индекс предполагается хранить на диске (например он будет слишком большой), то самая дорогая операция - обмен с диском (чтение/запись кластера) и минимизировать надо количество обращений к диску. Здесь практически без вариантов B-Tree (дисковый хеш бывает, но рехеш - изменение размера хеша - ОЧЕНЬ дорогая операция, поэтому стоит его применять либо для статичных данных, либо сразу резервировать хеш-таблицу с огромным запасом). B-Tree тоже гарантирует логарифмическое количество обращений к диску для худшего случая для всех основных "древесных" операций.
http://en.wikipedia.org/wiki/B-tree
http://perl.plover.com/BTree/
> давал и универские конспекты по этому поводу не помогают
> мне реализовать все это на Perl. Наверное, я тупой %).
Хотя если ты действительно хочешь сделать эффективный поиск, то я бы предпочел делать его на C, а перлу отдать биндинги. Насколько я помню стандартная перловская библиотека нормально биндится с Berkeley DB, а большего и не надо - это просто реализация нескольких структур данных (в том числе и B-Tree и Hash) для эффективного хранения и поиска
http://www.sleepycat.com/products/bdb.html
-------------------
Написал кучу всего, а так и не сказал, чего ж использовать в качестве ключа и чего в качестве ассоциированного значения. Для поиска, ключ - слово в верхнем регистре и по возможности без окончаний/суффиксов, а значение - id-шники постов, в которых это слово встречается. Если ты прикрутишь BDB, то ничто не помешает тебе перетащить и сами посты в базу, а не юзать файлы.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
В зависимости от задач - нужны разные деревья [update] - amirul