Выбор уникального идентификатора в C для встроенного приложения

Question

В настоящее время я пытаюсь реализовать алгоритм для выбора уникального идентификатора (16-разрядный). Задача состоит в том, чтобы сделать это быстро, так как не использует слишком много памяти. Список используемых в настоящее время идентификаторов - , определяемый путем сканирования внешнего флэш-устройства через последовательность транзакций SPI и, следовательно, является относительно медленным процессом. Кроме того, алгоритм будет работать на микросхеме с малым размером, поэтому я не могу действительно просто читать все записи в ОЗУ и обрабатывать их там.

Мысли у меня были до сих пор являются:

1. Выберите номер, а затем просканировать список и посмотреть, если он используется. Промойте и повторите. Страдает от довольно медленного (особенно если - это много файлов).
2. Как указано выше, но выберите номер, используя генератор псевдослучайных чисел с соответствующим семенем. Это имеет то преимущество, что меньше , вероятно, будет такое большое количество итераций.
3. Сканировать по списку и заполнить массив всеми найденными . Сортируйте его, а затем он становится тривиальным. Это может использовать огромный объем памяти .
4. Используйте огромную (хорошо, смешно огромную) битную маску. Не совсем практичный.
5. Примите, что срок службы инструмента таков, что он будет выброшен или «отформатирован» задолго до того, как он набрал 65534 файлов на Flash, , поэтому просто сохраните наивысшее значение, используемое до сих пор во Flash или Резервное копирование и сохранение приращений. Честно говоря, это, вероятно, будет работать достаточно хорошо для данного приложения .

На данный момент, я доходящей к использованию либо второй или пятый, , но мне было бы интересно знать, если кто имеет какие-либо другие мысли. Я бы хотел, чтобы считал, что существует алгоритм, похожий по форме на CRC, который можно использовать для обрабатывать каждый номер по очереди и дать справедливое представление о количестве, которое не было , но я понятия не имею как это может сработать.

Answer 1

У меня есть несколько вариантов здесь, но еще один вопрос - Bloom Filter. У этого есть вероятность ложных срабатываний (т. Е. Вы можете исключить идентификатор, который уже использовался, хотя он еще не был), но он может позволить вам выбрать точный объем пространства, которое вы можете посвятить этим данным.

Answer 2

Пойду с 2. Будь осторожен, как вы выбираете генератор и семена. Все псевдо-числовые последовательности повторяют себя после некоторого количества итераций. Поэтому вам нужно проверить, что он не повторится слишком рано.

Answer 3

Я предполагаю, что устройство FLASH не снимается из-за упоминания SPI, но карты IIRC SD имеют режим доступа SPI, так что это может быть неверно.

Если FLASH постоянна, и у вас есть надежное, энергонезависимое место для запоминания последнего идентификационного номера, то это, вероятно, то, что нужно сделать. Это определенно быстрая и низкая память во время выполнения. Это должно быть легко объяснить, реализовать и протестировать.

Если FLASH является съемным, то использование генератора псевдослучайных чисел и тестирование на столкновение - это, вероятно, путь. Предполагая, что ваши номера хорошо распределены, ваши шансы на столкновение легко предсказать из общего объема использования. Просто выберите генератор с прилично длинным интервалом повторения. Это может быть хорошей идеей, чтобы высмеять это в симуляции в качестве приемочного теста для выбранного алгоритма.

Answer 4

Я бы попробовал вариант 3. Вместо хранения отсортированного массива значений я бы сохранил отсортированный массив диапазонов.

Answer 5

Мне интересно, почему вы не просто сохраняете последний идентификатор и увеличиваете его. Есть ли причина, почему вы колеблетесь? Вы не даете ответа на свой вопрос, просто общее беспокойство.

Если вам необходимо, чтобы идентификатор был несколько случайным по соображениям безопасности, используйте генератор случайных чисел и сохраните текущие значения регистра генератора во флэш-памяти. Таким образом, вы можете загрузить их для следующего идентификатора, который гарантирует, что вы получите полную длину цикла без повторов, если вы тщательно выберете свой алгоритм.

[EDIT] Поскольку вы столкнулись с столкновениями, должны быть некоторые данные, в которых может произойти столкновение, например, в именах файлов или некоторых таких. Если очевидный подход (создать имя файла и проверить, существует ли он) слишком медленный, и у вас есть огромные пробелы в «карте распределения», тогда сгенерируйте случайный идентификатор и проверьте это. Это должно позволить вам найти неиспользуемый ID всего несколькими итерациями.

