Bazist12 фев 2018 в 16:25

Самый быстрый Индиан: Key/Value контейнер на базе Trie

8 мин

6.5K

Алгоритмы *

+16

Комментарии 19

maksqwe 12 фев 2018 в 17:35

Когда-то просматривал ваш проект… заметил странный код и как-то забыл об этом спросить.
HArray\HArray_insert.cpp — 576

else //key is exists, update
{
	pContentPage->pContent[contentIndex] = pContentPage->pContent[contentIndex];

	return 0;
}

Это не опечатка?

Bazist 12 фев 2018 в 18:07

Да, опечатка, обязательно исправлю. Спасибо за внимательность, порой самые очевидные ошибки сложнее всего заметить.

unsafePtr 12 фев 2018 в 18:23

Поскольку проект под лицензией MIT, можно попробовать прогнать статический анализатор PVS-Studio, может ещё какие нибудь недочеты можно будет устранить.

Bazist 12 фев 2018 в 18:47

Можно конечно, наверняка от этого была бы польза. Но самые сложные баги что я здесь ловил, были алгоритмические. Обычно дело обстояло так, на вставке 345123 ключа, что-то идет не так, но баг никак себя не проявляет и структура умудряется безошибочно вставить еще несколько сотен тысяч ключей после чего необьяснимо крашится в каком нибудь проприетарном коде. Такие баги пришлось ловить, написав отдельную функциональность которая тщательно проверяет Healthy всей памяти после вставки каждого ключа, чтобы засечь баг как можно раньше. Для структуры, которая кодирует данные чуть менее чем полностью через GoTo по другому не получается. На сейчас, в основных кейсах, структура достаточно стабильно работает под Linux и Windows, на х64/x32 платформах. В одном из тестов удалось вставить даже около 1 млрд ключей и ничего не рассыпалось.

Tangeman 13 фев 2018 в 17:10

Простите, не можете ли объяснить, каким образом содержание или количество данных влияют на надежность?

Мне казалось, что если алгоритм верен (и железо надёжно) — то неважно, сколько данных хранится — 1000 записей или миллиард, а судя по вашему комментарию получаются что это лотерея, и не факт что при 10 миллиардах записей ничего не «рассыпется».

Bazist 13 фев 2018 в 17:38

Далеко не все алгоритмы. Хештаблицы построены на вероятностной модели. Такая модель подразумевает, что распределение по слотам идет достаточно равномерно без сильных перекосов. Но большие данные сами по себе подразумевают что может быть любой сценарий. В одних buckets будет всего несколько ключей, а в других 100500. И дальше все зависит предусмотрено ли это разработчиками. Плохое качество хешфункции и(или) большие данные могут «подвесить» или «развалить» практически любую хештаблицу.

dreamer-dead 14 фев 2018 в 12:43

Да, на больших объемах могут вылезти ошибки или недостатки проектирования, но при чем тут надежность? Небалансирующееся дерево может выродится в список, но работать то оно не перестанет, просто будет тормозом.
Если у Вас там вероятны проезды по памяти, то напишите приличные тесты и гоняйте их под {l,m}san.

Bazist 14 фев 2018 в 13:31

С семейством Binary Tree да. Это одна из причин, почему именно это семейство поисковых алгоритмов используется в базах данных. Хорошее предсказуемое поведение как по скорости работы так и по потреблению памяти в независимости от объемов данных, хотя тут тоже есть ньюансы. Пост выше касался хештаблиц и разных гибридных алгоритмов, которые используют вероятностную модель. С ними не все так однозначно.

Videoman 13 фев 2018 в 14:20

Спасибо большое за поднятие интересной темы. А вы не могли бы привести какие-нибудь детали реализации, в чем основная фишка или описать основные операции по шагам? Просто при прочтении, внимательном, не мог отделаться от мысли что вы описываете suffix-tree. Кода много, а по картинкам вообще ничего не понял, хотя, вроде немного в теме, про хеш-таблицы и деревья. Заранее извиняюсь, если туплю на пустом месте.

Bazist 13 фев 2018 в 15:29

