Ответ 1

Основные улучшения, наборы и локальные имена

Использовать набор, а не список, а тестирование уникальности выполняется намного быстрее; установленное тестирование членства занимает постоянное время, не зависящее от заданного размера, тогда как списки принимают O (N) линейное время. Используйте множество понятий для создания серии ключей за раз, чтобы избежать необходимости поиска и вызова метода set.add() в цикле; правильно случайные, большие ключи имеют очень малую вероятность создания дубликатов в любом случае.

Поскольку это выполняется в узком цикле, вам стоит как можно больше оптимизировать все поисковые запросы:

import secrets
import numpy as np
from functools import partial

def produce_amount_keys(amount_of_keys, _randint=np.random.randint):
    keys = set()
    pickchar = partial(secrets.choice, string.ascii_uppercase + string.digits)
    while len(keys) < amount_of_keys:
        keys |= {''.join([pickchar() for _ in range(_randint(12, 20))]) for _ in range(amount_of_keys - len(keys))}
    return keys

Аргумент _randint привязывает имя np.random.randint к локальному в функции, которые быстрее ссылаются, чем глобальные, особенно когда задействуются запросы атрибутов.

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

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

Сроки для этого первого улучшения

Для 100 предметов разница не такая большая:

>>> timeit('p(100)', 'from __main__ import produce_amount_keys_list as p', number=1000)
8.720592894009314
>>> timeit('p(100)', 'from __main__ import produce_amount_keys_set as p', number=1000)
7.680242831003852

но когда вы начнете масштабировать это, вы заметите, что стоимость тестирования членства O (N) против списка действительно перетаскивает вашу версию вниз:

>>> timeit('p(10000)', 'from __main__ import produce_amount_keys_list as p', number=10)
15.46253142200294
>>> timeit('p(10000)', 'from __main__ import produce_amount_keys_set as p', number=10)
8.047800761007238

Моя версия уже почти в два раза быстрее, чем 10 тыс. элементов; 40k элементов можно запустить 10 раз за 32 секунды:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_list as p', number=10)
138.84072386901244
>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_set as p', number=10)
32.40720253501786

Версия списка заняла более 2 минут, более чем в десять раз.

Функция Numy random.choice, а не криптографически сильная

Вы можете сделать это быстрее, оставив модуль secrets и используя np.random.choice(); однако это не приведет к криптографическому уровню случайности, но выбор случайного символа в два раза быстрее:

def produce_amount_keys(amount_of_keys, _randint=np.random.randint):
    keys = set()
    pickchar = partial(
        np.random.choice,
        np.array(list(string.ascii_uppercase + string.digits)))
    while len(keys) < amount_of_keys:
        keys |= {''.join([pickchar() for _ in range(_randint(12, 20))]) for _ in range(amount_of_keys - len(keys))}
    return keys

Это имеет огромное значение, теперь 10 раз 40 КБ ключей могут быть созданы всего за 16 секунд:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_npchoice as p', number=10)
15.632006907981122

Дополнительные настройки с помощью модуля itertools и генератора

Мы также можем взять unique_everseen() функцию из раздела рецептов модуля itertools, чтобы он заботился о уникальности, затем используйте бесконечный генератор и itertools.islice() функция, чтобы ограничить результаты только желаемым числом:

# additional imports
from itertools import islice, repeat

# assumption: unique_everseen defined or imported

def produce_amount_keys(amount_of_keys):
    pickchar = partial(
        np.random.choice,
        np.array(list(string.ascii_uppercase + string.digits)))
    def gen_keys(_range=range, _randint=np.random.randint):
        while True:
            yield ''.join([pickchar() for _ in _range(_randint(12, 20))])
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

Это немного быстрее, но только незначительно:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_itertools as p', number=10)
14.698191125993617

os.urandom() и другой способ создания строк

