Описание проекта на buildin: https://buildin.ai/fiit-urfu/44df4cd11-c1fa-4f6e-b08f-f86517699e5f Статья источник: https://ieeexplore.ieee.org/document/10975746

Исследовательский проект: Компактные структуры данных

Исполнитель: Студент ФИИТ УрФУ Цыганов Артём Дмитриевич ФТ-201 Научный руководитель: к.ф.-м.н., доцент Веретенников Александр Борисович

Введение

Актуальность: При работе с огромными массивами пространственных данных классические деревья поиска занимают слишком много оперативной памяти. Компактные структуры (в частности, k²-tree) решают эту проблему, но требуют очень эффективных алгоритмов обхода, так как данные в них сильно упакованы.

Цель проекта: Исследование концепции компактных структур данных и создание оптимизированной реализации алгоритма KNN на языке C++ по материалам выбранной научной статьи.

Задачи проекта:

1. Изучить теоретическую базу k²-tree и алгоритма инкрементального радиуса для поиска KNN.
2. Провести рефакторинг и модернизацию оригинального исходного кода авторов статьи.
3. Разработать оптимизированную версию структуры данных на современном C++.
4. Создать Python-библиотеку для интеграции C++ кода.
5. Написать юнит-тесты и провести замеры производительности.

1. Теоретическая основа: k²-tree и алгоритм KNN

1.1. Как устроено k^2-дерево

Структура данных k^2-tree изначально придумана для того, чтобы очень компактно хранить большие разреженные матрицы (например, графы связей в соцсетях) или координаты точек на карте.

Главная фишка структуры - это рекурсивное деление пространства. Мы берем квадратную сетку с точками размера N x N и делим ее на k x k равных блоков меньшего размера. Процесс идет сверху вниз:

• Кодирование узлов: Если в маленьком блоке есть хотя бы одна точка, этому узлу дерева присваивается единица (1), и мы делим этот блок дальше на такие же k x k частей. Если блок абсолютно пустой, ему присваивается ноль (0), и делить его дальше не нужно.

• Хранение без указателей: В обычных деревьях каждый узел - это тяжелый объект, который хранит ссылки на своих «детей». В k^2-tree никаких указателей нет. Дерево просто упаковывается в два плоских массива битов (нолей и единиц):

  1. Вектор T (Tree): Хранит биты всех верхних уровней дерева. Он показывает саму структуру дерева.
  2. Вектор L (Leaves): Хранит биты самого нижнего уровня (листья дерева). Они показывают, есть ли точка в конкретной минимальной ячейке.

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

1.2. Поиск ближайших соседей (KNN) с увеличивающимся радиусом

Классический поиск K ближайших соседей часто страдает от того, что алгоритму приходится проверять слишком много лишних веток дерева, которые в итоге не подойдут.

В статье, по которой делался проект, используется метод инкрементального (постепенно увеличивающегося) радиуса. Он работает в несколько шагов:

1. Старт: Вокруг точки, для которой мы ищем соседей, очерчивается круг небольшого начального радиуса R.

2. Поиск по дереву: Алгоритм спускается по k^2-дереву, но проверяет только те блоки k x k, которые пересекаются с нашим кругом поиска. Если узел дерева равен 0, мы мгновенно пропускаем всю эту ветку - там точно ничего нет.

3. Проверка результата: * Если внутри круга нашлось нужное количество точек (больше или равно K), алгоритм останавливается и сортирует их по расстоянию.

   • Если точек не хватило, мы немного увеличиваем радиус круга и повторяем поиск на более широкой области.

4. В чем выгода: k^2-tree позволяет очень быстро отсекать пустые пространства на самых верхних уровнях всего по одному биту. Поэтому постепенно расширять радиус поиска получается гораздо выгоднее, чем сразу перебирать всю базу данных. Мы распаковываем и смотрим только те участки дерева, которые находятся близко к точке запроса.

2. Как собирался и переписывался код

2.1. Сборка и очистка исходного кода

• За основу я взял оригинальный код от авторов статьи. С ним было две главные проблемы: во-первых, он был разбит на отдельные куски, которые нужно было связать вместе. Во-вторых, все комментарии и названия функций были на испанском языке, что сильно мешало разбору.

• Я начал с того, что объединил все изолированные части в один нормально работающий проект. В процессе я полностью почистил кодовую базу - убрал лишние, дублирующие друг друга элементы, которые авторы, скорее всего, использовали для своих черновиков. Это сделало проект намного компактнее и понятнее.

2.2. Построчная оптимизация функций

• Я не стал переписывать всю архитектуру проекта с нуля, а пошел по более практичному пути: взял существующие функции и стал разбирать их построчно.

• Я прошелся по каждой критически важной функции и переписал их внутренности под стандарты современного C++. Где-то убрал лишние проверки, где-то упростил условия в циклах и избавился от ненужных операций. Сама математическая логика авторов осталась прежней, но код стал работать намного эффективнее.

2.3. Создание Python-библиотеки

• Чтобы кодом было удобно пользоваться и проводить эксперименты, я скомпилировал C++ код в динамическую библиотеку и написал для нее обертку на Python.
• Получилось удобное разделение: вся тяжелая математика и обход k^2-дерева происходят на низком уровне в C++ с максимальной скоростью, а запускать тесты и работать с результатами можно из простой и гибкой среды Python.

2.4. Проверка корректности с помощью pytest

