Pull to refresh

Comments 16

UFO just landed and posted this here

| yatrie creation time: 4.588216s (666k wps)


Батюшка, да не иначе сотона руковОдил вами во время сией разработки. Нехорошая какая цифирь нарисовалась

Я так понял, все пока рассчитано на работу в одном потоке (ну, разве, что читать можно параллельно). Если модифицировать для многопоточного использования, то скорость наверняка просядет.
Даже если писать из одного потока, а читать из других, то проблемы неизбежны :)
Я не очень хорошо знаю английский, поэтому из множества прочитанных на тему префиксных деревьев статей наверняка часть информации до меня не дошла.

Дракона давно перевели на русский.
С авторами знаком, а вот про книгу не слышал. Спасибо.
Пока посмотрел код работы с односвязными списками и есть пара моментов для улучшений:
1. Отказаться от рекурсии в пользу итерации для операций на списках;
2. Насколько часто происходит поиск предка в односвзянном списке? Если часто, может стоит рассмотреть использование двусвязного?
Спасибо. Приятно, что кто-то полез под капот.
1. А если в процентах измерить, это сколько даст роста?
2. Там список я взял, который делал для ассоц. массива. Поэтому там так все. Предок там вообще не нужен ни разу, да и сам список нужен только при создании дерева. При чтении уже не используется.
Сейчас хочу попробовать самые потенциально сильные изменения, скорость повыше, а размер еще меньше.
Там сейчас битовая маска 96 бит 12 раз по 1 байту. Поэтому счет битов идет 12 раз. Хочу сделать не char, а int32 3 раза.
Id хранятся в полях int32, что сильно больше самого большого словаря. По моим замерам, весь русский язык умещается в 5 млн. узлов. А значит можно взять 3 байта на id, а не 4.
Выравнивание сожрет 1 байт на узле, но польза все равно останется за счет уменьшения ссылок. Узел 16 байт, 1 ссылка 3 байта. На большом словаре примерна одинаковое кол-во узлов и ссылок, получается экономия 1 байт из 19, что чуть больше 5%.
Жаль читать по 3 байта одним махом невозможно, придется копировать 3 байта на число uint32_t.
typedef struct _ref_s {
uint8_t data[3];
} ref_s;

typedef struct _node_s {
uint32_t mask[3];
ref_s ref_id;
} node_s;

typedef struct _refs_s {
    uint32_t increment;
    uint32_t size;
    ref_s data[];
} refs_s;



www.jdoodle.com/c-online-compiler#&togetherjs=e0PePScmmQ
Еще вот думаю как-то сделать, чтобы алфавит и размер маски можно было бы выбирать. Сейчас используется около 80 бит, но там англ. + русский + символы, обычно сразу оба алфавита не нужны.
В итоге можно сделать дерево более компактным, чем делает продвинутая, но более медленная либа libdatrie.
Дракона почитайте, там есть глава про подходящую структуру данных для этой задачи.
Пролистал, но не нашел ничего похожего. Может книга другая? Я смотрел:
Ахо А.В., Сети Р. Ульман Дж.Д. Компиляторы: Принципы, технологии и инструменты
Если у Вас 2 издание, то раздел 3.9.8 описывает структуру для уплотнения хранения графа переходов.
Или я задачу понял неверно.
Большое спасибо. Почитаю. Вместо описанного в этой статье префиксного дерева я как раз сейчас пытаюсь реализовать структуру направленного графа.

Моё сжатое префиксное дерево из списка английский заголовков wiki(4 000 000+ заголовков, 206мб файлик) читает и добавляет 2мб/сек. В памяти на 64 битах занимет 1.1гб, из них на дерево 700мб, т.е. в 4 раза больше чем на диске.

Узел дерева строю по одному биту, если у ключа n-й бит 0 то добавляю в первый узел, 1 во второй. Префикс у узла длиной максимум 4 байта.

Скорость поиска, добавления, удаления вообще не нужно считать, у префиксного она всегда большая.

А то что у вас получилось я не понимаю. Считаете какие-то слова в секунду, 84 мегабайта откуда-то возникли. Типо меньше стало чем на диске, чтоли?

Sign up to leave a comment.

Articles