Отсортируй список по возрастанию («Телесистемы»: Конференция «Микроконтроллеры и их применение»)

Разработка, производство и продажа радиоэлектронной аппаратуры

| Карта сайта | Пишите нам | В избранное

Требуется программист в Зеленограде
- обработка данных с датчиков; ColdFire; 40 тыс.
e-mail:jobsmp@pochta.ru

Телесистемы | Электроника | Конференция «Микроконтроллеры и их применение»

Отсортируй список по возрастанию

Отправлено mandigit (91.79.39.195) 11 августа 2010, г. 18:10
В ответ на: Я по теме. Приходилось ли кому нибудь сравнивать пришедший из линии или от считывателя ключ/пароль/ID с "белым" списком состоящим из например 256 разрешенных. Простой перебор положим, не проходит по времени. Нужны хитрые методы, наверно размазывать ключи по памяти придется. Байтов в каждом ключе, положим 8. Вполне домофонная задача, СКУД конечно. Где почитать или готовенькое посмотреть? отправлено VasilyS 10 августа 2010, г. 21:21

бьешь в центр списка, понимаешь выше надо искать или ниже, бьешь в середину ...

второй вариант - ветвление бинарное

третий вариант - в лоб решать. Учитывая вероятность попадания в партию последовательных ID проверку проводить с младшего байта. В общем случае не потребуется проверять все 8 байт для того что-бы сделать вывод, что ключ не подходит.

Составить ответ | Вернуться на конференцию

Ответы

Уже научили добрые люди. ID имеют разную длину поэтому младшие байты у коротких занулены. Ищу со старшего. Уже написал, вышло ~60 uS. - VasilyS (11.08.2010, 18:29:3 80.92.96.25, пустое)
- Кстати, этот алгоритм позволяет проверить только 255 "белых" ключа. Но за 7 итераций..))) - quark (13.08.2010, 09:38:12 79.139.184.12, пустое)