Умный способ генерации уникального случайного числа

Ответ 1

Вы можете создать таблицу со всеми возможными числами в ней, дать записи поле 'used'.

• Выберите все записи, которые не были использованы
• Выберите случайное число (r) между 1 и числом записей
• Записать номер записи r
• Получите свое "случайное значение" из записи
• Установите флаг 'used' и обновите db.

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

Ответ 2

Вы можете использовать либо линейный конгруэнтный генератор (LCG), либо регистр сдвига линейной обратной связи (LFSR). Google или wikipedia для получения дополнительной информации.

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

Обновление: я должен добавить, что нет необходимости предварительно вычислять или предварительно хранить предыдущие значения каким-либо образом, вам нужно сохранить прежнее начальное значение (single int) и рассчитать "по требованию" следующее число в последовательности. Конечно, вы можете сохранить цепочку предварительно рассчитанных чисел в свою БД, если это необходимо, но это необязательно.

Ответ 3

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

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

Ответ 4

Использовать генераторы псевдослучайных чисел.

Например, линейный конгруэнтный генератор случайных чисел

(если приращение и n взаимно просты, тогда код будет генерировать все числа от 0 до n-1):

    int seed = 1, increment = 3;
    int n = 10;

    int x = seed;
    for(int i = 0; i < n; i++)
    {
        x = (x + increment) % n;
        Console.WriteLine(x);
    }

Вывод:   4   7   0   3   6   9   2   5   8   1

Основные генераторы случайных чисел

Mersenne Twister

Ответ 5

Использование этого алгоритма может быть подходящим, хотя его память потребляет: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Поместите числа в массиве от 1 до 99999999 и сделайте перетасовку.

Ответ 6

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

Вы генерируете 32-битное целое число, тогда как для достижения уникальности вам нужно гораздо большее число в терминах около 128 бит, которое использует GUID размера, которые гарантированно всегда будут глобально уникальными.

Ответ 7

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

Искусство программирования, Том 2: Семинумерные алгоритмы

Дональдом Э. Кнутом. Глава 3 касается случайных чисел.

Ответ 8

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

Вы отметили вопрос с помощью С#, поэтому я предполагаю, что вы используете С# для генерации случайного числа. Возможно, подумайте о том, чтобы получить базу данных для генерации случайного числа в хранимой процедуре и вернуть ее.

Ответ 9

Вы можете просто разместить свои номера в наборе. Если размер набора после генерации ваших N чисел слишком мал, сгенерируйте еще несколько.

Проведите несколько пробных запусков. Сколько чисел вы должны генерировать в среднем? Попытайтесь найти оптимальное решение компромисса "сгенерируйте слишком много чисел" / "слишком часто проверяйте дубликаты". Это оптимальное число M, так что после генерации M чисел ваш набор, скорее всего, будет содержать N уникальных номеров.

Oh и M также можно вычислить: если вам нужен дополнительный номер (ваш набор содержит N-1), тогда вероятность случайного числа, уже входящего в набор, равна (N-1)/R, с R являясь диапазоном. Я собираюсь перебраться сюда, так что вам придется это выяснить самостоятельно (но этот интересный материал делает программирование забавным, нет?).

Ответ 10

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

id = startValue + (totalNumberOfAccounts * inctrementalNumber)

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

id = startValue + (totalNumberOfAccounts * inctrementalNumber) + totalConflicts

Ответ 11

Я должен был сделать что-то подобное раньше (создайте "случайно выглядящий" номер для части URL-адреса). То, что я сделал, это создать список случайно сформированных ключей. Каждый раз, когда он нуждался в новом номере, он просто произвольно выбирал число из ключей. Count и XOR - ключ и заданный порядковый номер, затем выводил значение XORed (в базе 62) с префиксом индекса ключей (в базе 62). Я также проверяю вывод, чтобы он не содержал никаких ничтожных слов. Если он просто возьмет следующий ключ и пойдет вторым. Расшифровка номера одинаково проста (первая цифра является индексом используемого ключа, простым XOR и все сделано).

Мне нравится andora answer, если вы создаете новые числа и, возможно, использовали его, если бы я знал. Однако, если бы я сделал это снова, я бы просто использовал UUID. Большинство (если не каждая) платформа имеет метод их генерации, а длина - не проблема для URL-адресов.

Ответ 12

Вы можете попробовать перетасовать набор возможных значений, затем последовательно их использовать.

Ответ 13

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

Но, как я уже сказал, мне нравится решение Лазару - я считаю, что ваш лучший выбор для большинства сценариев.

Ответ 14

function getShuffledNumbers(count) {
 var shuffledNumbers = new Array();
 var choices = new Array();
 for (var i = 0; i<count; i++) {
  // choose a number between 1 and amount of numbers remaining
  choices[i] = selectedNumber = Math.ceil(Math.random()*(99999999 - i));
  // Now to figure out the number based on this selection, work backwards until
  // you figure out which choice this number WOULD have been on the first step
  for (var j = 0; j < i; j++) {
   if (choices[i - 1 - j] >= selectedNumber) {
    // This basically says "it was choice number (selectedNumber) on the last step,
    // but if it greater than or equal to this, it must have been choice number
    // (selectedNumber + 1) on THIS step."
    selectedNumber++;
   }
  }
  shuffledNumbers[i] = selectedNumber;
 }
 return shuffledNumbers;
}

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

Ответ 15

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

Ответ 16

• создайте и сохраните ind db две перетасованные версии (SHUFFLE_1 и SHUFFLE_2) интервала [0..N), где N = 10 000,

• всякий раз, когда создается новый порядок, вы назначаете его id следующим образом:

ORDER_FAKE_INDEX = N * SHUFFLE_1 [ORDER_REAL_INDEX/N] + SHUFFLE_2 [ORDER_REAL_INDEX% N]

Ответ 17

Я также пришел с такой же проблемой, но на С#. Я, наконец, решил. Надеюсь, что это сработает и для вас.

Предположим, что мне нужно случайное число от 0 до некоторого MaxValue и наличие случайного объекта типа random.

int n=0;
while(n<MaxValue)
{
   int i=0;
   i=random.Next(n,MaxValue);
   n++;
   Write.Console(i.ToString());
}

Ответ 18

По линии подбора мы можем получить, например. 6 не повторяющихся случайных чисел для диапазона, например. От 1 до 100.

var randomNumbers = Enumerable.Range(1, 100)
    .OrderBy(n => Guid.NewGuid())
    .Take(6)
    .OrderBy(n => n);

Ответ 19

глупый способ: создать таблицу для записи, сохранить все онемение первым и их каждый раз, когда используется numble, и пометить его как "использованный"

Ответ 20

System.Random rnd = new System.Random();
IEnumerable<int> numbers = Enumerable.Range(0, 99999999).OrderBy(r => rnd.Next());

Это дает случайную перетасовку коллекции int в вашем диапазоне. Затем вы можете перебирать коллекцию по порядку.

Приятная часть этого заключается в том, что вы фактически не создаете всю коллекцию в памяти.

См. комментарии ниже - это сгенерирует всю коллекцию в памяти, когда вы перейдете к первому элементу.