Спасибо за отзыв. Действительно, сейчас когда говорят о Trie, зачастую подразумевают тот-же Suffix-Tree, хотя это всего лишь один из подвидов применения Trie, где добавив все возможные суффиксы строк получаются доступными такие операции как — поиск подстроки, количество различных подстрок в строке и др. Как это работает достаточно хорошо описано в разных источниках, есть посты и на этом сайте. Однако область применения Trie, как и любого Key/Value контейнера, не ограничивается работой с текстом или алгоритмами архивирования. Если реализация не тривиальная, то работать такой контейнер может на уровне или быстрее хештаблиц при этом потребляя меньше памяти и предоставляя более широкую функциональность. В таком ключе статей мало, почему я и решил написать пост выше на хабре. Подробного описания алгоритмов для HArray пока что нет, но есть подобное описание для JudyArray. Как по мне, то эти документы как их не пиши, будут тяжелыми для восприятия, поэтому я больше склоняюсь к мысли просто записать несколько видео-лекций возле доски в будущем.

Videoman 13 фев 2018 в 19:14

В принципе, описывать всю полную и законченную реализация не обязательно. Насколько мне удалось понять из вашего описания, вы применяете хитрую методику аллокации узлов которая сильно отличается от аллокации узлов в дереве. Вот про нее бы и хотелось услышать поподробнее. За счет чего появляется возможность оптимизации, ведь мы, по сути, пытаемся создать такие же разреженные массивы узлов как и в случае с деревьями?

Bazist 14 фев 2018 в 13:49

Тут конечно можно было бы написать длинный пост, с большим количеством технических деталей, как и что работает. Но самом деле, я бы смотрел глубже, вообще в суть Trie. А суть в том, что он на самом деле намного ближе к уже работающим механизмам в мире биологии, он сам по себе моделирует эволюционный процесс, где каждый из узлов усложняется только по мере необходимости. Поэтому он часто находит применения в таких неожиданных областях, как например анализ цепочек ДНК. Но это отступление, если вернуться почему Trie работает быстрее, то все сведется к тому, что он лучше работает с линейной памятью. Он просто линейно пишет свои узлы, шаг за шагом. Пишет эффективно, если ключи похожи, он использует одни и теже сегменты два и более раз, не пишет ничего дважды, не перемещает уже записанные сегменты, ничего не балансирует, ничего глобально не перестраивает на ходу. Если у него есть конфликт, ставит шунт, говорит здесь ветвление делаем джамп и снова линейно пишет. Вообщем суммируя, сам по себе алгоритм, кроме всех прочих достоинств, более дружелюбен к блоку предсказания процессора, к кешам процессора и к линейной модели памяти вообще. Но конечно, чтобы раскрыть весь его потенциал, нужно многие вещи делать вручную. Если напр. на каждой операции создания вызывать создание узла через оператор new, то никаких конечно профитов по скорости не будет.

Videoman 14 фев 2018 в 13:57

А поясните пожалуйста вот это ваше высказывание:

Вообщем суммируя, сам по себе алгоритм, кроме всех прочих достоинств, более дружелюбен к блоку предсказания процессора, к кешам процессора и к модели памяти вообще.

Если даже предположить, что мы не используем new и сжимаем узлы, то возьмем, к примеру, текстовый ключ «veryveryverylongkey». Здесь я насчитал 19-ть рандомных переходов по памяти. Как это соотносится с вашим утверждением выше, что-то я туплю?

Bazist 14 фев 2018 в 14:06

Если у вас всего один ключ veryveryverylongkey, то у вас самый простой примитив. Все что сделает Trie, просто запишет его в одну единственную область памяти как сплошной текст на максимальной скорости. Чуть сложнее будет если у вас будет еще один, похожий на этот ключ, тогда получится бранч на два ветвления Здесь есть обьяснение с картинками

Videoman 14 фев 2018 в 14:19

Т.е. мы не сплитим ключ пока в этом нет необходимости. ОК, я вас понял. Эх, тогда все-таки придется читать оригиналы начиная с Judy Array и по списку. Жаль. Вы меня заинтриговали. Не часто на ровном месте открываешь давно известные идеи с новым неожиданным подходом.

Bazist 14 фев 2018 в 14:48

Judy Array достаточно большой документ, там используется до десятка разных способов сжатия узлов. Если интересует только этот метод сжатия, то это Patricia или Compact Trie описан в вики, напр. здесь en.wikipedia.org/wiki/Radix_tree