Ответ 1

Проблема в основном порождает случайную перестановку целых чисел в диапазоне 0..n-1.

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

Примеры операций, которые мы можем выполнять на каждом числе x в диапазоне, включают:

• Дополнение: Мы можем добавить любое целое число c в x.
• Умножение. Мы можем умножить x на любое число m которое не имеет простых коэффициентов с n.

Применение только этих двух операций в диапазоне 0..n-1 уже дает вполне удовлетворительные результаты:

>>> n = 7
>>> c = 1
>>> m = 3
>>> [((x+c) * m) % n for x in range(n)]
[3, 6, 2, 5, 1, 4, 0]

Выглядит случайно, не так ли?

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

Реализация

Трудная часть реализации - это просто генерация подходящего случайного m. Для этого я использовал код основной факторизации из этого ответа.

import random

# credit for prime factorization code goes
# to /questions/249114/prime-factorization-list/1283685#1283685
def prime_factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, next_ = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[next_]
        next_ += 1
        if next_ == length:
            next_ = cycle
    if n > 1: fs.append(n)
    return fs

def generate_c_and_m(n, seed=None):
    # we need to know n prime factors to find a suitable multiplier m
    p_factors = set(prime_factors(n))

    def is_valid_multiplier(m):
        # m must not share any prime factors with n
        factors = prime_factors(m)
        return not p_factors.intersection(factors)

    # if no seed was given, generate random values for c and m
    if seed is None:
        c = random.randint(n)
        m = random.randint(1, 2*n)
    else:
        c = seed
        m = seed

    # make sure m is valid
    while not is_valid_multiplier(m):
        m += 1

    return c, m

Теперь, когда мы можем генерировать подходящие значения для c и m, создание перестановки тривиально:

def random_range(n, seed=None):
    c, m = generate_c_and_m(n, seed)

    for x in range(n):
        yield ((x + c) * m) % n

И ваша функция генератора может быть реализована как

def MyGenerator(foo, num):
    for x in random_range(num):
        if foo(x):
            yield x

Ответ 2

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

вы могли бы смешивать ваши shuffle и set решения с порогом на значение num. Это в основном сборка ваших первых первых решений в одном генераторе:

from random import shuffle,randint

def MyGenerator(foo, num):
    if num < 100000 # has to be adjusted by experiments
      order = list(range(num))
      shuffle(order)
      for i in order:
          if foo(i):
              yield i
    else:   # big values, few collisions with random generator 
      tried = set()
      while len(tried) < num:
        i = randint(0, num-1)
        if i in tried:
           continue
        tried.add(i)
        if foo(i):
           yield i

Решение randint (для больших значений num) хорошо работает, потому что в случайном генераторе не так много повторов.

Ответ 3

Получение максимальной производительности в Python намного сложнее, чем на языках более низкого уровня. Например, в C вы часто можете немного сэкономить в горячих внутренних циклах, заменив умножение на сдвиг. Накладные расходы на ориентацию байт-кода python стирают это. Конечно, это снова меняется, когда вы рассматриваете, какой вариант "python" вы нацеливаете (pypy? Numpy? Cython?) - вам действительно нужно написать свой код, на основе которого вы используете.

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

Один из самых простых способов получить немного по сравнению с существующими ответами будет путем генерации чисел в кусках с использованием numpy.arange() и непосредственного применения ((x + c) * m) % n к numpy ndarray. Любой цикл на уровне питона, который можно избежать, помогает.

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

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

Xoroshiro128+ является вторым по качеству и быстрее, но менее информативным для изучения.

Python (и многие другие) по умолчанию выбирает Mersenne Twister.

(там также что-то называется splitmix64, которого я не знаю достаточно, чтобы разместить его - некоторые говорят это лучше, чем Xoroshiro128+, но у него есть проблема периода - конечно, вы можете этого захотеть здесь)

Оба по умолчанию - PCG и Xoroshiro128+ используют состояние 2N бит для генерации N-разрядных чисел. Это обычно желательно, но означает, что числа будут повторяться. Тем не менее, у PCG есть альтернативные режимы, которые избегают этого.

Конечно, многое из этого зависит от того, является ли num (близким) к мощности 2. Теоретически варианты PCG могут быть созданы для любой ширины бита, но в настоящее время реализованы только различные размеры слов, так как вам нужна явная маскировка. Я точно не знаю, как создавать параметры для новых размеров бит (возможно, это в документе?), Но их можно протестировать просто, выполнив переход периода /2 и проверив, что значение отличается.

Конечно, если вы только делаете 200 звонков в RNG, вам, вероятно, на самом деле не нужно избегать дубликатов на математической стороне.

Кроме того, вы можете использовать LFSR, который существует для каждого размера бита (хотя обратите внимание, что он никогда не генерирует значение all-zeros (или, что то же самое, значение all-ones)). LFSRs являются серийными и (AFAIK) не пересказуемыми, и поэтому их нельзя легко разделить на несколько задач. Редактирование: я понял, что это неверно, просто представляем шаг вперед как матрицу и выражаем его, чтобы прыгать.

Обратите внимание, что LFSR имеют одинаковые явные пристрастия, как просто генерирование чисел в последовательном порядке на основе случайной начальной точки - например, если rng_outputs [a: b] все не работают с вашей функцией foo, тогда rng_outputs[b] будет гораздо более вероятным первый выход независимо от начальной точки. Параметр "поток" PCG позволяет избежать этого, не генерируя числа в том же порядке.

Edit2: Я завершил то, что, как я думал, был "кратким проектом", реализующим LFSR в python, включая прыжки, полностью протестирован.