Я сейчас пытаюсь реализовать алгоритм выбора уникального
(16-битный) идентификатор. Задача состоит в том, чтобы сделать это быстрым способом, который
не использует слишком много памяти. Список используемых в настоящее время идентификаторов
определяется путем сканирования внешнего флэш-устройства с помощью последовательности
SPI транзакции и, следовательно, является относительно медленным процессом. Также,
алгоритм будет работать на небольшом микроконтроллере, поэтому я не могу
на самом деле просто прочитайте все записи в ОЗУ и обработайте их там.
Мысли, которые у меня были до сих пор:
- Выберите номер, затем просмотрите список и посмотрите, используется ли он. Полоскание
и повтори. Страдает от того, что довольно медленно (особенно если
много файлов).
- Как и выше, но выберите число, используя генератор псевдослучайных чисел
с соответствующим семенем. Преимущество в том, что оно меньше
вероятно, что будет так много итераций.
- Сканирование по списку и заполнение массива всеми записями.
найденный. Сортируйте это, и тогда это становится тривиальным. Это может использовать
огромное количество памяти.
- Используйте огромную (хорошо, нелепо огромную) битовую маску. На самом деле, нет
практичны.
- Примите, что срок службы инструмента таков, что он будет брошен
прочь или «отформатирована» задолго до того, как она записала 65534 файла во Flash,
так что просто сохраните самое высокое значение, использовавшееся до сих пор во флэш-памяти или в резервной памяти, и сохраните
приращение. Честно говоря, это, вероятно, будет работать очень хорошо для этого
конкретное применение.
В данный момент я на грани использования второго или пятого,
но мне было бы интересно узнать, есть ли у кого-нибудь другие мысли. Я бы хотел
думаю, что есть алгоритм, похожий по форме на CRC, который может быть использован для
обработать каждое число по очереди и дать четкое представление о числе, которое не было
используется, но я понятия не имею, как это может работать.