Генерация неповторяющихся случайных чисел

Question

Я хочу создать функцию в C. Она будет возвращать случайное целое число в диапазоне N, например: - rand ()% N;но дело в том, что я хочу отслеживать уникальность.Я не хочу, чтобы числа повторялись.но я также могу сделать это, создав массив и скопировав в него сгенерированные целые числа.например: - array[count] = rand() % N; и каждый раз проверять, было ли сгенерированное число уже внутри него или нет.(просто ища его внутри массива []);Это простой, но правильный подход.это займет много, если и для;чтобы это работало.это лучшее, что я могу придумать.

---

Дело в том, что я хочу получить самое лучшее / оптимизированное решение для этой проблемы.Каков будет наиболее эффективный способ сделать это?

позволяет очистить некоторые вещи: - я хочу установить некоторый текст в UILabel из NSArray, который всегда уникален.мой NSArray получает данные из Plist, и мой Plist содержит более 1000 записей.если я хочу сделать это много раз, это повлияет на производительность, поэтому я хочу эффективный способ сделать это.

Answer 1

Звучит так, как будто вы действительно хотите случайную перестановку числа 1..N. Итак, заполните массив последовательными целыми числами 1..N, а затем перемешайте массив. Есть хорошо известные алгоритмы тасования , которые вы можете посмотреть.

Answer 2

Четыре варианта, все из которых O (1) в памяти и во времени:

1. Просто увеличьте глобальный счетчик.Поскольку вам нужна уникальность, вы все равно не можете генерировать случайные числа.
2. Генерируйте число из набора, достаточно большого, чтобы повторение числа было крайне маловероятным.64 бита достаточно для уникальности приложения;128 битов достаточно для глобальной уникальности.Вот как UUID s работает.
3. Если вариант 1 не является «случайным» для вас, используйте хэш CRC-32 указанного глобального (32-немного) счетчик.Существует однозначное отображение (биекция) между N-битными целыми числами и их CRC-N, поэтому уникальность все равно будет гарантирована.
4. Создание чисел с использованием регистра сдвига линейной обратной связи .Это N-битные счетчики, которые считаются «случайным» (хотя и явно детерминированным) образом.Для ваших целей это будет существенно более быстрая версия варианта 3.

Answer 3

Вместо массива вы можете использовать супер быстрый эффективный фильтр Блума .Если вы генерируете какое-то большое количество чисел, это будет ПУТЬ быстрее, чем проходить по массиву.

Answer 4

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

Answer 5

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

Например, если у вас есть список из 1… 10, когда вы заполнили восемь элементов, осталось только два элемента (скажем, 7 и 9), теперь каждый раз, когда вы генерируете случайное число, оно генерирует неуникальное число в 80% случаев и имеетсканировать по крайней мере шесть записей, прежде чем обнаруживать дубликат.

Возможно, в некоторых библиотеках есть даже лучшие методы, но лучшим способом, чем в вопросе, было бы создать (связанный) список элементов,выберите один наугад, удалите и добавьте его в новый список.Таким образом, каждый раз, когда вы выбираете один случайный, он гарантированно будет уникальным, потому что использованных больше нет в пуле.