[life.work] 30 лет профессионального программизма

Как же все-таки летит время. Вроде бы недавно публиковал аналогичный пост, но про 25 лет, а тут хоба! И уже 30.

Ну а так-то да, где-то в октябре 1994-го мне сделали трудовую книжку и я стал считаться профессиональным программистом. Писать программки начал пораньше, года с 1990-го, но именно за зарплату только с 1994-го.

Многое из того, что можно было бы сказать по этому поводу, уже было написано пять лет назад. Попробую добавить еще (не)много.

[prog.data.structures] В склерозник: ссылки на тему prefix/radix tree

Довелось недавно столкнуться с темой prefix/radix деревьев. По ходу изучения нашел несколько ссылок, которые для меня оказались полезными, поэтому зафиксирую их в склерозник, чтобы было проще найти в будущем.

Даю только ссылки, без пространных пояснений, уж извините меня за халтуру, но так проще.

Adaptive Radix Tree. Собственно, основная PDF-ка, с которой и следует начинать.

HAT-trie, a cache-conscious trie. Обзор сразу нескольких подходов к реализации префиксных деревьев и хеш-таблицы с переходом к рассказу об их комбинации HAT-trie. Плюс реализация этой идеи на C++.

Crit-bit trees и qp tries and crit-bit tries. Еще несколько вариаций на тему префиксных деревьев.

Akamai Radix Tree. Реализация на C++ radix tree от Akamai. Очень интересно если хочется посмотреть, как это дело можно реализовать. Хотя оформлена библиотека (в плане описания, документации, примеров и комментариев в коде), как по мне, бестолково. Поэтому разбираться не просто + реализация на многоэтажных шаблонах, так что требуется хорошее знание C++.

Compressing dictionaries with a DAWG и Directed Acyclic Word Graphs. Пара статей вокруг идей о том, как можно сократить объем данных в префиксном дереве.

Ну и вот эта ссылка регулярно всплывала, хотя напрямую к теме, вроде бы, не относится: Implementation of sparse_hash_map, dense_hash_map, and sparsetable.

От себя добавлю, что для сценария, в котором мне потребовалось что-то вроде prefix/radix дерево, "классический" вариант префиксного дерева вел к слишком большому расходу памяти. И, как я понял, это характерно для подобного рода деревьев, поэтому как раз и есть статьи о том, как уменьшить объем данных.