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

Стандартный линейный Congrument Converal Number, последовательность семян генератора не может повторяться, пока не будет генерироваться полный набор чисел из исходного значения семян. Затем он должен повторить именно.

Внутреннее семя часто большая (48 или 64 бита). Сгенерированные числа меньше (обычно 32 бита), потому что весь набор битов не случайны. Если вы следуете значениям семян, они сформируют отчетную не повторяющуюся последовательность.

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

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

Вы говорите, что вы храните цифры в базе данных.

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

Примеры

MySQL:

SELECT column FROM table
ORDER BY RAND()
LIMIT 1

PostgreSQL:

SELECT column FROM table
ORDER BY RANDOM()
LIMIT 1

Это функция проектировать калиток. Класс можно использовать для связывания стилей и компонентов.

<form wicket:id="form" id="form>

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

Вы просто пытаетесь сократить количество запросов к базе данных или ищете умное решение?

Если это первое, я бы определенно пошел с кэшированием. Будет ли кэширование фрагментов работать в вашем случае? Если нет, возможно, вы могли бы поместить кэширование в код тэга шаблона (предполагая, что это не один из собственных тегов шаблона Джанго, которые вы используете)?

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

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

import random

class NonRepeatingRandom(object):

    def __init__(self, maxvalue):
        self.maxvalue = maxvalue
        self.used = set()

    def next(self):
        if len(self.used) >= self.maxvalue:
            raise StopIteration
        r = random.randrange(0, self.maxvalue - len(self.used))
        result = 0
        for i in range(1, r+1):
            result += 1
            while result in self.used:
                 result += 1
        self.used.add(result)
        return result

    def __iter__(self):
        return self

    def __getitem__(self):
        raise NotImplemented

    def get_all(self):
        return [i for i in self]

>>> n = NonRepeatingRandom(20)
>>> n.get_all()
[12, 14, 13, 2, 20, 4, 15, 16, 19, 1, 8, 6, 7, 9, 5, 11, 10, 3, 18, 17]

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

Если они не должны быть случайными, но просто не очевидно линейные (1, 2, 3, 4, ...), то вот простой алгоритм:

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

max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
    previous_serial += step
    previous_serial %= max_value
    print "Serial: %09i" % previous_serial

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

s = set()
with open("test.txt", "w+") as f:
    previous_serial = 0
    for i in xrange(0, 2711):
        previous_serial += 1811
        previous_serial %= 2711
        assert previous_serial not in s
        s.add(previous_serial)

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

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

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

Блок-шифры обычно имеют фиксированный размер блока E.G. 64 или 128 бит. Но шифрование для консервирования формата позволяет принимать стандартные шифры AES и сделать шифр меньшего количества шифров, какого-либо радикса и ширины (например, Radix 10, ширина 9 для параметров вопроса), с алгоритмом, который все еще Криптографически надежный.

Гарантировано никогда не иметь столкновений (потому что криптографические алгоритмы создают отображение 1: 1). Это также обратимо (двустороннее отображение), поэтому вы можете взять полученный номер и вернуться к контрмурированному значение, с которого вы начали.

AES-FFX - это один предлагаемый стандартный метод для достижения этого.

Я экспериментировал с некоторым базовым кодом Python для AES-FFX - см. Код Python здесь (но обратите внимание, что он не полностью соответствует спецификации AES-FFX). Это может быть, например, Зашифруйте счетчик случайным 7-значным десятичным числом. E.G.

0000000   0731134
0000001   6161064
0000002   8899846
0000003   9575678
0000004   3030773
0000005   2748859
0000006   5127539
0000007   1372978
0000008   3830458
0000009   7628602
0000010   6643859
0000011   2563651
0000012   9522955
0000013   9286113
0000014   5543492
0000015   3230955
...       ...

Еще один пример в Python, используя другой метод не AES-FFX (я думаю), см. Этот пост блога «Как генерировать номер учетной записи» , который делает FPE с использованием фигенного шифра. Он генерирует числа от 0 до 2 ^ 32-1.

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

modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime

current = 433494437 # some start value
for i in xrange(1, 100):
    print current
    current = (current + incrementor) % modulo