Далее мы можем перейти к идеям Адама Барнса для использования UUID4 (который в основном представляет собой обертку os.urandom()) и Base64. Но в случае сложения Base64 и замены 2 символов случайно подобранными, его метод сильно ограничивает энтропию в этих строках (вы не будете создавать полный диапазон уникальных значений, 20-символьная строка, используя только (256 ** 15) / (36 ** 20) == 1 в каждом 99437 бит энтропии!).

В кодировке Base64 используются символы верхнего и нижнего регистра и цифры, но также добавляются символы - и / (или + и _ для безопасного для URL варианта). Для только заглавных букв и цифр вам нужно загладить вывод и сопоставить эти лишние два символа с другими случайными символами, процесс, который выбрасывает большую часть энтропии из случайных данных, предоставленных os.urandom(). Вместо использования Base64 вы также можете использовать кодировку Base32, которая использует заглавные буквы и цифры с 2 по 8, поэтому создает строки с 32 ** n возможностями по сравнению с 36 ** n. Тем не менее, это может ускорить работу от вышеуказанных попыток:

import os
import base64
import math

def produce_amount_keys(amount_of_keys):
    def gen_keys(_urandom=os.urandom, _encode=base64.b32encode, _randint=np.random.randint, _factor=math.log(256, 32)):
        while True:
            count = _randint(12, 20)
            # count + 1 / _factor gives us the number of bytes needed 
            # to produce *at least* count encoded characters
            yield _encode(_urandom(int((count + 1) / _factor)))[:count].decode('ascii')
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

Это действительно быстро:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_b32 as p', number=10)
4.266283575998386

40k ключей, 10 раз, всего за 4 секунды. Так примерно в 75 раз быстрее; скорость использования os.urandom() в качестве источника неоспорима.

Это криптографически сильное снова; os.urandom() создает байты для криптографического использования. С другой стороны, мы уменьшили количество возможных строк, созданных более чем на 90% (((36 ** 20) - (32 ** 20)) / (36 ** 20) * 100 - 90,5), мы больше не используем цифры 0, 1, 8 и 9 в выходов.

Итак, мы должны использовать трюк urandom() для создания правильной кодировки Base36; мы должны будем создать собственную функцию b36encode():

import string
import math

