在 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

原文由 Kev1n91 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 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

我的版本速度几乎是 10k 项目的两倍； 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 模块和生成器

我们还可以从 itertools 模块 Recipes 部分获取 unique_everseen() 函数 让它处理唯一性，然后使用无限生成器和 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() 字节和生成字符串的不同方法

接下来，我们可以继续 Adam Barnes 关于使用 UUID4（基本上只是 os.urandom() 的包装器）和 Base64 的想法。但是通过大小写折叠 Base64 并用随机选择的字符替换 2 个字符，他的方法严重限制了这些字符串中的熵（你不会产生可能的唯一值的全部范围，一个 20 个字符的字符串只使用 (256 ** 15) / (36 ** 20) == 每 99437 位熵中有 1 个！）。

The Base64 encoding uses both upper and lower case characters and digits but also adds the - and / characters (or + and _ for 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 指出这个 outchmann）。

在下面选择一个整数 (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 方法一样快，但会生成全范围的密钥！

原文由 Martijn Pieters 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

所以这是一场速度竞赛，是吗？

基于 Martijn Pieters 的工作，我得到了一个巧妙地利用另一个库生成随机字符串的解决方案： uuid 。

我的解决方案是生成一个 uuid4 ，对其进行 base64 编码并大写，以仅获取我们之后的字符，然后将其切成随机长度。

这适用于这种情况，因为我们之后的输出长度 (12-20) 比 uuid4 的最短 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 ）。

---

感谢 Martijn Pieters 的反馈，我对方法进行了一些改进，增加了熵，并将速度提高了大约 ¹⁄₆ 倍。

将所有小写字母转换为大写字母仍然会损失很多熵。 If that’s important, then it’s possibly advisable to use b32encode() instead, which has the characters we want, minus 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 。

---

Martijn 对熵的评论让我开始思考。我与 base64 和 .upper() 一起使用的方法使字母比数字更常见。我以更加二元的思维重新审视了这个问题。

这个想法是从 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

完整的代码，以及关于实现的更深入的自述文件，在 de0db8 结束。

我尝试了几件事来加快实施速度，如回购协议中所示。肯定有帮助的是字符编码，其中数字和 ASCII 大写字母是连续的。

原文由 Adam Barnes 发布，翻译遵循 CC BY-SA 3.0 许可协议