информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяСетевые кракеры и правда о деле ЛевинаСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Phrack #70/0x46 
 Возможно, Facebook наступил на... 
 50 лет электронной почте 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
В зависимости от задач - нужны разные деревья [update] 17.04.06 12:58  Число просмотров: 2721
Автор: 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, то ничто не помешает тебе перетащить и сами посты в базу, а не юзать файлы.
<programming> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach