Ранг-селект словари
Это первая статья из планируемой серии про succinct data structures - класс наиболее компактных структур данных. Канонический пример такой структуры - это представление дерева в виде правильной скобочной последовательности, дерево изnвершин таким образом представляется с помощью2nбит в то время как типичная динамическая реализация требовала бы как два указателя по 64-бит на каждый узел (разумеется можно немного сократить простыми оптимизациями, но даже близко 2 бита не получить). Фундамент подобных структур - это rank-select словарь, представляющий собой битовый вектор и дополнительную структуру для выполнению двух операций ранг и селект. В указанном примере с деревом с помощью ранга и селекта можно сделать базовую навигацию: найти номера потомков/родителей, узнать размер поддерева. В статье расскажу как делать эти операции быстро используя при этом всего 3,6% дополнительной памяти.
https://habr.com/ru/articles/939614/
#cpp #programming
👉 @cpp_lib
Это первая статья из планируемой серии про succinct data structures - класс наиболее компактных структур данных. Канонический пример такой структуры - это представление дерева в виде правильной скобочной последовательности, дерево изnвершин таким образом представляется с помощью2nбит в то время как типичная динамическая реализация требовала бы как два указателя по 64-бит на каждый узел (разумеется можно немного сократить простыми оптимизациями, но даже близко 2 бита не получить). Фундамент подобных структур - это rank-select словарь, представляющий собой битовый вектор и дополнительную структуру для выполнению двух операций ранг и селект. В указанном примере с деревом с помощью ранга и селекта можно сделать базовую навигацию: найти номера потомков/родителей, узнать размер поддерева. В статье расскажу как делать эти операции быстро используя при этом всего 3,6% дополнительной памяти.
https://habr.com/ru/articles/939614/
#cpp #programming
👉 @cpp_lib
❤3👍3
This media is not supported in your browser
VIEW IN TELEGRAM
FTXUI
Простая кроссплатформенная библиотека C++ для пользовательских интерфейсов на базе терминала!
• Функциональный стиль
• Простой и элегантный синтаксис
• Создаваемые консольные UI поддерживают навигацию с помощью клавиатуры и мыши
• Поддержка UTF8
• Поддержка анимации
• Поддержка рисования
• Нет зависимостей
• Кроссплатформенность: Linux/MacOS, WebAssembly, Windows
https://github.com/ArthurSonzogni/FTXUI
#cpp #programming
👉 @cpp_lib
Простая кроссплатформенная библиотека C++ для пользовательских интерфейсов на базе терминала!
• Функциональный стиль
• Простой и элегантный синтаксис
• Создаваемые консольные UI поддерживают навигацию с помощью клавиатуры и мыши
• Поддержка UTF8
• Поддержка анимации
• Поддержка рисования
• Нет зависимостей
• Кроссплатформенность: Linux/MacOS, WebAssembly, Windows
https://github.com/ArthurSonzogni/FTXUI
#cpp #programming
👉 @cpp_lib
1👍11❤3💩1