Иллюстрация SAPT Adobe Photoshop
Иллюстрация 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
    Имеет прямой указатель на клетку, таким образом не нужно обращаться к игровому полю.
    При поиске детей также имеет готовые индексы детей, и номера фрагментов в которых они находятся, что нивелирует любые лишние операции.
    Поскольку в нашем случае дерево двунаправленное, указатель на родителя устанавливается при заполнении дерева (O(1) за каждое ребро*), либо уже после его полного заполнения (O(N) сразу для всех узлов). Суть в том что для создания ребра нам нужно располагать и родителем в дереве, и детьми.
    В том числе поэтому дерево статичное

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

Простая идея заключается в хранении номера фрагмента, с начала которого стоит считать индекс.
Без фрагментации максимальный размер уровня ограничивается максимальным возможным числом для типа 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 всегда будет 0 (из-за оптимизаций исключения переполнения), а Max будет являться размером наружного std::vector или std::array, который получается за O(1).

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

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

Вставка \ Удаление

O(1)

Поиск по индексу \ родителя \ ребенка

O(1)

Нахождение Min \ Max

O(1)

Балансировка

O(1)

Разделение на части \ с очисткой

O(1) \ O(log N)

Пример проекта
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<std::vector<std::vector<Memory>>> sapts;

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

Итог

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

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

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

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