Алгоритм для генерации случайного числа

Жесткое кодирование позиции slice не очень гибкое.

Определите индекс первой точки со статусом = 0, а затем разделите данные на основе этого индекса.

var firstStatus0 = data.findIndex( e => e.status === 0);
firstStatus0 = firstStatus0 === -1 ? data.length : firstStatus0;

// Add the valueline path.
var lineGraph2 = lineSvg.append("path")
  .attr("class", "line")
  .attr("d", valueline(data.slice(0, firstStatus0)))
  .attr("stroke", "blue").attr("stroke-width", 2)
  .attr("fill", "none");

var lineGraph1 = lineSvg.append("path")
  .attr("class", "line")
  .attr("d", valueline(data.slice(Math.max(0, firstStatus0 - 1))))
  .attr("stroke", "red").attr("stroke-width", 2)
  .attr("fill", "none");
8
задан Dan Dyer 26 November 2008 в 02:11
поделиться

15 ответов

Никакой Ваш алгоритм не масштабируем. Что я сделал, прежде к номерам выпуска последовательно (+1 каждый раз), и затем передайте их посредством операции "исключающее ИЛИ" для смешивания битов, таким образом дающих мне на вид случайные числа. Конечно, они не действительно случайны, но они смотрят так к пользовательским глазам.


[Редактирование] Дополнительная информация

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

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

[Благодаря Adam Liss & CesarB для exapanding на решении]

18
ответ дан 5 December 2019 в 04:31
поделиться

Я, вероятно, не поймал Вашу точку, но что относительно auto_increments?

0
ответ дан 5 December 2019 в 04:31
поделиться

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

0
ответ дан 5 December 2019 в 04:31
поделиться

Я на самом деле ранее написал статью об этом. Это проявляет тот же подход как ответ Robert Gould, но дополнительно показывает, как сократить блочный шифр к подходящей длине с помощью xor сворачивание, и затем как генерировать перестановки по диапазону, который не является питанием 2, все еще сохраняя свойство уникальности.

1
ответ дан 5 December 2019 в 04:31
поделиться

Надлежащий PRNG (Генератор Псевдослучайного числа) алгоритм будет иметь время цикла, в течение которого это никогда не будет в том же состоянии. При представлении всего состояния PRNG в числе, полученном от него Вы доберетесь, число гарантировало уникальный в течение периода генератора.

Простой PRNG, который делает это, называют 'Линейным Congruential' PRNG, который выполняет итерации формулы:

X(i) = AX(i-1)|M

Используя правильную пару факторов можно получить период 2^30 (приблизительно 1 миллиард) от простого PRNG с аккумулятором на 32 бита. Обратите внимание необходимость во временной переменной 64 бита длиной длиной для содержания промежуточной части 'AX' вычисления. Большинство, если не все компиляторы C будут поддерживать этот тип данных. Необходимо также смочь сделать это с типом числовых данных на большинстве диалектов SQL.

С правильными значениями A и M мы можем получить генератор случайных чисел с хорошими статистическими и геометрическими свойствами. Существует известная статья о записанном Fishman и Moore.

Для M = 2^31 - 1 мы добираемся, может использовать значения ниже для получения PRNG с хорошим длительным периодом (2^30 IIRC).

Хорошие значения A:

742,938,285  
950,706,376  
1,226,874,159  
62,089,911  
1,343,714,438   

Обратите внимание, что этот тип генератора (по определению) не криптографически безопасен. Если Вы знаете последнее число, сгенерированное от него, можно предсказать то, что это сделает затем. К сожалению, я полагаю, что Вы не можете получить криптографическую безопасность и гарантируемую невоспроизводимость одновременно. Чтобы PRNG был криптографически безопасен (например, Blum Blum Shub), он не может выставить достаточное состояние в сгенерированном числе, чтобы позволить следующему числу в последовательности быть предсказанным. Поэтому внутреннее состояние более широко, чем сгенерированное число и (чтобы иметь хорошую безопасность), период будет дольше, чем количество возможных значений, которые могут быть сгенерированы. Это означает, что выставленное число не будет уникально в течение периода.

По подобным причинам то же верно для генераторов длительного периода, таких как вихрь Мерсенна.

