Отчет о проекте эффективного приоритетного дерева SAPT27.01.2025 11:31

Иллюстрация SAPT Adobe Photoshop

Отчет о, написанном мною, алгоритмическом статичном двунаправленном дереве, имеющим сложность O(1) по всем параметрам. Не считаю эту статью чем-то выдающимся, никуда не претендую, это всего лишь отчет моей работы. Если вам понравится можете свободно пользоваться.

В качестве небольшого предисловия:
Зачем я спроектировал дерево?

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

Пример профилей поведения будет в конце статьи.

Концепция структуры

Сама концепция структуры дерева SAPT (Static Abstract Priority Tree) опирается на ее абстрактное представление программистом, а годится для разных специфических задач, хоть и может быть модифицирована.

Структура SAPT является двумерным массивом std::vector(или std::array, настраиваемо), где уровнем (рядом) является внутренний массив, содержащий узлы в виде упомянутых ниже профилей.

Имеет 6 профилей, 2 из которых (с суффиксом Mini) существуют только для минимизации затрат при небольших структурах, я их называю под-профилями. Далее будут описаны общая работа профилей, и особенности каждого профиля отдельно ниже.

Выбор между памятью и эффективностью падает на горб пользователя.

Mini концепт (можно пропустить)

Для начала стоит запомнить что отличие автоматизированных профилей Mini заключается лишь в меньшем адресном пространстве на — 16 бит || 2 байта, вместо 32 бит || 4 байт в полноценных профилях. По этой причине отдельно разбирать их не имеет смысла.
Ну, а автоматизированные они потому, что SAPT сам решает когда какой профиль использовать. Может показаться что лучше было бы использовать авто-определение, однако мне это не подходит по отдельным причинам.

Общая работа профилей

Каждый узел содержит адрес (или указатель) на свою клетку в пространстве. Также атрибут помогающий в поиске детей, родителя, и приоритет — по которому и балансируется SAPT. Остальное используется лишь для оптимизации\эффективности работы.

Замечание: следующие профили содержат переменные предыдущих с некоторыми изменениями.

Профиль Memory || 8 байт
Содержит Координаты клетки (cell_y, cell_x), приоритет и количество детей (childCount — что подразумевает что все {childCount} дети идут последовательно).
Профиль BalanceMemory || 12 байт
Все еще содержит количество детей, также индекс первого ребенка (children). Дополнительно содержит номер фрагмента (fragmentIndexBy), в котором хранится первый ребенок.
Профиль BalanceSpeed || 24 байт
Вместо Координат клетки, содержит прямой указатель на нее (*cell).
Также хранит адрес родителя parent и его фрагмент parentFragmentIndexBy;.
Профиль Speed || 32 байта
Хранит индекс, и номер фрагмента для каждого ребенка отдельно. Это означает что добавлять ребенка можно в конец массива уровня. Также позволяет отречься от childCount.

Работа функций с разными профилями

Теперь о работе функций с разными профилями:

Примечание: Balance «наследует» метод хранения адреса клетки от своего брутального родителя, BalanceMemory от Memory, BalanceSpeed от Speed. По этой причине BalanceSpeed не описан (его отличает лишь метод хранения адреса клетки).

Memory
При запросе адреса клетки возвращает ее координаты.
При поиске детей берет childCount всех предыдущих узлов в уровне — получаем сдвиг на первого ребенка. В обратном порядке для поиска родителя.
BalanceMemory
Для поиска детей у нас есть готовый сдвиг (children), и нам остается лишь считать описанное количество детей (childCount), которое гарантирует что при считывании мы не прочитаем чужих детей.
Speed
Имеет прямой указатель на клетку, таким образом не нужно обращаться к игровому полю.
При поиске детей также имеет готовые индексы детей, и номера фрагментов в которых они находятся, что нивелирует любые лишние операции.
Поскольку в нашем случае дерево двунаправленное, указатель на родителя устанавливается при заполнении дерева ( за каждое ребро*), либо уже после его полного заполнения ( сразу для всех узлов). Суть в том что для создания ребра нам нужно располагать и родителем в дереве, и детьми.
В том числе поэтому дерево статичное

Фрагментация