• После того как я перебрал функции и убрал лишнее, нужно было гарантировать, что алгоритм нигде не ошибается. Для этого я настроил автоматические тесты через фреймворк pytest.

• Тесты работали по следующему принципу: генерировался набор случайных точек, и поиск ближайших соседей запускался одновременно через мое k^2-дерево и через обычный линейный перебор (brute-force). То, что результаты совпали до единой точки во всех тестах, доказало: моя оптимизация функций не сломала логику алгоритма и он работает абсолютно верно.

3. Оптимизация производительности

3.1. Переход на современный C++

• Первым делом я избавился от старых ресурсоемких конструкций в функциях. В оригинальном коде было много мест, где данные копировались впустую или происходили лишние выделения памяти прямо во время работы алгоритма.
• Я переписал эти участки с использованием возможностей современного C++: настроил правильную передачу объектов по ссылкам, убрал ненужные промежуточные переменные и оптимизировал работу с контейнерами. Это помогло избавиться от базовых «тормозов» и подготовило код к главному разгону.

3.2. 32-битная оптимизация циклов

• В исходном коде обход битовых векторов происходил последовательно: алгоритм проверял каждый бит один за другим. Для компактных структур данных это самое критическое узкое место, потому что при поиске приходится делать миллионы таких мелких проверок.
• Я оптимизировал этот процесс, использовав архитектурную особенность современных процессоров - то, что они на уровне железа за один раз работают сразу с целым машинным словом (в данном случае 32 бита). Вместо унылого побитового перебора я переписал циклы так, чтобы они обрабатывали данные пачками по 32 элемента за один шаг.
• Для этого я задействовал низкоуровневые битовые маски и сдвиги. Теперь процессор с помощью простых логических операций проверяет состояние целой группы узлов k^2-дерева за один проход цикла. Это позволило кардинально сократить количество итераций в критически важных местах кода.
• В результате этих двух шагов - чистки логики на уровне языка и битовой оптимизации циклов - и получилось добиться итогового ускорения работы алгоритма в 1.5 раза.

4. Экспериментальное исследование и результаты

4.1. Методика тестирования и бенчмаркинга

Для сравнения производительности исходного кода авторов статьи (версия baseline) и моей оптимизированной версии (NOW) использовалась автоматическая библиотека pytest-benchmark.

Всего было проведено 360 тестов с различными комбинациями параметров: менялся размер входных данных, количество искомых соседей (K) и конфигурация самого k^2-дерева. Во время тестов замерялись минимальное (Min), максимальное (Max), среднее (Mean) и медианное (Median) время выполнения операции в микросекундах (us).

4.2. Анализ результатов замеров

Все тесты можно наглядно разделить на две группы:

1. Микро-нагрузки (маленькие датасеты)

На тестах с минимальным количеством данных (например, конфигурации вида [10-1-1000]) обе реализации работают практически мгновенно - в районе 8-10 микросекунд.

• Здесь оптимизированная версия NOW показывает себя примерно так же, как baseline, или с минимальным отставанием в пределах погрешности.
• Это логично и честно: на крошечных объемах процессор не успевает раскрыть потенциал 32-битных пакетных операций, а на первый план выходят небольшие накладные расходы от вызова C++ кода из-за Python-обертки.

2. Высокие нагрузки (большие датасеты)

Как только алгоритм начинает обрабатывать тяжелые запросы на больших объемах данных, разница становится колоссальной. Рассмотрим несколько показательных примеров из логов:

Тест с параметром 1000:

• baseline: среднее время - 67.39 us, медиана - 77.89 us.
• NOW: среднее время - 50.75 us, медиана - 49.08 us.
• Результат: Скорость работы выросла примерно в 1.58 раза.

Тест с параметром 50000000:

• baseline: среднее время - 272.93 us, медиана - 264.77 us.
• NOW: среднее время - 149.44 us, медиана - 147.39 us.
• Результат: Скорость работы увеличилась почти в 1.8 раза.

4.3. Стабильность работы системы

Отдельно стоит отметить показатель максимального времени (Max). В тяжелых тестах у оригинального кода случались серьезные пиковые задержки (до 792 us), вызванные неэффективным последовательным перебором битов.

В оптимизированной версии пиковое время сократилось более чем в 2.5 раза (с 792 us до 283 us). Это доказывает, что обработка битовых векторов пачками по 32 элемента делает работу алгоритма не просто быстрой, но и стабильной, без внезапных тормозов процессора.

Заключение

В ходе выполнения исследовательского проекта были успешно решены все поставленные задачи:

1. Изучена теоретическая концепция компактного дерева k^2-tree и алгоритма поиска ближайших соседей (KNN) с инкрементальным радиусом.
2. Оригинальный код авторов статьи был очищен от избыточных элементов, полностью переведен на английский язык и модернизирован под стандарты современного C++.
3. Создана удобная гибридная архитектура: тяжелое вычислительное ядро на C++ интегрировано в Python-среду в виде готовой библиотеки, что позволило покрыть проект юнит-тестами через pytest.
4. Реализована низкоуровневая оптимизация циклов, которая обрабатывает данные пачками по 32 бита за одну инструкцию процессора.

Бенчмаркинг подтвердил эффективность предложенного подхода: на больших объемах данных удалось достичь стабильного ускорения работы алгоритма в 1.5-1.8 раза и существенно снизить пиковые задержки. Код полностью готов к работе, легко читается и прошел все проверки на корректность результатов.