Если вам не нужно что-то криптографически защищенное, а просто "достаточно затуманенное"...

Галуа-поля

Вы можете попробовать выполнить операции в Галуа-полях , например, GF(2)³², чтобы сопоставить простой инкрементирующий счетчик x с кажущимся случайным порядковым номером y:

x = counter_value
y = some_galois_function(x)

• Умножить на константу
  • Обратное равно умножению на противоположность константы
• Поднять на мощность : xⁿ
• Reciprocal x^-1
  • Special case of raise to power n
  • It is its own inverse
• Exponentiation of a primitive element: a^x
  • Обратите внимание, что это не имеет легко вычисляемого обратного (дискретного логарифма)
  • Убедитесь, что a является примитивным элементом , так же известным как генератор

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

Что касается поиска библиотеки для Галуа поле для Питона... хороший вопрос. Если Вам не нужна скорость (а для этого не нужна), то Вы можете сделать свой собственный. Я не пробовал:

• NZMATH
• Finite field Python package
• Sage, хотя это целая среда для математических вычислений, гораздо больше, чем просто библиотека Python

Умножение матриц в GF(2)

Выберите подходящую 32×32 инверсионную матрицу в GF(2), и умножьте на нее 32-битный счетчик входных данных. Это концептуально связано с LFSR, как описано в ответе С.Лотта S.Lott.

CRC

Связанная с этим возможность заключается в использовании CRC вычисления. Основано на остатке длинного деления с несводимым полиномом в GF(2). Питоновый код легко доступен для CRC (crcmod, pycrc), хотя для ваших целей может понадобиться другой несводимый многочлен, нежели обычно используемый. Я немного неясен в теории, но думаю, что 32-битная КСГ должна генерировать уникальное значение для каждой возможной комбинации 4-байтовых входов. Проверьте это. Довольно просто экспериментально проверить это, подавая выход обратно на вход и проверяя, что он производит полный цикл длиной 2³²-1 (ноль только сопоставляет ноль). Для работы этой проверки может понадобиться избавиться от любых исходных/окончательных XOR в алгоритме CRC.

Я пересматривал самому самой проблеме ... вы, кажется, не делаете ничего последовательного с числами ... и у вас есть индекс в столбце, который имеет их. На самом деле они нужны номера ?

Рассмотрим хэш SHA ... Тебе на самом деле не нужна вся вещь. Делайте то, что делают GIT или другие укорочения URL-адреса, и принимают первые 3/4/5 символов хеша. Учитывая, что каждый символ теперь имеет 36 возможных значений вместо 10, у вас есть 2176 782,336 комбинаций вместо 999999 комбинаций (для шести цифр). Комбинируйте это с быстрой проверкой на том, существует ли комбинация (запрос чистого индекса) и семя, такое, как временное помещение + случайное число, и он должен сделать практически для любой ситуации.

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

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

Довольно очевидно, что, после собрания 10 чисел, ваш пул возможных случайных чисел будет уменьшен на 10. Следовательно, вы не должны выбирать число от 1 до 1000 000 000, но от 1 до 999,990. Конечно, это число не является действительным числом, но только индекс (если только 10 чисел не составили 999,991, 999,992, ...); Вам придется рассчитывать сейчас от 1 пропуская всех чисел уже собранных.

Конечно, ваш алгоритм должен быть умнее, чем просто рассчитывать от 1 до 1000.000, но я надеюсь, что вы понимаете метод.

Мне не нравится рисовать случайные числа, пока я не получаю тот, который либо подходит. Это просто не так чувствует.

Я думаю, что вы переоцениваете проблемы с подходом 1). Если у вас нет требований в реальном времени, просто проверяя случайным выбором, заканчивается довольно быстро. Вероятность необходимости более чем ряд итераций распадается экспоненциально. При выходе на 100 метров выводится (10% счетчатка), у вас будет один миллиард шансов требовать более чем 9 итераций. Даже при 50% чисел, сделанных вы в среднем, нужны 2 итерации и имеют один за миллиард шансов требовать более 30 чек. Или даже крайний случай, когда уже приняты 99% чисел, все еще могут быть разумными - вы будете в среднем 100 итерациях и имеют 1 в миллиарде изменения, требующих 2062 итераций