Простая идея заключается в хранении номера фрагмента, с начала которого стоит считать индекс.
Без фрагментации максимальный размер уровня ограничивается максимальным возможным числом для типа uint32_t был бы 4,294,967,295 (4,3 миллиарда) элементов, не учитывая профиль Memory (ограничения нет, ибо сам индекс там и не храниться).
А теперь воспользуемся фрагментацией, и у нас получается максимум maxNum * 256 = 1,099,511,627,520 (1,1 триллион) элементов! Конечно же не учитывая ограничений ОЗУ
Кстати при грамотном подходе фрагментация улучшает работу cache locality.

Может показаться что это бесполезное использование памяти на номер фрагмента, ведь в реальных условиях вряд-ли будет достигнуто и 30–40 миллионов, чего уж там говорить о десятках миллиардов.

В общем это утверждение будет верным, однако мы на этом ничего не теряем, ведь место под номер фрагмента (1–4 байт) и так выделилось бы, учитывая выравнивание процессора, а заместо бесполезной памяти мы получаем огромную гибкость размеров.

Почему структура SAPT так быстра?

Весь секрет скорости (в худшем алгоритмическом случае, при профиле Speed) кроется в самом описании:
SAPT заимствует у std::vector или std::array скорость поиска, добавления и так далее.
При удалении амортизация достигается просто стиранием значений, вместо полноценного удаления, таким образом избегая дорогого сдвига.
То есть считая нужные нам параметры:

Вставка \ Удаление (амортизированное) O(1)
Получение элемента по индексу O(1)
(просто запоминаем)

Далее используется простая закономерность:
Если у нас на каждом уровне только узлы с одинаковым приоритетом, значит на следующем уровне приоритет будет current+1.
Таким образом достигается скорость определения уровня O(1) , а также «самобалансировка», ведь при вставке мы сразу знаем куда вставлять.

В общем с скоростью массива выходит в:

Поиск родителя \ ребенка O(1)
Балансировка O(1)

С поиском Min\Max значений тот же случай, Min всегда будет (из-за оптимизаций исключения переполнения), а Max будет являться размером наружного std::vector или std::array, который получается за O(1) .

Деление на несколько экземпляров, допустим один из детей стал самостоятельной клеткой, и отделился, образовав вторую структуру.
Эта операция займет O(log N) , где сложность заключается лишь в очистке предыдущей структуры-родителя. Не учитывая удаления выходит O(1) — вставка копии в список всех структур SAPT.

Подведя итоги мы имеем:

Вставка \ Удаление
Поиск по индексу \ родителя \ ребенка
Нахождение Min \ Max
Балансировка
Разделение на части \ с очисткой	\

Пример проекта

struct Memory {
    std::uint16_t cell_y;
    std::uint16_t cell_x;

    std::uint16_t priority;
    std::uint8_t childCount;
};
struct BalanceMemoryMini; // With uint16_t children       || -2 bytes
struct BalanceMemory {
    std::uint32_t children; // Index of first child
  
    std::uint16_t cell_y;
    std::uint16_t cell_x;
    std::uint16_t priority;

    std::uint8_t childCount;
    std::uint8_t childrenFragmentIndexBy;
};
struct BalanceSpeed {
    std::uint32_t *cell;

    std::uint32_t parent;
    std::uint32_t children; // Index of first child
    std::uint16_t priority;

    std::uint8_t childCount;
    std::uint8_t childrenFragmentIndexBy;
    std::uint8_t parentFragmentIndexBy;
};
struct SpeedMini; // With uint16_t children[3] & parent   || -8 bytes
struct Speed {
    std::uint32_t children[3];
    std::uint32_t parent;
  
    std::uint32_t *cell;
    std::uint16_t priority;
  
    std::uint8_t childrenFragmentIndexBy[3];
    std::uint8_t parentFragmentIndexBy;
};

// Example
// Massive with trees \/
// Every Tree is massive with levels \/
// Every Level is massive with profiles \/
std::vector>> sapts;

Это лишь пример проекта, без фактической реализации функций.

Итог

Структура требовательна к строгой реализации функций и контролем работы с ней программистом, однако это компенсируется легкой модификацией и производительностью.

Таким образом мы имеем эффективную, быструю и довольно гибкую статичную структуру сложности O(1) .
На проектирование у меня ушло 5 дней, и еще 5 дней на оптимизацию и поиск возможных ошибок.

Спасибо за прочтение!

Можете оставить комментарий о ваших идеях, например оптимизации памяти. Также будет интересно пригодилась ли вам статья, и найдете ли вы применение SAPT.