Comments 16
| yatrie creation time: 4.588216s (666k wps)
Батюшка, да не иначе сотона руковОдил вами во время сией разработки. Нехорошая какая цифирь нарисовалась
1. Отказаться от рекурсии в пользу итерации для операций на списках;
2. Насколько часто происходит поиск предка в односвзянном списке? Если часто, может стоит рассмотреть использование двусвязного?
1. А если в процентах измерить, это сколько даст роста?
2. Там список я взял, который делал для ассоц. массива. Поэтому там так все. Предок там вообще не нужен ни разу, да и сам список нужен только при создании дерева. При чтении уже не используется.
Сейчас хочу попробовать самые потенциально сильные изменения, скорость повыше, а размер еще меньше.
Там сейчас битовая маска 96 бит 12 раз по 1 байту. Поэтому счет битов идет 12 раз. Хочу сделать не char, а int32 3 раза.
Id хранятся в полях int32, что сильно больше самого большого словаря. По моим замерам, весь русский язык умещается в 5 млн. узлов. А значит можно взять 3 байта на id, а не 4.
А значит можно взять 3 байта на id, а не 4.
а выравнивание?
Жаль читать по 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
В итоге можно сделать дерево более компактным, чем делает продвинутая, но более медленная либа libdatrie.
Моё сжатое префиксное дерево из списка английский заголовков wiki(4 000 000+ заголовков, 206мб файлик) читает и добавляет 2мб/сек. В памяти на 64 битах занимет 1.1гб, из них на дерево 700мб, т.е. в 4 раза больше чем на диске.
Узел дерева строю по одному биту, если у ключа n-й бит 0 то добавляю в первый узел, 1 во второй. Префикс у узла длиной максимум 4 байта.
Скорость поиска, добавления, удаления вообще не нужно считать, у префиксного она всегда большая.
А то что у вас получилось я не понимаю. Считаете какие-то слова в секунду, 84 мегабайта откуда-то возникли. Типо меньше стало чем на диске, чтоли?
Хитрое префиксное дерево Си реализация