Comments 19
А если для неиспользуемых использовать 0xFFFFFFFЕ? ТОгда можно убрать проверку на ноль в цикле. Правда служебные тогда будут располагаться после неиспользуемых — чуть усложнится алгоритм подготовки загрузки.
Хотя, можно же просто неиспользуемые нули в начале массива расположить. Тогда логика работы контроллера вобще не поменяется.
Еще вариант — сортировать по убыванию — тогда нули останутся в конце (возможно это упростит загрузку), а в поиске просто поменять сравнения на противоположные.
Хотя, можно же просто неиспользуемые нули в начале массива расположить. Тогда логика работы контроллера вобще не поменяется.
Еще вариант — сортировать по убыванию — тогда нули останутся в конце (возможно это упростит загрузку), а в поиске просто поменять сравнения на противоположные.
Можно и так. Вероятность того, что попадётся карта с таким номером пренебрежимо мала. С другой стороны, доп. сравнение с нулём в цикле практически ни на что не влияет. Там ведь сравнений не более 11. Изначально мы себе просто задачу упростили на стороне сервера, когда готовили список карт. Делаем выборку из базу, заполняем массив, остальное дописываем нулями. А впоследствии при расширении функционала системы решили по максимуму вписаться в существующую структуру.
А есть разница в скорости читать 1 байт из флэша или блок? Небось как раз накладных задержек бы хватило, и не нужен гемор с перезаписью сортированных кодов??
Не понял, при чём тут гемор с перезаписью кодов? При добавлении нового пользователя в любом случае перезаписывается весь массив в контроллере. Но этот процесс нечастый (пользователей не добавляют каждый день), поэтому проблемы нет. А серверу без разницы в каком виде отдавать список. Он уже из базы получается отсортированный по номеру ключа.
Ну можно поберечь ресурс флэшки и в конец приписать… Скорость больше интересует как меняется, можете написать сколько секунд читаете 3 000 записей за раз?
Промахнулся в ветке. Ответил ниже
Решение «считать количество элементов при записи во флеш» прямо на МК приходит прямо само. Записи всё равно проходят сквозь RAM, добавить один цикл с простым счётчиком, и в итоге рядом с массивом же его и записать.
Так-то так, но что в итоге выиграем? Вместо 11 сравнений будет, например, 10, в случае заполненности массива карт наполовину. Ну а если будет 5 сотрудников в базе, то количество сравнений может быть, конечно, всего 3. Но опять же, это какие-то единицы миллисекунд экономии. Поэтому мы и пошли более простым путём.
У нас во флешке хранится две структуры данных:
1. База пользователей. Она меняется крайне редко. Ресурс в 4 млн. перезаписей исчерпан никогда не будет.
2. Журнал событий. В него пишется постоянно при проходе сотрудников. Там организован кольцевой буфер как раз для равномерного использования всех блоков флеш-памяти.
Само чтение 3000 записей занимает порядка 3 сек. Но там есть ещё накладные расходы из-за того, что мы читаем не последовательно всю память, а каждую запись отдельно. Если считывать весь массив линейно, то это время будет порядка 1,5 сек, что для данной задачи тоже много.
1. База пользователей. Она меняется крайне редко. Ресурс в 4 млн. перезаписей исчерпан никогда не будет.
2. Журнал событий. В него пишется постоянно при проходе сотрудников. Там организован кольцевой буфер как раз для равномерного использования всех блоков флеш-памяти.
Само чтение 3000 записей занимает порядка 3 сек. Но там есть ещё накладные расходы из-за того, что мы читаем не последовательно всю память, а каждую запись отдельно. Если считывать весь массив линейно, то это время будет порядка 1,5 сек, что для данной задачи тоже много.
Предполагается, что база номеров ключей всегда будет отсортированной? Или номера ключей просто выбираются подряд? А если нужно будет несколько их них отключить и, вместо них, создать новые?
В Вашем случае эффективнее использовать Hash Table. Поиск будет о(1).
Да, тоже интересный вариант. Но в данном случае уже особо ускорять нечего. А вот при работе Web-интерфейса мы как раз хеш-таблицу и используем. При формировании динамического содержимого мы вместо текстовых меток подставляем нужные значения. И чтобы не делать громадную кучу сравнений строк просто вычисляем хеш и по нему мгновенно находим требуемое значение.
С хэш тадблицей можно оптимизировать, но для поиска, емнип, там тоже деление пополам и будет применяться. Но зато добавятся коллизии.
Решал такую же задачу как вы — тоже СКУД, тоже PIC18, тоже медленная flash, карт до 96 тыс.
Сначала тоже использовал бинарный поиск «в лоб».
Но с ним были проблемы:
— необходимость перезаписи всего списка карт при малейших изменениях (долго, если контроллеры на rs485)
— временное нарушение консистентности базы на контроллере во время ее перезаписи
— износ flash
В полях были уже десятки тысяч таких контроллеров, надо было как-то решать эти пробемы в т.ч. на них — без возможности апгрейда железа.
В итоге переделал на красно-черное самобалансирующееся бинарное дерево, размещенное в виртуальном адресом пр-ве, которое замаплено в физические сектора flash картой, которая тоже размещена во flash. Это если кратко.
Несмотря на всю мудренность этого решения получилось сделать так, что PIC сам особо про сложности не знает, т.к. знает только как читать. И чтение работает только за логарифмическое время.
Сервер системы же присылает контроллерам апдейты в виде потоков записей в память, финальным из которых подменяется таблица маппинга и так транзакционно все переключается на новый список. Ну там даже не просто список карт, там еще всякие автономноые логики, графики доступа и прочее.
Думаю это самое сложное, что я делал в СКУД. Доволен собой ;)
Сначала тоже использовал бинарный поиск «в лоб».
Но с ним были проблемы:
— необходимость перезаписи всего списка карт при малейших изменениях (долго, если контроллеры на rs485)
— временное нарушение консистентности базы на контроллере во время ее перезаписи
— износ flash
В полях были уже десятки тысяч таких контроллеров, надо было как-то решать эти пробемы в т.ч. на них — без возможности апгрейда железа.
В итоге переделал на красно-черное самобалансирующееся бинарное дерево, размещенное в виртуальном адресом пр-ве, которое замаплено в физические сектора flash картой, которая тоже размещена во flash. Это если кратко.
Несмотря на всю мудренность этого решения получилось сделать так, что PIC сам особо про сложности не знает, т.к. знает только как читать. И чтение работает только за логарифмическое время.
Сервер системы же присылает контроллерам апдейты в виде потоков записей в память, финальным из которых подменяется таблица маппинга и так транзакционно все переключается на новый список. Ну там даже не просто список карт, там еще всякие автономноые логики, графики доступа и прочее.
Думаю это самое сложное, что я делал в СКУД. Доволен собой ;)
Существует элементарное решение, которое не требует никакого быстродействия вообще, где количество пользователей ограничено лишь объёмом используемой энергонезависимой памяти. Просто нужно уметь по-другому смотреть на проблему. Советую почитать книгу Джеральда Надлера и Шозо Хибино «Мышление прорыва».
Хочется заинтриговать человека, чтобы поднапряг мозги, нарастил немножко нейросеть. Пригодится же для будущих решений. Даже в школе нужно уметь задачки решать, а не получать от учителей готовые ответы на все вопросы.
Уже два года прошло. Ну как, догадались как решить задачу? Даю подсказку: Нужно уметь выходить за пределы поля зрения. Смотреть не только на софт и математические алгоритмы, но и на железо и его возможности.
Sign up to leave a comment.
Бинарный поиск в микроконтроллере