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

Question

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

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

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

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

Answer 1

Я думаю, у вас есть несколько вариантов здесь, но еще один, который нужно рассмотреть, это Фильтр Блума . Это может привести к ложным срабатываниям (т. Е. Вы можете исключить идентификатор, который уже использовался, даже если он не использовался), но он может позволить вам выбрать точное количество места, которое вы можете выделить для этих данных.

Answer 2

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

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

Answer 3

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

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

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

С другой стороны, почему вы просто не подсчитываете и не храните последнее выданное число?

Answer 4

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

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

[РЕДАКТИРОВАТЬ] Так как вы обеспокоены коллизиями, должны быть некоторые данные, где коллизия может произойти, например, в именах файлов или что-то подобное. Если очевидный подход (создать имя файла и проверить, существует ли он) слишком медленный, и у вас есть огромные пробелы в «карте размещения», то сгенерируйте случайный идентификатор и проверьте это. Это должно позволить вам найти неиспользуемый идентификатор всего за несколько итераций.

Answer 5

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

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

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

Answer 6

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

Answer 7

о вашем CRC, как алгоритм интереса ...

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

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

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

Если вы любите приключения ...

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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