1
ответ дан 5 December 2019 в 04:31
поделиться

Мне нравится идея Oddthinking, но вместо того, чтобы выбрать самую сильную хеш-функцию в мире, Вы могли просто:

  • Генерируйте MD5 первых 10 миллионов чисел (выраженный как строки, +some соль)
  • Проверьте на дубликаты офлайн, т.е. перед входом в производство (я предполагаю, что не будет никого),
  • Сохраните дубликаты в массиве где-нибудь
  • Когда Ваше приложение запустится, загрузите массив
  • Когда Вы хотите вставить идентификатор, выбрать следующее число, вычислить его MD5, проверьте, находится ли это в массиве, и если это не использование это как идентификатор в базе данных. Иначе выберите следующее число

MD5 быстр, и проверяющий, принадлежит ли строка массиву, избежит Вас ВЫБОР.

1
ответ дан 5 December 2019 в 04:31
поделиться

Если Вы действительно хотите добраться, "случайные" числа формируются от 0 до 9 999 999, то решение состоит в том, чтобы сделать "рандомизацию" однажды, и затем хранить результат к Вашему диску.

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

$array = range(0, 9999999);
$numbers = shuffle($array);

Вам также нужен указатель на текущую позицию в $numbers (сохраните его в базе данных); запустите с 0 и увеличьте его каждый раз, когда Вам нужно новое число. (Или Вы могли использовать array_shift () или array_pop (), если Вам не нравится использовать указатели.)

1
ответ дан 5 December 2019 в 04:31
поделиться

Проблема состоит в том, что, если Вы генерируете случайные числа, очень возможно произвести дубликаты infinatly.

однако:

<?php
//Lets assume we already have a connection to the db
$sql = "SELECT randField FROM tableName";
$result = mysql_query($sql);
$array = array();
while($row = mysql_fetch_assoc($result))
 {
   $array[] = $row['randField'];
 }
while(True)
 {
   $rand = rand(0, 999999);
   if(!in_array($rand))
     {
       //This number is not in the db so use it!
       break;
     }
 }
?>

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

1
ответ дан 5 December 2019 в 04:31
поделиться

Мой опыт просто использовал RNG в PHP. Я нашел, что с помощью определенного размера числа (я использую интервал, таким образом, у меня есть макс. из 4G). Я запустил некоторые тесты и нашел, что в среднем, в 500 000 повторений, получил 120 единственных дубликатов. Я никогда не получал 3 экз. после выполнения цикла набор времен. Мое "решение" состояло в том, чтобы затем просто вставить и проверить, перестало ли оно работать, затем генерируйте новый идентификатор и пойдите снова.

Мой совет состоит в том, чтобы сделать то же и видеть то, что Ваш уровень аварийности является &c, и посмотрите, приемлемо ли это для Вашего случая.

Это не оптимально, поэтому если у кого-либо есть предложения, я смотрю также:)

Править: Я был ограничен 5 идентификаторами цифры ([a-zA-z0-9] {5,5}), дольше идентификатор (больше комбинации, несколько коллизий). md5 электронной почты почти никогда не конфликтовал бы, например.

1
ответ дан 5 December 2019 в 04:31
поделиться

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

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

1
ответ дан 5 December 2019 в 04:31
поделиться

Принятие:

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

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

2
ответ дан 5 December 2019 в 04:31
поделиться

Хотите чрезмерное решение?

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

Во время разработки генерируйте список всех 10 миллионов чисел в строковой форме.

Дополнительно, выполните некоторое простое преобразование, как добавление постоянной строки к середине. (Это - на всякий случай результат, слишком предсказуемо.)

Передайте их в инструмент, который генерирует Идеальные Хеш-функции, такие как gperf.

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

6
ответ дан 5 December 2019 в 04:31
поделиться

Попробуйте оператор в БРОСКЕ ВЫБОРА mysql (РЭНД () * 1 000 000 AS INT)

3
ответ дан 5 December 2019 в 04:31
поделиться

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

17
ответ дан 5 December 2019 в 04:31
поделиться

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

BTW, почему не просто выпускают идентификатор пользователя последовательно?

1
ответ дан 5 December 2019 в 04:31
поделиться