Поиск и структуры данных
Поиск можно считать одной из наиболее нужных и часто используемых операций при разработке программного обеспечения. На сегодняшний день известно большое количество алгоритмов и структур данных, обеспечивающих высокую скорость поиска. Пусть и в меньшей степени, но подобные задачи возникают и в сфере разработки ПО для встраиваемых систем, одной из главных особенностей которой является существенная ограниченность системных ресурсов.
В статье предлагается рассмотреть особенности реализации элементарной структуры данных и способы оптимизации в условиях малого объема доступной памяти.
Зачем это автору
В процессе разработки фреймворка для ARM-микроконтроллеров мне захотелось реализовать более-менее универсальный способ обработки ответов устройств, управляемых посредством AT-команд.
Текущая идея заключается в реализации Patricia-дерева, где значениями узлов будут указатели на обработчики ответа, а ключами, соответственно, префиксы ответов. Однако классическая реализация выходит чересчур дорогой в плане расходования RAM, что заставило подумать над способами уменьшить количество необходимой памяти.
Префиксное дерево само по себе не самое простое для понимания и реализации, а если добавить шаблоны C++, то существует риск окончательно запутаться и не довести задумку до конца, поэтому экспериментировать я решил с BST.
Бинарное дерево поиска на C++
Классической структурой данных, предназначенной для быстрого поиска, является бинарное дерево поиска (BST – binary search tree), которое обладает следующими характеристиками:
Временная сложность поиска: O (log n)
Емкостная сложность: O(n)
И если с временной сложностью в целом поделать ничего нельзя (так как функция поиска элементарная) и реальное затраченное время зависит исключительно от размера данных и мощности процессора, то емкостная накладывает существенное ограничение на применимость данной структуры (да и других тоже) в условиях крайне малого объема доступной памяти.
Рассмотрим классическую реализацию бинарного дерева поиска на языке C++. В первую очередь необходимо определить тип данных каждого узла будущего дерева (для упрощения примем, что и ключи, и значения имеют целочисленный тип), код непосредственно реализации дерева можно опустить, так как с точки зрения расходования памяти он является несущественным, потому что содержит только указатель на корневой элемент:
struct Node
{
int Key; // 4 байта
int Value; // 4 байта
Node* Left; // 4 байта
Node* Right; // 4 байта
};Таким образом, каждый узел дерева занимает ~16 байтов (будем считать, что программа предназначена для 32-битных систем с размером указателя 4 байта и размером типа int также 4 байта), то есть константа в оценке емкостной сложности равна 16!
Подобная структура данных становится весьма дорогим удовольствием, учитывая размеры RAM современных микроконтроллеров. Например, один из самых популярных ARM-контроллеров низшей ценовой категории Stm32f103c8t6 предлагает 20 Кб RAM и 64 Кб Flash-памяти. Классическая реализация бинарного дерева поиска позволит хранить ~1200 узлов, что займет практически весь доступный объем оперативной памяти.
В то же время разработка программного обеспечения для микроконтроллерной техники имеет ряд особенностей, одной из которых можно считать нередкое отсутствие необходимости изменять структуру данных во время выполнения, значительная часть данных известна еще на этапе компиляции, что позволяет разместить их не в оперативной, а во flash‑памяти, используя приемы статического шаблонного программирования на языке C++.
Рассмотрим возможную модификацию реализации дерева.
Статическое константное дерево
Каждый узел дерева можно задать шаблонной структурой:
template<unsigned _Key, unsigned _Value, typename _Left, typename _Right>
struct Node
{
static const unsigned Key = _Key;
static const unsigned Value = _Value;
using Left = _Left;
using Right = _Right;
};Несложно заметить, что структура содержит два статических константных значения, что позволяет ожидать от компилятора помещения их именно в ROM-память, а указатели на потомков заменены на их типы, то есть в памяти места не занимают.
В терминах шаблонных классов, когда каждый узел дерева определяет новый тип данных, понятие "текущий узел" (используемое в классической реализации метода поиска) некорректно, поскольку отсутствуют объекты. Вместо этого необходимо, как это обычно и происходит, применить рекурсивный алгоритм, добавив в структуру Node метод поиска:
static auto Search(unsigned key)
{
return key == Key
? Value
: key < Key
? Left::Search(key)
: Right::Search(key);
}Само же дерево существенно упрощается, содержит только корень, а метод поиска делегирует поиск корневому элементу:
template<typename _Root>
struct BST
{
using Root = _Root;
static auto Search(unsigned key)
{
return _Root::Search(key);
}
};Основной проблемой является корректное формирование дерева на этапе компиляции, можно предложить три пути решения:
Формировать узлы вручную.
Написать программу генерации C++ кода с правильным порядком узлов (например, на каком-либо скриптовом языке).
Используя приёмы метапрограммирования сформировать корректное дерево на этапе компиляции.
Может показаться, что первый и второй пункты добавлены для количества, однако признаюсь, что действительно первоначальной идеей было оставить все как есть и формировать узлы вручную.
Формирование структуры дерева в compile-time
Используемое в качестве примера бинарное дерево поиска с учетом изначально известного набора ключей несложно построить следующим алгоритмом:
Корень дерева - это медианный элемент массива ключей.
Левый потомок - это дерево из элементов левее медианного, правый - правее.
В рамках реализации автоматического построения дерева структура узла разделилась на 2 части:
/// Базовая структура (ключ-значение)
template<auto _Key, unsigned _Value>
struct Node
{
static constexpr auto Key = _Key;
static constexpr unsigned Value = _Value;
};
/// Расширенный узел (с потомками)
template<typename _BaseNode, typename _Left, typename _Right>
struct ExtendedNode
{
static constexpr auto Key = _BaseNode::Key;
static constexpr auto Value = _BaseNode::Value;
using Left = _Left;
using Right = _Right;
static auto Search(unsigned key)
{
return key == Key
? Value
: key < Key
? Left::Search(key)
: Right::Search(key);
}
};Пользователь объявляет необходимое количество базовых узлов, а специальный класс формирует из них по предложенному выше алгоритму дерево:
/// Компаратор узлов для их сортировки
template<typename LeftNode, typename RightNode>
struct NodesComparator
{
static const bool value = LeftNode::Key > RightNode::Key;
};
/// Формирование узла
template<typename Nodes>
struct MakeNode
{
/// Сортировка узлов по ключам
using SortedNodes = typename TypeListSort<NodesComparator, Nodes>::type;
static const int size = Length<Nodes>::value;
/// Корень - медианный элемент, потомки формируются рекурсивно
using type = ExtendedNode<
typename GetType<size / 2, SortedNodes>::type,
typename MakeNode<typename Slice<0, size / 2, SortedNodes>::type>::type,
typename MakeNode<typename Slice<size / 2 + 1, size - (size / 2 + 1), SortedNodes>::type>::type
>;
};
/// Дно рекурсии
template<>
struct MakeNode<TypeList<>>
{
using type = NullNode;
};В коде выше использованы вспомогательные элементы из состава шаблонных утилит:
TypeListSort - сортировка списка типов по предикату.
GetType - получение типа из списка типов по его индексу.
Slice - выбор среза из списка типов.
Для конечного пользователя формирование дерева выглядит так:
/// Объявить базовые узлы
using N1 = Node<5, 105>;
using N2 = Node<10, 110>;
using N3 = Node<20, 120>;
/// Объявить список узлов (не обязательно упорядочивать)
using nodes = TypeList<N2, N1, N3>;
/// Сформировать дерево
using Tree = BST<MakeNode<nodes>::type>;
/// Поиск по дереву: Tree::Search(Value);Результаты
Предложенный подход проверен на компиляторе GCC для ARM, эксперименты с количеством узлов показали, что каждый узел дерева требует ~10 байтов ROM и ни одного байта RAM! (автор программирует под микроконтроллеры исключительно как любитель, но оперативная память, как правило, расходуется быстрее ROM).
С точки зрения быстродействия программа также позволяет предположить максимальную скорость, поскольку поиск представляет собой последовательность конструкций if-else, фрагмент дизассемблированной версии программы приведен на рисунке 1, а более понятная декомпилированная версия – на рисунке 2.
Таким образом, если все элементы структуры данных известны на этапе компиляции, язык C++ позволяет существенно сэкономить ресурсы системы, объем занимаемой памяти сократился примерно в 1.6 раза, причем вся структура данных переместилась из RAM-памяти в ROM, что также можно считать позитивным результатом. Скорость поиска по сравнению с классической реализацией даже ускорится (честно признаюсь, не проверял, но смею заявить это на основании результатов дизассемблирования), так как переход по ветвям представляет собой просто последовательность условий.
Применимы ли полученные результаты на практике - вопрос для автора нерешенный. Как уже упоминалось под катом в начале, есть желание таким же образом реализовать префиксное дерево. Получится или нет - пока неизвестно. Однако сам эксперимент бы весьма интересным, позволил попрактиковаться в программировании на C++ и получить интересные результаты хотя бы в цифрах.
Комментарии (40)
bullitufa
13.01.2022 14:28По сути, у вас получился switch-case формируемый во время компиляции. Но есть плюс, по сравнению с switch, можно масштабировать вариативным шаблоном.
А можно добавить поддержку динамического добавления узлов? Ерунда, но иногда бывает нужно.
DSarovsky Автор
13.01.2022 15:08Да, по сути, это switch-case, но именно бинарный, то есть поиск все же за O(logn).
Динамическое добавление узлов здесь никак, к сожалению (это уже реальные объекты, а их у меня нет вовсе).bullitufa
13.01.2022 16:07+1arm gcc, switch на добрую сотню case, делает что-то близкое к бинарному дереву. Никаких if-else. При этом switch(u16), case отсортирован (кодогенерация), значение ключей с дырками, поиск (смотрел в отладке) в несколько ассемблерных операций.
Amomum
13.01.2022 16:01Не думали использовать хэшмап в компайл-тайме? Например, https://github.com/mapbox/eternal
Поскольку добавлять или удалять узлы не нужно, снимаются вопросы с управлением памятью, а look-up константный.
Вот насчет коллизий не знаю, но, наверное можно что-то придумать (static_assert выдавать, например :)
DSarovsky Автор
13.01.2022 16:27Не знал про такой проект, пролистал описание, выглядит очень интересно, спасибо! Более чем возможно, что получится его применить в своем проекте, а не изобретать велосипед, как обычно бывает :(
Amomum
13.01.2022 16:50+1Это просто первая же ссылка в гугле, если что :)
Ну а насчет велосипедов.. "если никто не будет изобретать велосипеды, то они превратятся в непознаваемое наследие предков". Это может быть не очень полезно для проекта, но полезно для вас как специалиста :)
oleg-m1973
13.01.2022 16:20+1Для таких задач в compile-time нужно использовать массивы. Хотя, для общего развития, чтобы научиться работать с constexpr-выражениями, и такое сойдёт.
DSarovsky Автор
13.01.2022 16:24С массивами тоже приходилось иметь дело, однако ситуация такова, что задать данные надо статическими, а иметь к ним доступ в runtime. Или я не так понял про массивы.
oleg-m1973
13.01.2022 16:31В смысле? У меня примерно вот так это выглядело - сортируешь статический массив в compile-time, потом, в runtime, просто ищешь по нему при помощи std::lower_bound/upper_bound
static constexpr auto _symbols2 = MakeSortedArray
({
"USTECHIndex",
"AAPL_us",
"UK100Index",
"BARC_uk",
"DE30Index",
"BNP_fr",
"JAPANIndex",
});Amomum
13.01.2022 16:52Есть std::binary_search :) Но по моему опыту он очень хорошо стек кушает
oleg-m1973
13.01.2022 16:55Каким образом? Там даже рекурсии нет
Amomum
13.01.2022 16:58Видимо, зависит от реализации std, я сходу не помню, но в моей почему-то было очень много вложенных вызовов каких-то вспомогательных
oleg-m1973
13.01.2022 18:54Нет, не зависит. Это старый и простой алгоритм https://en.cppreference.com/w/cpp/algorithm/lower_bound
Amomum
14.01.2022 02:09Вообще говоря, конечно, может зависеть, ведь стандарт не оговаривает как именно реализуются стандартные алгоритмы..
Но видимо у меня какие-то фантомные воспоминания (или я с чем-то другим путаю), сейчас посмотрел стектрейс на том компиляторе, получил:
std::__lower_bound⟨int*, int, __rw::__rw_lt⟨int⟩, int⟩(T1, T1, const T2&, T3, T4*, std::random_access_iterator_tag) ⇒ __rw::__rw_lt⟨int⟩::operator ()(const int&, const int&) constИ 96 байт стека; по воспоминаниям было как-то сильно больше, но тот проект давно канул в Лету, так что признаю свою неправоту :)
DSarovsky Автор
13.01.2022 17:01Бегло посмотрел справку на std::lower_bound/upper_bound, они принимают конкретные runtime-параметры, тогда вопрос: в какой памяти окажется этот массив? Да, он статический и constexpr, то есть проинициализирован целиком в compile-time, однако какую память будет в итоге занимать?
oleg-m1973
13.01.2022 17:03+1Статическую, естественно. А заполняться и сортироваться будет в compile-time. В результате получится обычный статический массив.
DSarovsky Автор
13.01.2022 17:07А побочной целью было еще и перенести данные во Flash (раз уж они все равно неизменные).
Izaron
13.01.2022 18:16Можно использовать другой способ, который займет столько же памяти.
Для удобства можно считать, что нас вершин 1024 штуки (степень двойки специально), нумерация от 0 до 1023 включительно.
Можно завести `std::array<int, 1024> keys` (ключи отсортированы) и `std::array <int, 1024> values`.
Поиск по ключу займет не более чем 10 сравнений, по одному биту каждый раз. Индексы ключей у нас от `0000000000` до `1111111111`, поэтому надо смотреть ключ посередине - по индексу `1000000000`. Если он больше, то единицу отнимаем. И потом смотрим следующий бит.
int some_key = XXX; int index = 0; for (int i = BYTES - 1; i >= 0; --i) { if (some_key >= keys[index + (1 << i)]) { index += (1 << i); } } return value[index];DSarovsky Автор
13.01.2022 18:30По сути, это еще одна реализация бинарного поиска (кстати, про std::array: std:: что_угодно в микроконтроллерах чаще всего применить не получится, контейнеры точно). Да, с числовыми ключами проще было бы определить массив и искать в нём.
Amomum
14.01.2022 02:02std::array-то почему нет?
Кстати, есть еще такая штука - https://www.etlcpp.com
desertkun
13.01.2022 18:30+1Stm32f103c8t6 предлагает 20 Кб RAM и 64 Кб Flash-памяти.
Спалю годноту, у Stm32f103c8t6 128 кб флеш памяти. У этого мк такой же кристалл, как и Stm32f103c(B)t6, просто вторая половина залочена. Так дешевле выпускать. Простыми манипуляциями компилятора и аплоадера можно легко открыть себе вторую половину.
DSarovsky Автор
13.01.2022 18:32Ого, а я думал, что 128 только у китайских клонов cs32f103c8t6. Круто, спасибо, буду знать и меньше экономить:)
paluke
А статический массив, отсортированный по ключу, чем плох?
Обычно двоичное дерево полезно тем, что в нем вставка/удаление за log(n). Но если дерево неизменяемое, в чем преимущество перед массивом?
DSarovsky Автор
Вы правы, ничем, если речь идет про числовые ключи: в таком случае можно задать упорядоченный массив, по нему бинарный поиск и всё будет хорошо и быстро работать. Первоначальная идея подразумевает ключи строковые и тогда, как я предположил, постоянное сравнение строк при поиске в массиве будет накладным, поэтому обратил внимание на префиксные деревья.
paluke
А как вы NodesComparator для строковых ключей реализовали?
И в Search сравнения?
TypeListSort тоже интересно увидеть
DSarovsky Автор
Приводить в комментариях не хочется, слишком много, шаблонные утилиты — это часть разрабатываемого фреймворка, можно ТУТ посмотреть.
wataru
Но ведь в дереве поиска происходит ровно столько же операций сравнения ключей, неважно что там за ключи. Более того, сравнения идут с теми же самым элементами! Бинарный поиск в массиве — это фактически есть поиск в неявно хранимом бинарном дереве.
Бинарный поиск будет в константном массиве по всем параметрам лучше: и места меньше занимать будет и работать быстрее.
DSarovsky Автор
Вы правы, с числовыми ключами это бессмысленно, но глобальная идея в использовании префиксного дерева, а там сравнение ключей сильно отличается, Patricia, на которое я нацелился, подразумевает сравнение одного лишь бита в каждом узле.
Также к своему стыду признаюсь, что так и не понял, можно ли статический массив разместить во Flash, а доступ к нему получать в runtime? Или придется все равно городить список типов?
lorc
Можно. Достаточно расположить его в секции которая попадет в ROM. Нужно смотреть ld script, но обычно они содержат секции вроде .ro_data
0o00oo00o0
Обработка строк предполагает дополнительные накладные расходы. Если множество ключей известно в момент компиляции и неизменно, тогда можно использовать таблицу дескрипторов с целочисленными ключами, например типа enum. enum значения ключей можно использовать в качестве индексов элементов массива. Тогда и хеш считать не придется.
DSarovsky Автор
Не совсем понял: у нас есть известный набор ключей, а в runtime мы от устройства получаем строку, ее как-то нужно «на лету» преобразовать?
0o00oo00o0
Если вынуждены работать со строками, то да, придется "на лету". Я вижу два варианта:
Можно держать словарь, упорядоченный лексикографически (как альтернатива trie) и по нему запускать бин. поиск. Во втором массиве хранить по соответствующим индексам значения.
Аккуратная хеш-функция + хеш-таблица. Например, если строки короткие то можно считать в позиционной системе s[i] * 26^i. Вычисление хеша - отдельная большая тема. Скорее всего, кто-нибудь уже решил оптимальным образом задачу для коротких строк.
0o00oo00o0
Можете посмотреть
What is the best 32bit hash function for short strings (tag names)?
http://www.orthogonal.com.au/computers/hashstrings/
Пишут, что crc32 подходит хорошо, предлагаются другие варианты. Я бы начал с лексикографически упорядоченного словаря + бин.поиск + массив значений. Если решение не подходит по скорости или памяти, то хеш.функция (напр. crc32) + таблица. Что-нибудь из этого может стать лучшей альтернативой trie.
0o00oo00o0
Большая проблема шаблонной магии - раздутый код, который может не помещаться в кеш инструкций, замедляя выполнение программы. В вашем случае с бинарным деревом я не представляю, как процессор сможет оптимизировать гору ветвлений.
И trie хорошо, когда есть строки с общими префиксами, что не всегда так.
DSarovsky Автор
В этом плане не могу не согласиться, что такая опасность есть. Жаль, мой уровень квалификации не позволяет нормально оценить влияние раздутого кода на выполнение программы. Наверно, если когда-то вздумается тащить всё в продакшн, следует провести качественные эксперименты.
DSarovsky Автор
По поводу кеша, наткнулся на статью из которой подчерпнул, что на значительной части линейки Cortex-M (в частности, и на M3), кеша нет совсем.
bullitufa
Раздутый код? Шаблоны не добавляют код сами по себе! Особенно специализация, тут даже меньше должно быть.
На сколько я помню, префетчеров в армах (мк) нет) Поэтому никакой оптимизации ветвлений) Только кэш инструкций и данных.
Ориентироваться на использование кеша - плохая идея. Практически полное отсутствие детерминированости.
bullitufa
Тогда нужен "решатель" ключ -> индекс массива, по типу unordered_map.
DSarovsky Автор
Кстати интересная мысль! Насколько я помню, несовпадение хешей означает 100% отличия ключей, но совпадение (что очевидно) не гарантирует их равенство. В случае с МК строковых констант будет очень и очень немного, что позволяет надеяться на отсутствие коллизий (+ их на этапе компиляции можно обнаружить) и тогда действительно строковые ключи с большой вероятностью можно превратить в числовые.