Привет всем. ... Не все таки меня здорово подкололи насчет моей реализации управления деревом, хранящимся в файле. Ржунемогу. Респект шутнику :)
Вообщем, к своему великому огорчению, я так и не смог сдвинутся с места со своей идеей текстовой индексации. Бьюсь головой "апстену", но это факт. Заклинило на механизме регистрации комбинаций. Который я пытался реализовать на базе AVL дерева. Натурального дерева - с Left, Right, Parent, Key. Дерево хранится в страничном файле. На каждой странице (4K) помещалось 88 нодов. Вывод который я сделал своей новизной особо не отличается - что русскому хорошо... то есть, что хорошо для конструкций в оперативной памяти, то для внешних хранилищ - смерть. Гы. Я знаю, что этому еще в школе учат, но вот проверил на своей шкуре :) Тормоза на этапе балансировки. Если эти самые left,right,parent (заголовок элемента дерева) всегда держать в памяти, то дикого падения производительности не наблюдается. Как только заканчивается место в кэше (начинается обмен с диском) то моск у этого дерева заклинивает напрочь. И ничего его не спасает. Все из-за того, что ноды, задействованные при балансировке, разбросаны по разным страницам. Короче, при добавлении одного нода, который весит всего-то ~50 байт, меняется до 10 страниц данных. Это для тех маленьких объемов данных, которые я пытался обработать. Если убрать балансировку - моск залинивает сразу. И бесповоротно. ----- Единственное что утешает, что я действительно смог разогнать первоначальную реализацию почти в два раза - ноды помещаются целиком на странице. Раньше они могли "размазываться" - убрал проверки внутренней целостности - прикрутил кэш для заголовков нодов. Еще пытался развалить индекс на секции (думал, это уменьшит число коллизий в многопоточной программе) - но толку мало. Пока все данные в кэше - ускорение действительно было заметно. Как только начинается обмен с диском - приходит добрый, пушистый зверь. Есть конечно еще идея - радикально увеличить размер кэша для заголовков нодов и упорядочить их выгрузку в файл (начать с тех, страницы которых сейчас в кэше, а потом группировать по страницам) - но я думаю это тоже нифига не поможет :)) ----- Я посмотрел как сделано в FB 1.5 (tree.h). Но, боюсь, я такую реализацию пока не осилю. Нужно пересматривать реализацию свего кэша, а это .... достаточно рискованное мероприятие. ... Самофатова надо придушить за оформление иходников. ---- Вообщем, буду пытаться заюзать хеширование. Идея такая. Хеш таблица оформляется в виде набора страниц файла. Справочник страниц будет всегда хранится в памяти. На странице хранится указатели на списки данных. Указатель на список - 6 байт. Получается что на странице (4K) будет хранится свыше 650 указателей. Если заюзать хеш-таблицу размером 5 млн, то размер справочника будет в районе 7700 страниц. Каждый элемент списка должен хранить явно больше одного элемента. Но тут я по-эксперементирую. Гы. Да. Размер самого описателя комбинации - 22 байта. ---- Всего-то нужно 350 млн комбинаций обработать. Хотя, судя по той статистике которую я лицезрел во время этого секс-марафона - число повторений >2. Так что, если быть оптимистом - то 175 млн максимум :))) ---- Коваленко Дмитрий.
