[Алгоритмы, Программирование микроконтроллеров, Производство и разработка электроники] Бинарный поиск в микроконтроллере
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Алгоритм бинарного поиска или поиска делением пополам известен давно. В данной статье будет рассмотрен пример его «железячной» реализации на 8-битном микроконтроллере и особенностях, которые возникают при этом.Одно время мы выпускали несложный контроллер облачной СКУД на 100 пользователей. В его основе лежал микроконтроллер PIC18F46K22. В качестве памяти для хранения кодов ключей пользователей использовалась FLASH-память с интерфейсом I2C ёмкостью 64 кБ. Сама «флешка» довольно быстрая, но на шине I2C находилась ещё микросхема часов DS1307, которая работает на скорости не выше 100 кбит/сек. Высокой скорости работы нам не требовалось, поэтому в итоге вся шина была запущена на частоте 100 кГц.
Однако со временем мы начали разрабатывать новую версию контроллера, поддерживающего уже 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;
}
Это классический вариант реализации алгоритма, работающий на отсортированном по возрастанию массиве данных. В нашем случае это не составляет проблемы, так как данные грузятся с сервера, который и осуществляет их сортировку перед отправкой в контроллер.О различных частных случаях при реализации бинарного поиска можно почитать в статье:
«Я не могу написать бинарный поиск (https://habr.com/ru/post/146228)».Итак, рассмотрим работу алгоритма. Переменные beg и end задают начальный и конечный индекс массива данных. На каждой итерации мы вычисляем индекс m, который находится посередине между beg и end, и сравниваем требуемое значения ключа с тем, что находится по этому индексу. В этом случае возможны три варианта:
- Если значения совпадают, то мы нашли нужный ключ и можно открывать замок.
- Если номер искомой карты меньше, то следует его искать в левой части массива. Тут мы отбрасываем сразу половину заведомо не подходящих вариантов. Индекс end теперь будет равен m – 1.
- Если номер искомой карты меньше, то следует его искать в правой части массива. Так же отбрасываем сразу половину заведомо не подходящих вариантов, но меняем индекс beg (он будет равен m + 1).
Если в массиве данных вообще нет искомого значения ключа, то нам нужно выйти из цикла. Условием выхода является beg > end.Очень важным является дополнительное условие user.COD == 0 в строке:
if ((pCOD < user.COD) || (user.COD == 0))
Дело в том, что неиспользуемые элементы массива данных мы просто заполняем нулями. Реально это происходит так. Из базы данных получается отсортированная по значению кода карты выборка пользователей. Эта информация записывается в массив данных, начиная с нулевого индекса. Остальные значения дописываются нулями:ИндексЗначение013071311130878021318001321740824229046752291521...029960299702998029990Можно было бы записывать туда значения 0xFFFFFFFF, но его мы используем в качестве сервисного для служебных нужд системы. Поэтому дополнительное условие user.COD == 0 всегда «заставляет» алгоритм искать код в левой половине массива данных.Кто-то может справедливо заметить, что нет смысла тогда вообще обрабатывать эти нулевые значения. Но дело в том, что мы не передаём в контроллер реальное количество карт доступа. Изначально для 100 карт это не имело смысла (поиск и так работал очень быстро), а потом мы просто не стали менять структуру данных. Но, по большому счёту, это и не нужно, так как бинарный поиск очень сильно ускоряет работу.Рассмотрим следующий пример. Пусть у нас имеется полный массив из 3000 записей. Пользователь подносит ключ и мы должны проверить, есть такая карта или нет. При линейном поиске нам понадобится в худшем случае просмотреть все записи. Итого нужно будет сделать 3000 сравнений.А вот при бинарном поиске количество сравнений будет составлять log23000 ≈ 11 шт!Интересно, что если записей будет аж 4 миллиарда, то количество сравнений при использовании бинарного поиска увеличится всего лишь до 32!Попробуем пошагово проверить алгоритм бинарного поиска на вышеприведённой табличке. Допустим, нам требуется найти значение ключа 2174082.ИтерацияbegendmКод искомой картыКод карты в массиве по индексу m102999149921740820201498749217408203074837421740820403731862174082050185922174082060914521740820704422217408208021102174082090942174082229046710032217408213180011133321740822174082В итоге мы за 11 итераций нашли искомое значение. Важно понимать, что 11 итераций это максимальное время поиска. В вышеприведённом примере в случае, если бы мы искали значение 2290467, то количество итераций было бы равно 9.Так в чём преимущество такого решения? В начале статьи я указывал, что алгоритм реализовывался на микроконтроллере. Использование крайне дешёвой памяти с интерфейсом I2C снижает общую себестоимость изделия, а новый алгоритм поиска сильно уменьшает время реакции контроллера.Всегда интересно посмотреть как реализации алгоритмов работают «вживую». Для этого я снял два небольших видео, где показана работа контроллера в двух вариантах: с линейным поиском и бинарным. Нужное значение карты памяти я специально внёс в самый конец списка (индекс 2999), чтобы можно было оценить работы обоих алгоритмов в худшем случае.Вот работа линейного поиска:Извините, данный ресурс не поддреживается. :( А вот бинарного:Извините, данный ресурс не поддреживается. :( Результат, как говориться, на лицо!
===========
Источник:
habr.com
===========
Похожие новости:
- [Разработка веб-сайтов, Программирование, Сетевые технологии, Программирование микроконтроллеров] Разрабатываем web-site для микроконтроллера
- [Алгоритмы, Профессиональная литература] Книга «Совершенный алгоритм. Алгоритмы для NP-трудных задач »
- [Алгоритмы, Машинное обучение, Исследования и прогнозы в IT, Искусственный интеллект] Исследователи изучают, как GPT-3 разбирает входящую почту
- [Математика] Новые квантовые алгоритмы, совершившие прорыв в нелинейных уравнениях (перевод)
- [Информационная безопасность, Производство и разработка электроники] BlackBerry: расцвет и закат эпохи QWERTY-смартфонов
- [Бизнес-модели, Производство и разработка электроники, IT-компании] Японская Renesas ведет переговоры о покупке британской Dialog Semi
- [Производство и разработка электроники, Сотовая связь] Поступила в продажу первая базовая станция LTE и LTE-A российского производства
- [Программирование микроконтроллеров, Процессоры, Игры и игровые приставки] Doom запустили на ПЛИС iCE40
- [Производство и разработка электроники] Продолжение истории одного осциллографа
- [Rust, Производство и разработка электроники, DIY или Сделай сам] Фитнес-трекер для скейта
Теги для поиска: #_algoritmy (Алгоритмы), #_programmirovanie_mikrokontrollerov (Программирование микроконтроллеров), #_proizvodstvo_i_razrabotka_elektroniki (Производство и разработка электроники), #_skud (скуд), #_binarnyj_poisk (бинарный поиск), #_algoritm (алгоритм), #_mikrokontroller (микроконтроллер), #_blog_kompanii_spetspromdizajn (
Блог компании СпецПромДизайн
), #_algoritmy (
Алгоритмы
), #_programmirovanie_mikrokontrollerov (
Программирование микроконтроллеров
), #_proizvodstvo_i_razrabotka_elektroniki (
Производство и разработка электроники
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 00:32
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 Алгоритм бинарного поиска или поиска делением пополам известен давно. В данной статье будет рассмотрен пример его «железячной» реализации на 8-битном микроконтроллере и особенностях, которые возникают при этом.Одно время мы выпускали несложный контроллер облачной СКУД на 100 пользователей. В его основе лежал микроконтроллер PIC18F46K22. В качестве памяти для хранения кодов ключей пользователей использовалась FLASH-память с интерфейсом I2C ёмкостью 64 кБ. Сама «флешка» довольно быстрая, но на шине I2C находилась ещё микросхема часов DS1307, которая работает на скорости не выше 100 кбит/сек. Высокой скорости работы нам не требовалось, поэтому в итоге вся шина была запущена на частоте 100 кГц.  Однако со временем мы начали разрабатывать новую версию контроллера, поддерживающего уже 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; } 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; } «Я не могу написать бинарный поиск (https://habr.com/ru/post/146228)».Итак, рассмотрим работу алгоритма. Переменные beg и end задают начальный и конечный индекс массива данных. На каждой итерации мы вычисляем индекс m, который находится посередине между beg и end, и сравниваем требуемое значения ключа с тем, что находится по этому индексу. В этом случае возможны три варианта:
if ((pCOD < user.COD) || (user.COD == 0))
=========== Источник: habr.com =========== Похожие новости:
Блог компании СпецПромДизайн ), #_algoritmy ( Алгоритмы ), #_programmirovanie_mikrokontrollerov ( Программирование микроконтроллеров ), #_proizvodstvo_i_razrabotka_elektroniki ( Производство и разработка электроники ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 00:32
Часовой пояс: UTC + 5