Справочники, или словари — обычно большие объёмы статических данных, адресуемые и не модифицируемые при работе программы. Как правило, подготавливаются или загодя, при разработке, или вне программы, или в специальных её режимах. Зачастую с ними обращаются как с обычными структурами, однако можно организовывать их и иначе — так, чтобы работа с ними шла вообще без резервирования памяти и каких‑либо лишних операций, а в памяти они занимали минимально возможный объём.
Я Андрей Коваленко, или Keva. Сделал поисковые движки Рамблера и украинской Меты. Последние годы работал с компанией МойОфис, где разработал корпоративный поиск.
Продолжу разговор о строительстве поисковых машин заметкой про эффективность организации так называемых словарей или справочников — статических данных key:value с минимальным временем доступа и сжатыми требованиями к ресурсам.
Впервые я реализовал такой справочник в 1995 году при разработке словарной системы, где предварительно размеченный словарь был преобразован в объектный код и представлен динамической библиотекой windows (.dll) — это был проект «Русский Филолог», второй мой коробочный продукт после Прописи.
Основные достоинства статического представления словарей я уже перечислил выше: минимум объёма, отсутствие операций резервирования памяти при обращении к ним, отсутствие какой‑либо инициализации. Давайте теперь по шагам построим такой словарь, но так, чтобы ещё и обращение к нему занимало минимум времени.
Пусть у нас есть простая сортированная таблица, где персонажам — именам поставлены в соответствие идентификаторы, 525 штук:
Персонаж | Номер |
Abel | 1 |
Abraham | 2 |
Ada | 3 |
... | |
Winnie | 525 |
Это могут быть некоторые внешние по отношению к программе данные произвольного размера или статическая таблица — неважно. И пусть нам предстоит искать номера записей по именам.
Для наглядности запишем эту таблицу в виде инициализированной структуры:
const struct Person { const char* name; int id; } persons[] = { { "Abel", 1 }, { "Abraham", 2 }, { "Ada", 3 }, ... { "Winnie", 525 } };
В таком виде, зная, что данные отсортированы по первому полю 'name', можно искать по ним двоичным поиском, выполняя log₂N сравнений строки со строкой. И давайте сразу ещё и сериализуем этот массив так, чтобы можно было искать по его дампу тем же алгоритмом. Для этого добавим к этому массиву в сериализованной форме индекс с фиксированным размером элемента (uint16). Для этого определим методы его сериализации:
template <size_t N> size_t GetBufLen( const Person (&names)[N] ) ... template <class O, size_t N> O* Serialize( O* o, const Person (&names)[N] ) ...
Полный код сериализации, примеров и измерений лежит на github.
Результатом будет blob, где в первых двух байтах лежит количество элементов (525), далее таблица из 525 16-битных смещений реальных записей (младший байт + старший байт), после чего собственно записи переменной длины (asciiz‑строка и компактно сериализованный id). Результирующий размер — 5525 байт. Случайно так получилось, честно!
Выполним миллион поисков случайных элементов в один поток разными способами, измерив время исполнения в миллисекундах.
Метод | ms на 106 поисков |
std::find_if() — оптимизированный поиск прямым перебором слева направо | ~510 ± 20 |
std::lower_bound() — двоичный поиск в массиве средствами стандартной библиотеки | 85 ± 5 |
Рукописный двоичный поиск в сортированном массиве — классическая дихотомия до схождения границ или найденного элемента | 70 ± 5 |
Рукописный двоичный поиск в дампе сортированного массива | 71 ± 5 |
std::lower_bound() по очевидным причинам в несколько раз быстрее, чем std::find_if() - это двоичный поиск против прямого просмотра, пусть и реализованный [в библиотеке gcc] пачками по 4 элемента.
Рукописный двоичный поиск также заметно быстрее шаблонного метода из стандартной библиотеки - но это тоже понятно: std::lower_bound() оперирует методом сравнения is_less(...), что ведёт к лишним вызовам функции сравнения строк (нужен, как минимум, финальный вызов, чтобы понять, совпадает ли ключ найденной границы с искомым) , тогда как в рукопиской реализации сравнение делается однократно, а его результат (<=>) используется для принятия решения.
Приятно, что поиск в компактном дампе такого массива, не нуждающийся в какой-либо хитрой загрузке и настройке данных, по времени исполнения практически не отличается от поиска в оптимизированных компилятором данных с идеальным выравниванием. Это означает, что динамически сгенерированные словари можно использовать без ущерба производительности и с заметной экономией ресурсов.
В следующей заметке построим более эффективное представление такого словаря в виде базисного дерева (radix tree, patricia), тоже сериализуем и оценим скорость поиска.