Answer 6

Сколько у вас RAM? Это немного сложно сказать, «встроенный» может означать так много в наши дни. :) Растровое изображение потребует 8192 байт на время генерации и гарантирует идеальные результаты каждый раз.

Я также рассматривал какое-то «разреженное» растровое изображение, но я не знаю подходящей структуры данных, но, возможно, стоит изучить.

Answer 7

Если оперативной памяти недостаточно, чтобы реализовать растровое изображение, достаточно большое для 64 тыс. Записей, количество сканирований через FLASH для поиска неиспользуемого идентификатора может быть уменьшено за счет использования меньшего временного растрового изображения для каждого сканирования. 16-разрядная растровая карта может записывать найденные идентификаторы в диапазоне 0-255 на первом проходе, 256-511 на втором сканировании и т. Д. В конце каждого сканирования, если в битовой карте есть хотя бы один немаркированный бит, сделанный. Я считаю, что это будет хорошо работать в сочетании с использованием случайного пускового диапазона.

С другой стороны, если бы у меня была высокая уверенность в варианте 5, я мог бы просто пойти с этим.

Answer 8

Продолжайте подсчет последовательного идентификатора.
Запустите идентификатор через MD5.
Используйте самые младшие 16 бит.

Теория заключается в том, что MD5 создает другой хеш для каждого входа. Самые младшие 16 бит должны быть такими же «случайными», как весь хеш.

Answer 9

Если бы вы могли использовать более крупные идентификаторы, тогда 5 были бы без проблем.

Answer 10

Об КПР, как алгоритм интерес ...

Похоже, что вы ищете алгоритм, который будет работать через случайный список менее 64К 16-разрядных чисел и генерировать новый 16-битный номер не уже в списке; предпочтительно делать это за один проход через данный список.

Если последовательность, в которой идентификаторы освобождены, не имеет никакого отношения к последовательности, в которой они выделены (например, я чувствую, что это ваш случай), вы ничего не можете сделать с генерацией или распределением идентификаторов для получения вашего алгоритма.

Лучшая ставка тогда кажется 5 из вашего списка.

Если вы предприимчивы ...

и, если вы можете повторно номер ваши идентификаторы (т.е. изменить выделенный идентификатор другого незанятого ID), вы можете запустить «дефрагментацию» вид итерации один раз в некоторое время, чтобы переместить все выделенные идентификаторы для более низких значений и найти самый высокий свободный идентификационный номер для следующего выделения. Это поможет запомнить общее количество распределений и освобождений, сделанных с момента последнего такого «дефрагментации». Выделяйте инкремент последовательно, начиная с 0.

Таким образом, вам нужно запомнить всего 3 беззнаковых коротких целых числа в памяти. И да, возьмите немного дорогостоящую итерацию перераспределения раз в то время, основываясь на их значениях.

Answer 11

Другим вариантом является сохранение файла действительных идентификаторов на флеш-накопителе. Таким образом, вы не каждый раз запрашиваете все возможности. Если вам нужны случайные идентификаторы, то рандомизируйте файл. Храните смещение до последнего в качестве первого номера в файле. Когда вам это нужно, удалите последнее из файла, а когда вы его освободите, добавьте его обратно в файл. При смещении и флэш-накопителе это должно быть почти постоянное время, независимо от количества оставшихся идентификаторов. В качестве бонуса смещение в начале подскажет вам, сколько идентификаторов у вас осталось, если вам нужно знать, что в любой момент. Недостатком было бы то, что вам нужно получить доступ к флэш-памяти для каждого идентификатора (постоянный, но все же доступ) и как обрабатывать случай ошибки, если файл отсутствует.

Answer 12

Используйте Maximal Linear Feedback Shift Register и сохраните последнее значение, которое вы раздавали. LFSR будет, учитывая определенную начальную точку (не считая нуля), даст вам все числа в последовательности 1..2^n в псевдослучайном порядке. Если вы начнете с k-го элемента, вы всегда получите тот же k + 1-й элемент. Реализация крошечное:

if (IsEven(sequence)) { 
    sequence /= 2; 
} 
else { 
    sequence = (sequence/2)^feedback; 
} 

, где обратная связь битовый шаблон из таблицы максимальных обратных связей для числа битов, которые вы хотите создать. Это означает, что для генерации следующего числа вы читаете последний выданный номер, запускаете его через указанный выше код и затем используете его.

В качестве альтернативы, почему вы просто не подсчитываете и не сохраняете последний выданный номер?