Отчет о, написанном мною, алгоритмическом статичном двунаправленном дереве, имеющим сложность по всем параметрам. Не считаю эту статью чем-то выдающимся, никуда не претендую, это всего лишь отчет моей работы. Если вам понравится можете свободно пользоваться.
В качестве небольшого предисловия:
Зачем я спроектировал дерево?
Я пишу научный проект из сферы биологии, где присутствует элемент иерархии, и для последовательного выполнения действий следовало отсортировать данные по приоритетам, при этом делать это максимально быстро и эффективно. Для удобства данные я называю клетками, а приоритет представляю "старостью" клеток.
Пример профилей поведения будет в конце статьи.
Концепция структуры
Сама концепция структуры дерева 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,3 миллиарда) элементов, не учитывая профиль Memory (ограничения нет, ибо сам индекс там и не храниться).
А теперь воспользуемся фрагментацией, и у нас получается максимум (1,1 триллион) элементов! Конечно же не учитывая ограничений ОЗУ
Кстати при грамотном подходе фрагментация улучшает работу cache locality.
Может показаться что это бесполезное использование памяти на номер фрагмента, ведь в реальных условиях вряд-ли будет достигнуто и 30-40 миллионов, чего уж там говорить о десятках миллиардов.
В общем это утверждение будет верным, однако мы на этом ничего не теряем, ведь место под номер фрагмента (1-4 байт) и так выделилось бы, учитывая выравнивание процессора, а заместо бесполезной памяти мы получаем огромную гибкость размеров.
Почему структура SAPT так быстра?
Весь секрет скорости (в худшем алгоритмическом случае, при профиле Speed) кроется в самом описании:
SAPT заимствует у std::vector или std::array скорость поиска, добавления и так далее.
При удалении амортизация достигается просто стиранием значений, вместо полноценного удаления, таким образом избегая дорогого сдвига.
То есть считая нужные нам параметры:
Вставка \ Удаление (амортизированное)
Получение элемента по индексу
(просто запоминаем)
Далее используется простая закономерность:
Если у нас на каждом уровне только узлы с одинаковым приоритетом, значит на следующем уровне приоритет будет current+1.
Таким образом достигается скорость определения уровня , а также "самобалансировка", ведь при вставке мы сразу знаем куда вставлять.
В общем с скоростью массива выходит в:
Поиск родителя \ ребенка
Балансировка
С поиском Min\Max значений тот же случай, Min всегда будет (из-за оптимизаций исключения переполнения), а Max будет являться размером наружного
std::vector или std::array, который получается за .
Деление на несколько экземпляров, допустим один из детей стал самостоятельной клеткой, и отделился, образовав вторую структуру.
Эта операция займет , где сложность заключается лишь в очистке предыдущей структуры-родителя. Не учитывая удаления выходит
- вставка копии в список всех структур 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<std::vector<std::vector<Memory>>> sapts;
Это лишь пример проекта, без фактической реализации функций.
Итог
Структура требовательна к строгой реализации функций и контролем работы с ней программистом, однако это компенсируется легкой модификацией и производительностью.
Таким образом мы имеем эффективную, быструю и довольно гибкую статичную структуру сложности .
На проектирование у меня ушло 5 дней, и еще 5 дней на оптимизацию и поиск возможных ошибок.
Спасибо за прочтение!
Можете оставить комментарий о ваших идеях, например оптимизации памяти. Также будет интересно пригодилась ли вам статья, и найдете ли вы применение SAPT.
Комментарии (12)
wataru
27.01.2025 08:47В статье очень не хватает хоть какого-то описания, что же это за структура данных-то и какие операции она выполняет.
Например, приоритетная очередь позволяет добавлять в структуру элементы с неким параметором "приоритет" и неким ключом, выдавать и удалять элемент с максимальным приоритетом и иногда изменять приоритет элемента с данным ключом: Insert(priority, key), GetMax() -> key, RemoveMax(), ChangePriority(key).
Бинарное дерево поиска позволяет добавлять элемент с ключом, удалять элемент по ключу и проверять, есть ли данный ключ в структуре, перебирать элементы в порядке возрастания ключа: Insert(key), remove(key), HasKey(key) -> bool, enumerate()-> key[]. Хеш-таблица далает все тоже самое, кроме перебора элементов по порядку возрастания ключа.
Дерево отрезков умеет изменять значение по индексу и выдавать сумму или максимум на отрезке между заданными индексами... и так далее.Вот также надо расписать все ваши операции, без этого вообще непонятно, зачем нужна ваша структура и нужна ли она вообще. Что за приоритет, что там меняется вообще, а что неизменно? Может, ваши операции с такой же сложностью выполняются на обычном массиве или связном списке. Может, вам подойдет обычная сортировка подсчетом вместо какой-то структуры данных, если вам надо упорядочить "клетки" по приоритету.
Dmitry_Mandi Автор
27.01.2025 08:47Если я верно понял, вы имеете ввиду описание реализации дерева. Однако в статье я написал лишь про концепт(если хотите идею) как структуры, так и работы с ней, и упомянул это в самом начале(про это еще немного в конце комментария).
Зачем нужна структура - думаю как в случае с другими структурами, каждый придумает конкретное применение себе сам, а я отдаленно привел пример со своим проектом. Если имеется ввиду общее назначение - для сортировки по приоритетам.
Приоритет самый простой, как например в бинарном дереве, но разрешаются дубликаты, в моем примере данные("клетки") уникальны, и объединить их в кластер без потерь трудно и выглядит для меня бессмысленным.
Меняться может все, но без серьезных логических потерь в сложности только при инициализации или полном пересчете дерева(для понимания потерь стоит представить дерево и вспомнить работу с функциями разных профилей).
Если ну очень сильно грубо говорить то конечно, можно сравнить дерево с массивом или связным списком. Насчет сложности - половина моих итоговых подсчетов унаследована от массивов, ведь с ними напрямую связаны вся структура, и отдельно уровни.
Не упомянул я реализацию по двум причинам:
- Я в программировании не профессионал, я только учусь, и показывать примеры, возможно, плохо организованного или отдаленного кода не хочется, хотя это меньшая из причин.
- Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом, постарался описать все функции как можно подробнее, но без технических деталей и реализации.
Я постарался как можно яснее объяснить идею работы функций, и попробовать передать абстрактное представление структуры программистом через иллюстрацию.
Спасибо за комментарий!wataru
27.01.2025 08:47Если я верно понял, вы имеете ввиду описание реализации дерева.
Нет, я имею ввиду описание того, что дерево делает. Какую задачу структура данных решает вообще. Я вам даже кучу примеров описания для других структур привел.
Приоритет самый простой, как например в бинарном дереве,
В бинарном дереве нет приоритетов. Приоритет есть в куче.
Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом,
Ну вот никому ничего не понятно, потому что неясно, что это вообще за структура и что она делает, зачем она нужна. Вы какие-то детали рассказали, но вообще не те, которые нужны для этого рассказа.
Dmitry_Mandi Автор
27.01.2025 08:47Окей, конечно, я могу написать функции если это столь не очевидно(в разделе "Итог" и "Работа функций с профилями" уже приведены все нужные параметры), далее на ваших примерах:
SAPT позволяет добавлять в структуру элементы с неким параметром "приоритет" и некими данными(ключом);Insert(priority, data)
Получать и удалять узел с максимальным \ минимальным приоритетом;GetMax() -> node; GetMin() -> node
Remove(node)
Перебирать элементы на одном уровне(с одним приоритетом), в глубину, снизу вверх и сверху вниз(является двунаправленным);IterateLevel(level) {}; IterateUp() {}; IterateDown() {}
Искать родителя\ребенка от ребенка\родителя, бонусом по индексу в уровне;FindByIndex(level, fragment, index) -> node
FindParent(child) -> parent
FindChildren(parent) -> children[]
Легко делить структуру на несколько;Divide(startNode) -> dividedPart
Дерево не ориентировано на частые изменения приоритета \ добавление новых элементов;
Сортирует данные по заданному приоритету при вставке, данные связаны между собой;Вся статья о работе и организации структуры, не понимаю проблемы. По моему быстрее статью прочитать, чем короткое описание ждать.
wataru
27.01.2025 08:47Спасибо, стало понятнее.Разделение дерева какими-то свойствами обладает? Например, в отсоединенном куске будут только элементы с меньшим приоритетом?
На одном уровне все элементы с заданным приоритетом?
Искать родителя\ребенка от ребенка\родителя, бонусом по индексу в уровне;
Что значит родитель в этой парадигме? И зачем вам его брать? Дерево - это внутреннее устройство структуры. Вообще говоря, снаружи вы о том что там вообще дерево можете и не знать. В insert() у вас никакого понятия о родителях/детях нет.
Дерево не ориентировано на частые изменения приоритета \ добавление новых элементов;
В таком случае вам не нужно дерево. Вам достаточно std::unordered_map<int, vector<Data>> priority_to_data. И еще в нагрузку к этому vector<> всех приоритетов, которые в структуре есть, чтобы можно было быстро брать следующий, предыдущий приоритет.
С разделением на части только не понятно немного. Возможно каждый кусок будет иметь свой вектор приоритетов и шарить один unordered_map. Если надо совсем быстро, то vector приоритетов тоже будет общим, и каждый кусок будет хранть array_view какой-нибудь на него.
Dmitry_Mandi Автор
27.01.2025 08:47Если интересен механизм, то в моей голове это происходит так - берется родитель который станет корнем, ищутся все его потомки, и к примеру копируются(или права на владения передаются) в отдельное дерево, а из этого очищаются(или становятся не валидными).
Да, как и сказано в статье, а также показано на иллюстрации. К примеру на 20м уровне данные исключительно с приоритетом 20; на уровне 15 с приоритетом 15 и так далее.
Родитель, как и ребенок, означает родительский узел, как и в обычном дереве типа бинарного. В примере профилей, и даже на иллюстрации показаны возможные методы создания ребер(связей), например хранение указателя\индекса.
Можно и не брать, и не хранить. В таком случае выйдет однонаправленное дерево, если вам угодно.
Согласен, в Insert() связи устанавливаются неявно. Чтобы скорее ответить на ваш комментарий, я взял пример из своего проекта, где связь вычисляется напрямую из данных. Пожалуй верная реализация без отстраненных данных будет такойInsert(priority, data, &parent) // Или индексы родителя в случаях с Memoryизвиняюсь, не доглядел.
Интересная идея. Тогда думаю и vector можно не хранить, если минимальный приоритет всегда 0, просто хранить максимум одной переменной. Однако конкретно мне нужно дерево для сохранения связей родитель-ребенок, а это как я знаю и образует дерево. В таком случае спасибо за обратную связь!
wataru
27.01.2025 08:47И еще, вы привели какие-то детали реализации касающиеся набора профилей, но ни ссылки на код, ни детального описания реализации нигде нет.
Dmitry_Mandi Автор
27.01.2025 08:47Профили я привел лишь как пример, они являются как бы разными примерами реализации структуры, хоть и считаю профили отдельной, доп. частью, структуры. Но для большего понимания я старался как можно лучше объяснить всю свою идею.
А описывать там кажется нечего, примеры структур представляющих узлы дерева. А если говорить про переменные - важные описаны в статье, а остальные полностью описывают себя своими названиями.
mayorovp
А делает-то это дерево что? Как вообще с ним работать? Что означают слова Static, Abstract и Priority в его названии?
Dmitry_Mandi Автор
Ваш первый вопрос довольно неконкретный, я затрудняюсь на него ответить.
Очевидно хранит данные, но почти уверен это не тот ответ который вы надеялись услышать.
Пример реализации функций работы с деревом я привел в статье, либо описал их идею, на примере фрагментации.
Static - подразумевает, негативно влияющую на сложность, реакцию на изменение данных дерева динамически(я к этому отсылался в разделе о фрагментации). Если сравнивать с привычными обществу деревьями - это узкое место SAPT. В том числе по этой причине я указал специфичность задач, которым подходит структура. Хотя безусловно этот концепт можно модифицировать, сместив фокус на динамичность.
Abstract - на эту тему я коротко высказался в начале статьи. Я имел ввиду, возможно не очевидное(потому приправленное иллюстрацией), представление структуры, а также различность реализации дерева с обычными деревьями, уровни физичны, некоторые вычисления опираются на закономерности выведенные только по причине такого представления программистом.
Priority - возможно, это не самое важное ключевое слово, однако хотелось подчеркнуть именно работу с приоритетами - дерево сортируется именно по ним.
Tree - также хочется добавить - независимо от реализации дерева, я опирался на идею о том, что родители и дети связаны между собой, потому назвал структуру не иначе как деревом. Хотя она идет вразрез с многими устоявшимися представлениями о реализации деревьев.