用Python 3生成具有随机长度的类似随机字符串的最快方法

Question

我知道如何创建随机字符串，例如：

''.join(secrets.choice(string.ascii_uppercase + string.digits) for _ in range(N))

但是，不应有重复项，因此我目前仅检查密钥是否已存在于列表中，如以下代码所示：

import secrets
import string
import numpy as np


amount_of_keys = 40000

keys = []

for i in range(0,amount_of_keys):
    N = np.random.randint(12,20)
    n_key = ''.join(secrets.choice(string.ascii_uppercase + string.digits) for _ in range(N))
    if not n_key in keys:
        keys.append(n_key)

对于少量的键（例如）也可以40000，但是，如果键越多，该问题就无法很好地解决。所以我想知道是否有更快的方法来获得更多键的结果，例如999999

Answer 1

基本改进，集合和本地名称

使用 set
而不是list，唯一性测试要快得多；集合成员资格测试花费与集合大小无关的恒定时间，而列表花费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

我的版本几乎已经快了1万倍。40k项可以在32秒内运行10次：

>>> 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分钟多的时间，是原来的十倍多。

Numpy的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

这产生了巨大的变化，现在仅16秒就可以产生10倍的40k密钥：

>>> 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（）字节和产生字符串的另一种方法

接下来，我们可以继续使用亚当·巴恩斯（AdamBarnes）关于使用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):
        # (count / math.log(256, 32)), rounded up, gives us the number of bytes
        # needed to produce *at least* count encoded characters
        factor = math.log(256, 32)
        input_length = [None] * 12 + [math.ceil(l / factor) for l in range(12, 20)]
        while True:
            count = _randint(12, 20)
            yield _encode(_urandom(input_length[count]))[: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.572628145979252

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, _ceil=math.ceil, _log=math.log, _fb=int.from_bytes, _len=len, _b=bytes,
        _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 = _fb(b, 'big')
    length = _len(b) and _ceil(_log((256 ** _len(b)) - 1, 36))
    return _b(_c[(b_int // 36 ** i) % 36] for i in _range(length - 1, -1, -1))

并使用：

def produce_amount_keys(amount_of_keys):
    def gen_keys(_urandom=os.urandom, _encode=b36encode, _randint=np.random.randint):
        # (count / math.log(256, 36)), rounded up, gives us the number of bytes
        # needed to produce *at least* count encoded characters
        factor = math.log(256, 36)
        input_length = [None] * 12 + [math.ceil(l / factor) for l in range(12, 20)]
        while True:
            count = _randint(12, 20)
            yield _encode(_urandom(input_length[count]))[-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)
8.099918447987875

诚然，base32版本几乎是该版本的两倍（由于使用表实现了高效的Python实现），但是使用自定义Base36编码器仍然是非加密安全numpy.random.choice()版本速度的两倍。

但是，使用os.urandom() 会 再次 产生偏差
。我们必须产生比12到19个base36“数字”所需的更多的熵。例如，对于17位数字，我们不能使用字节产生36
17个不同的值，只能产生最接近的等值256
11个字节，这大约是太高的1.08倍，因此我们最终会产生偏差朝A，B和较小的方向发展C（感谢Stefan
Pochmann指出这一点）。

在下面选择一个整数(36 ** length)并将其映射到base36

因此，我们需要寻求一种安全的随机方法，该方法可以使我们在0（包含）和36 ** (desired length)（包含）之间平均分配值。然后，我们可以将数字直接映射到所需的字符串。

首先，将整数映射到字符串；已对以下内容进行了调整，以最快的速度生成输出字符串：

def b36number(n, length, _range=range, _c=string.ascii_uppercase + string.digits):
    """Convert an integer to Base36 (uppercase ASCII and digits)"""
    chars = [_c[0]] * length
    while n:
        length -= 1
        chars[length] = _c[n % 36]
        n //= 36
    return ''.join(chars)

接下来，我们需要一种快速且 密码安全的
方法来选择一个范围内的数字。您仍然可以使用os.urandom()它，但是您必须将字节屏蔽为最大位数，然后循环直到您的实际值低于限制。这实际上已经通过secrets.randbelow()函数实现了。在Python版本<3.6中，可以使用random.SystemRandom().randrange()，它使用完全相同的方法并进行一些额外的包装以支持大于0的下限和步长。

使用secrets.randbelow()该函数将变为：

import secrets

def produce_amount_keys(amount_of_keys):
    def gen_keys(_below=secrets.randbelow, _encode=b36number, _randint=np.random.randint):
        limit = [None] * 12 + [36 ** l for l in range(12, 20)]
        while True:
            count = _randint(12, 20)
            yield _encode(_below(limit[count]), count)
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

然后，这与（可能有偏差的）base64解决方案非常接近：

>>> timeit('p(40000)', 'from __main__ import produce_amount_keys_below as p', number=10)
5.135716405988205

这几乎与Base32方法一样快，但是会产生所有密钥！