def b36encode(b, _range=range, _c=(string.ascii_uppercase + string.digits).encode()):
    """Encode a bytes value to Base36 (uppercase ASCII and digits)

    This isn't too friendly on memory because we convert the whole bytes
    object to an int, but for smaller inputs this should be fine.
    """
    b_int = int.from_bytes(b, 'big')
    length = len(b) and int(math.log(256 ** len(b), 36))
    count = b_int and int(math.log(b_int, 36))
    return bytes(_c[(b_int // 36 ** i) % 36] for i in _range(count, -1, -1)).rjust(length, b'A')

и используйте это:

def produce_amount_keys(amount_of_keys):
    def gen_keys(_urandom=os.urandom, _encode=b36encode, _randint=np.random.randint, _factor=math.log(256, 36)):
        while True:
            count = _randint(12, 20)
            # count + 1 / _factor gives us the number of bytes needed 
            # to produce *at least* count encoded characters
            yield _encode(_urandom(int((count + 1) / _factor)))[:count].decode('ascii')
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

Это все еще достаточно быстро, и, прежде всего, производит полный диапазон из 36 заглавных букв и цифр:

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_b36 as p', number=10)
7.3695860790030565

Конечно, версия base32 почти в два раза быстрее, чем эта (благодаря эффективной реализации Python с использованием таблицы), но использование настраиваемого кодировщика Base36 по-прежнему вдвое превышает скорость не криптографически безопасной версии numpy.random.choice()! В моей книге это хороший результат.

Обратите внимание, что версия Base64 работает быстрее, но я лично не верю, что она выбрасывает так много случайности из источника os.urandom().

Ответ 2

Итак, это гонка скорости?

Основываясь на работе Martijn Pieters, у меня есть решение, которое умно использует другую библиотеку для генерации случайных строк: uuid.

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

Это работает для этого случая, потому что длина выходных данных, которые мы получаем после (12-20), короче, чем кратчайшая кодировка u64 для base64. Это также очень быстро, потому что uuid очень быстро.

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

Интересно, что с использованием стандартной библиотеки randint функция была быстрее, чем numpy.

Вот тестовый вывод:

Timing 40k keys 10 times with produce_amount_keys
20.899942063027993
Timing 40k keys 10 times with produce_amount_keys, stdlib randint
20.85920040300698
Timing 40k keys 10 times with uuidgen
3.852462349983398
Timing 40k keys 10 times with uuidgen, stdlib randint
3.136272903997451

Вот код для uuidgen():

def uuidgen(count, _randint=np.random.randint):
    generated = set()

    while True:
        if len(generated) == count:
            return

        candidate = b64encode(uuid4().hex.encode()).upper()[:_randint(12, 20)]
        if candidate not in generated:
            generated.add(candidate)
            yield candidate

И здесь - это весь проект. (При фиксации d9925d на момент написания).

EDIT: благодаря отзывам Martijn Pieters, я несколько улучшил этот метод, увеличив энтропию и ускоряя ее примерно на 1/6.

До сих пор остается много энтропии, потерянной в литье всех строчных букв в верхний регистр. Если это важно, то, возможно, целесообразно использовать b32encode() вместо этого, у которого есть нужные символы, минус 0, 1, 8 и 9.

Новое решение выглядит следующим образом:

def urandomgen(count):
    generated = set()

    while True:
        if len(generated) == count:
            return

        desired_length = randint(12, 20)

        # # Faster than math.ceil
        # urandom_bytes = urandom(((desired_length + 1) * 3) // 4)
        #
        # candidate = b64encode(urandom_bytes, b'//').upper()
        #
        # The above is rolled into one line to cut down on execution
        # time stemming from locals() dictionary access.

        candidate = b64encode(
            urandom(((desired_length + 1) * 3) // 4),
            b'//',
        ).upper()[:desired_length]

        while b'/' in candidate:
            candidate = candidate.replace(b'/', choice(ALLOWED_CHARS), 1)

        if candidate not in generated:
            generated.add(candidate)
            yield candidate.decode()

И тестовый выход:

Timing 40k keys 10 times with produce_amount_keys, stdlib randint
19.64966493297834
Timing 40k keys 10 times with uuidgen, stdlib randint
4.063803717988776
Timing 40k keys 10 times with urandomgen, stdlib randint
2.4056471119984053

Новый коммит в моем репозитории 5625fd.

EDIT: комментарии Martijn по энтропии заставили меня задуматься. Метод, который я использовал с base64 и .upper(), делает буквы SO намного более распространенными, чем числа. Я снова рассмотрел проблему с более двоичным разумом.

Идея заключалась в том, чтобы вывести результат из os.urandom(), интерпретировать его как длинную строку из 6-битных неподписанных чисел и использовать эти числа в качестве индекса для скользящего массива разрешенных символов. Первое 6-битное число выбрало бы символ из диапазона A..Z0..9A..Z01, второе 6-битное число выбрало бы символ из диапазона 2..9A..Z0..9A..T и т.д.

Это небольшое дробиние энтропии в том, что первый символ будет немного менее вероятен содержать 2..9, второй символ с меньшей вероятностью будет содержать U..Z0 и т.д., но он намного лучше, чем раньше.

Он немного быстрее, чем uuidgen(), и немного медленнее, чем urandomgen(), как показано ниже:

Timing 40k keys 10 times with produce_amount_keys, stdlib randint
20.440480664998177
Timing 40k keys 10 times with uuidgen, stdlib randint
3.430628580001212
Timing 40k keys 10 times with urandomgen, stdlib randint
2.0875444510020316
Timing 40k keys 10 times with bytegen, stdlib randint
2.8740892770001665

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

Новый код выглядит следующим образом:

from os import urandom
from random import randint
from string import ascii_uppercase, digits

# Masks for extracting the numbers we want from the maximum possible
# length of `urandom_bytes`.
bitmasks = [(0b111111 << (i * 6), i) for i in range(20)]
allowed_chars = (ascii_uppercase + digits) * 16  # 576 chars long


def bytegen(count):
    generated = set()

    while True:
        if len(generated) == count:
            return

        # Generate 9 characters from 9x6 bits
        desired_length = randint(12, 20)
        bytes_needed = (((desired_length * 6) - 1) // 8) + 1

        # Endianness doesn't matter.
        urandom_bytes = int.from_bytes(urandom(bytes_needed), 'big')

        chars = [
            allowed_chars[
                (((urandom_bytes & bitmask) >> (i * 6)) + (0b111111 * i)) % 576
            ]
            for bitmask, i in bitmasks
        ][:desired_length]

        candidate = ''.join(chars)

        if candidate not in generated:
            generated.add(candidate)
            yield candidate

И полный код вместе с более углубленным README для реализации завершен в de0db8.

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

Ответ 3

Предостережение: это не криптографически безопасно. Я хочу дать альтернативный подход numpy к тому, который был в ответе Martijn.

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

• Мы знаем, что все ваши длины строк находятся между 12 и 20. Просто сгенерируйте все длины строк за один раз. Мы знаем, что окончательный set имеет возможность обрезать окончательный список строк, поэтому мы должны ожидать этого и делать больше "длины строк", чем нам нужно. 20 000 лишних излишков, но для того, чтобы сделать точку:

  string_lengths = np.random.randint(12, 20, 60000)

• Вместо того, чтобы создавать все наши последовательности в цикле for, создайте 1D-список символов, который достаточно длинный, чтобы быть разрезанным на 40 000 списков. В сценарии абсолютного наихудшего случая все длины случайных строк в (1) были максимальной длиной 20. Это означает, что нам нужно 800 000 символов.

  pool = list(string.ascii_letters + string.digits)

  random_letters = np.random.choice(pool, size=800000)

• Теперь нам просто нужно разбить этот список случайных символов. Используя np.cumsum(), мы можем получить порядковые начальные индексы для подписок, а np.roll() будет смещать этот массив индексов на 1, чтобы получить соответствующий массив конечных индексов.
  

  starts = string_lengths.cumsum()

  ends = np.roll(string_lengths.cumsum(), -1)

• Вырезать список случайных символов по индексам.
  

  final = [''.join(random_letters[starts[x]:ends[x]]) for x, _ in enumerate(starts)]

Объединяя все это:

def numpy_approach():
    pool = list(string.ascii_letters + string.digits)
    string_lengths = np.random.randint(12, 20, 60000)   
    ends = np.roll(string_lengths.cumsum(), -1) 
    starts = string_lengths.cumsum()
    random_letters = np.random.choice(pool, size=800000)
    final = [''.join(random_letters[starts[x]:ends[x]]) for x, _ in enumerate(starts)]
    return final

И timeit результаты:

322 ms ± 7.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Ответ 4

Альтернативный подход: уникальность в создании, а не при тестировании

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

• Генерировать вывод, который выглядит как можно более случайным
• Генерировать вывод, который гарантированно будет уникальным, и выглядит несколько случайным.
• Объединить их

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

Пример

Предположим, вы хотите сгенерировать строки 999999 с длиной от 12 до 20. Подход, конечно, будет работать для всех наборов символов, но позволяет сохранить его простым и предположить, что вы хотите использовать только 0-9.

• Генерировать случайный вывод с длиной от 6 до 14
• Случайно переставляйте числа от 000000 до 999999 (да, 6 цифр довольно много "жертвуют" в кажущейся случайности, но с большим набором символов вам не понадобится это много символов)
• Теперь объедините их так, чтобы уникальность была сохранена. Самый тривиальный способ - простая конкатенация сущностей, но вы, конечно, можете думать о менее очевидных решениях.

Малый пример

• Создать случайность:

  sdfdsf xxer ver

• Создать уникальность

  XD ае шд

• Объединить

  xdsdfdsf aexxer bdver

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