![](https://habrastorage.org/getpro/habr/upload_files/4dd/8ef/ba6/4dd8efba6cbd0829f2303448975d1c56.png)
Алгоритм бинарного поиска или поиска делением пополам известен давно. В данной статье будет рассмотрен пример его «железячной» реализации на 8-битном микроконтроллере и особенностях, которые возникают при этом.
Одно время мы выпускали несложный контроллер облачной СКУД на 100 пользователей. В его основе лежал микроконтроллер PIC18F46K22. В качестве памяти для хранения кодов ключей пользователей использовалась FLASH-память с интерфейсом I2C ёмкостью 64 кБ. Сама «флешка» довольно быстрая, но на шине I2C находилась ещё микросхема часов DS1307, которая работает на скорости не выше 100 кбит/сек. Высокой скорости работы нам не требовалось, поэтому в итоге вся шина была запущена на частоте 100 кГц.
![](https://habrastorage.org/getpro/habr/upload_files/db4/ec5/c73/db4ec5c73b9d09f6723db3d0550b70e8.png)
Однако со временем мы начали разрабатывать новую версию контроллера, поддерживающего уже 3000 пользователей. Не хотелось сильно менять архитектуру, поэтому основные узлы были сохранены, но при этом был увеличен объём FLASH-памяти до 256 кБ.
И вот тут возник один интересный момент. В первой версии поиск ключа в памяти осуществлялся простым перебором всех 100 ключей. Этот процесс занимал долю секунды и поэтому каких-либо оптимизаций кода не производилось. Но при количестве в 3000 записей это время увеличилось в 30 раз, что оказалось недопустимым, так как у пользователя появлялась неприятная задержка между считыванием карты и открытием замка.
Решить данную проблему можно двумя способами. Первый – аппаратный вариант, предполагающий использование более быстрого интерфейса с «флешкой», например, SPI. Скорости чтения здесь на два порядка выше, чем при использовании I2C. Это, так сказать, решение «в лоб». Неудобство лишь состоит в том, что приходится закладывать в устройство новый компонент, переделывать код и печатную плату. Плюс потребуются дополнительные линии микроконтроллера для подключения такой микросхемы памяти.
Но есть и другой способ – программный. Заключается он в переделке самой процедуры поиска. Изначально она выглядела так:
typedef struct
{
uint32_t COD;
uint8_t nSchedule;
} TSKUD_User;
bool skudFindUserByCode(uint32_t pCOD)
{
TSKUD_User user;
for (uint8_t i = 0; i < SKUD_USERS_COUNT; i++)
{
skudReadUser(i, &user);
if (user.COD == pCOD)
return 1;
}
return 0;
}
Функция skudReadUser считывала блок данных из I2C памяти, далее осуществлялась проверка на совпадение кода.
При ста пользователях в худшей случае (когда код находился в самом конце массива данных) время поиска занимало порядка 0,1 сек. При переходе же к 3000 пользователей время выросло 3 сек!
Поэтому для ускорения функция была переписана следующим образом:
bool skudFindUserByCode(uint32_t pCOD)
{
TSKUD_User user;
int16_t m, beg, end;
beg = 0;
end = SKUD_USERS_COUNT - 1;
while (beg <= end)
{
m = (beg + end) / 2;
skudReadUser(m, &user);
if (pCOD == user.COD)
return true;
if ((pCOD < user.COD) || (user.COD == 0))
end = m - 1;
else
beg = m + 1;
}
return false;
}
Это классический вариант реализации алгоритма, работающий на отсортированном по возрастанию массиве данных. В нашем случае это не составляет проблемы, так как данные грузятся с сервера, который и осуществляет их сортировку перед отправкой в контроллер.
О различных частных случаях при реализации бинарного поиска можно почитать в статье: «Я не могу написать бинарный поиск».
Итак, рассмотрим работу алгоритма. Переменные beg и end задают начальный и конечный индекс массива данных. На каждой итерации мы вычисляем индекс m, который находится посередине между beg и end, и сравниваем требуемое значения ключа с тем, что находится по этому индексу. В этом случае возможны три варианта:
Если значения совпадают, то мы нашли нужный ключ и можно открывать замок.
Если номер искомой карты меньше, то следует его искать в левой части массива. Тут мы отбрасываем сразу половину заведомо не подходящих вариантов. Индекс end теперь будет равен m – 1.
Если номер искомой карты меньше, то следует его искать в правой части массива. Так же отбрасываем сразу половину заведомо не подходящих вариантов, но меняем индекс beg (он будет равен m + 1).
Если в массиве данных вообще нет искомого значения ключа, то нам нужно выйти из цикла. Условием выхода является beg > end.
Очень важным является дополнительное условие user.COD == 0 в строке:
if ((pCOD < user.COD) || (user.COD == 0))
Дело в том, что неиспользуемые элементы массива данных мы просто заполняем нулями. Реально это происходит так. Из базы данных получается отсортированная по значению кода карты выборка пользователей. Эта информация записывается в массив данных, начиная с нулевого индекса. Остальные значения дописываются нулями:
Индекс | Значение |
0 | 1307131 |
1 | 1308780 |
2 | 1318001 |
3 | 2174082 |
4 | 2290467 |
5 | 2291521 |
... | 0 |
2996 | 0 |
2997 | 0 |
2998 | 0 |
2999 | 0 |
Можно было бы записывать туда значения 0xFFFFFFFF, но его мы используем в качестве сервисного для служебных нужд системы. Поэтому дополнительное условие user.COD == 0 всегда «заставляет» алгоритм искать код в левой половине массива данных.
Кто-то может справедливо заметить, что нет смысла тогда вообще обрабатывать эти нулевые значения. Но дело в том, что мы не передаём в контроллер реальное количество карт доступа. Изначально для 100 карт это не имело смысла (поиск и так работал очень быстро), а потом мы просто не стали менять структуру данных. Но, по большому счёту, это и не нужно, так как бинарный поиск очень сильно ускоряет работу.
Рассмотрим следующий пример. Пусть у нас имеется полный массив из 3000 записей. Пользователь подносит ключ и мы должны проверить, есть такая карта или нет. При линейном поиске нам понадобится в худшем случае просмотреть все записи. Итого нужно будет сделать 3000 сравнений.
А вот при бинарном поиске количество сравнений будет составлять log23000 ? 11 шт!
Интересно, что если записей будет аж 4 миллиарда, то количество сравнений при использовании бинарного поиска увеличится всего лишь до 32!
Попробуем пошагово проверить алгоритм бинарного поиска на вышеприведённой табличке. Допустим, нам требуется найти значение ключа 2174082.
Итерация | beg | end | m | Код искомой карты | Код карты в массиве по индексу m |
1 | 0 | 2999 | 1499 | 2174082 | 0 |
2 | 0 | 1498 | 749 | 2174082 | 0 |
3 | 0 | 748 | 374 | 2174082 | 0 |
4 | 0 | 373 | 186 | 2174082 | 0 |
5 | 0 | 185 | 92 | 2174082 | 0 |
6 | 0 | 91 | 45 | 2174082 | 0 |
7 | 0 | 44 | 22 | 2174082 | 0 |
8 | 0 | 21 | 10 | 2174082 | 0 |
9 | 0 | 9 | 4 | 2174082 | 2290467 |
10 | 0 | 3 | 2 | 2174082 | 1318001 |
11 | 3 | 3 | 3 | 2174082 | 2174082 |
В итоге мы за 11 итераций нашли искомое значение. Важно понимать, что 11 итераций это максимальное время поиска. В вышеприведённом примере в случае, если бы мы искали значение 2290467, то количество итераций было бы равно 9.
Так в чём преимущество такого решения? В начале статьи я указывал, что алгоритм реализовывался на микроконтроллере. Использование крайне дешёвой памяти с интерфейсом I2C снижает общую себестоимость изделия, а новый алгоритм поиска сильно уменьшает время реакции контроллера.
Всегда интересно посмотреть как реализации алгоритмов работают «вживую». Для этого я снял два небольших видео, где показана работа контроллера в двух вариантах: с линейным поиском и бинарным. Нужное значение карты памяти я специально внёс в самый конец списка (индекс 2999), чтобы можно было оценить работы обоих алгоритмов в худшем случае.
Вот работа линейного поиска:
А вот бинарного:
Результат, как говориться, на лицо!
alexxisr
А если для неиспользуемых использовать 0xFFFFFFFЕ? ТОгда можно убрать проверку на ноль в цикле. Правда служебные тогда будут располагаться после неиспользуемых — чуть усложнится алгоритм подготовки загрузки.
Хотя, можно же просто неиспользуемые нули в начале массива расположить. Тогда логика работы контроллера вобще не поменяется.
Еще вариант — сортировать по убыванию — тогда нули останутся в конце (возможно это упростит загрузку), а в поиске просто поменять сравнения на противоположные.