Поиск и структуры данных
Поиск можно считать одной из наиболее нужных и часто используемых операций при разработке программного обеспечения. На сегодняшний день известно большое количество алгоритмов и структур данных, обеспечивающих высокую скорость поиска. Пусть и в меньшей степени, но подобные задачи возникают и в сфере разработки ПО для встраиваемых систем, одной из главных особенностей которой является существенная ограниченность системных ресурсов.
В статье предлагается рассмотреть особенности реализации элементарной структуры данных и способы оптимизации в условиях малого объема доступной памяти.
Зачем это автору
В процессе разработки фреймворка для 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++ и получить интересные результаты хотя бы в цифрах.
