在Python 3中生成随机长度的类似随机字符串的唯一字符串的最快方法是什么?

31

我知道如何创建随机字符串,例如:

''.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


你使用numpy生成随机数的特别原因是什么,而不是使用Python标准库中的“random”模块? - ash
不,随机算法更快吗? - Kev1n91
7
请注意,实际上您并没有生成40,000个密钥。因为如果存在重复,您不会生成更多的密钥,所以您生成的密钥数量其实是少于 40,000个的。 - Martijn Pieters
1
@MartijnPieters 嗯...以至少99.999999997829302352%的概率,他们确实会生成40k个密钥:https://eval.in/951632 - Stefan Pochmann
定义好随机数...你想要多随机? - Christophe Roussy
6个回答

55

基本改进、集合和局部名称

使用集合,而不是列表,测试唯一性更快;集合成员测试独立于集合大小,需要常量时间,而列表需要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
< p > _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,000个项目快了近两倍;40,000个项目可以在大约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!)。

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

在仅仅4秒多的时间内,生成了40k个密钥,比使用os.urandom()作为源要快约75倍。这种速度是不可否认的。

加密强度也很高;os.urandom()生成用于加密的字节。另一方面,我们减少了可能产生的字符串数量超过90%(((36 ** 20) - (32 ** 20)) / (36 ** 20) * 100 是90.5),不再使用输出中的0189数字。

因此,也许我们应该使用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

虽然基于32位的版本比这个版本快近一倍(由于使用了高效的Python实现),但是使用自定义的Base36编码器仍然比不安全的numpy.random.choice()版本快两倍。

然而,使用os.urandom()再次产生偏差;我们必须产生比需要的12到19个Base36“数字”所需的熵更多的位数。例如,对于17个数字,我们不能使用字节产生36 ** 17个不同的值,只能使用最接近的256 ** 11个字节的相当值,大约是太高的1.08倍,因此我们最终会偏向于AB,在较小程度上偏向于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方法一样快,但可以生成完整范围的密钥!


1
@Michael:这样会使连接变慢,所以我明确地不这样做。 - Martijn Pieters
2
@Michael:请查看Python中不使用[ ]的列表推导式 - Martijn Pieters
仔细研究了base64(或者更确切地说是base32)的解决方案以及b32encode的工作原理。我认为它没有偏差。你想要32的幂,就至少要创建一个256的幂。这样你就得到了一个精确的倍数,只是多创建了一些额外的位。而且b32encode的工作方式以及从其结果中提取的方法,我认为你只能提取随机部分,而不是填充部分。 - Stefan Pochmann
是的,当然,但那很明显,所以你说的“可能有偏差”不是指那个,对吧?我是指除了那个明显的键空间缩减外,我认为它没有偏差。 - Stefan Pochmann
1
@CesareIurlaro 是的,我在回答中的代码会生成长度随机的字符串,每个字符串的最小长度为12个字符,最大长度为20个字符。 - Martijn Pieters
显示剩余8条评论

8

所以这是一场速度比赛吗?

在 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的反馈,我对这个方法进行了改进,增加了熵并将其加速了约六分之一。

将所有小写字母转换为大写字母仍然会导致很多熵损失。 如果这很重要,则可能建议改用b32encode(),其中包含我们需要的字符,不包括0189

新的解决方案如下:

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大写字母成为连续的。


为什么将十六进制字符串进行b64编码?这会严重降低熵值,输出结果的字节只有16个不同的值。这极大地减少了你所能生成的密钥范围。至少,应将二进制数据编码为base 64。另外,base 64使用了一组不同的字符(不仅是字母和数字,还有+/),这也非常重要,你可能想将它们映射到有效的密钥字符。 - Martijn Pieters
1
Base32 缺少 01,不仅仅是 89 - Martijn Pieters
为了进行公正的比较,请将字节对象解码为字符串。 - Martijn Pieters
我还将字节解码为字符串,详见implementations/urandomgen.py#L38。同样的操作也出现在uuidgen.py中。 - Adam Barnes
我仍然担心对Base64编码进行大小写折叠会降低熵。您将64个值压缩为38个,并用36个范围内的随机值替换了2个可能的值。因此,3个字节的随机数据编码(256 ** 3 ==)16777216种可能的值被减少到(4个字节的Base64,缩小到4个字节的base36,== 36 ** 4 ==)1679616个字符串,因此将熵降低了近10倍! 对于20个字符的输出,您的15个字节的os.urandom()数据范围会减少99437倍。 真是太伤人了! - Martijn Pieters
显示剩余10条评论

5
一个简单快速的方法:
def b36(n, N, chars=string.ascii_uppercase + string.digits):
    s = ''
    for _ in range(N):
        s += chars[n % 36]
        n //= 36
    return s

def produce_amount_keys(amount_of_keys):
    keys = set()
    while len(keys) < amount_of_keys:
        N = np.random.randint(12, 20)
        keys.add(b36(secrets.randbelow(36**N), N))
    return keys

-- 编辑:以下内容是对Martijn之前回答的修订版本。在我们的讨论后,他添加了另一种解决方案,本质上与我的解决方案相同,但进行了一些优化。但它们并没有多大帮助,只比我在测试中快约3.4%,所以我认为它们基本上只会使事情更加复杂。--

与Martijn在他被接受的答案中的最终解决方案相比,我的方案要简单得多,快约1.7倍,并且不偏向任何一方:

Stefan
8.246490597876106 seconds.
8 different lengths from 12 to 19
  Least common length 19 appeared 124357 times.
  Most common length 16 appeared 125424 times.
36 different characters from 0 to Z
  Least common character Q appeared 429324 times.
  Most common character Y appeared 431433 times.
36 different first characters from 0 to Z
  Least common first character C appeared 27381 times.
  Most common first character Q appeared 28139 times.
36 different last characters from 0 to Z
  Least common last character Q appeared 27301 times.
  Most common last character E appeared 28109 times.

Martijn
14.253227412021943 seconds.
8 different lengths from 12 to 19
  Least common length 13 appeared 124753 times.
  Most common length 15 appeared 125339 times.
36 different characters from 0 to Z
  Least common character 9 appeared 428176 times.
  Most common character C appeared 434029 times.
36 different first characters from 0 to Z
  Least common first character 8 appeared 25774 times.
  Most common first character A appeared 31620 times.
36 different last characters from 0 to Z
  Least common last character Y appeared 27440 times.
  Most common last character X appeared 28168 times.

马丁的文本存在偏差,第一个字符中出现了太多的A,而8则出现得太少。我运行了十次测试,他最常见的首字母总是A或B(分别出现了五次),而他最不常见的字符总是7、8或9(分别出现了两次、三次和五次)。我还单独检查了长度,长度为17的情况尤其糟糕,他最常见的首字母总共出现了约51500次,而他最不常见的首字母只出现了约25400次。
有趣的一面:我正在使用马丁拒绝的"secrets"模块 :-)
我的整个脚本:
import string
import secrets
import numpy as np
import os
from itertools import islice, filterfalse
import math

#------------------------------------------------------------------------------------
#   Stefan
#------------------------------------------------------------------------------------

def b36(n, N, chars=string.ascii_uppercase + string.digits):
    s = ''
    for _ in range(N):
        s += chars[n % 36]
        n //= 36
    return s

def produce_amount_keys_stefan(amount_of_keys):
    keys = set()
    while len(keys) < amount_of_keys:
        N = np.random.randint(12, 20)
        keys.add(b36(secrets.randbelow(36**N), N))
    return keys

#------------------------------------------------------------------------------------
#   Martijn
#------------------------------------------------------------------------------------

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()):
    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_martijn(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)
            yield _encode(_urandom(math.ceil(count / _factor)))[-count:].decode('ascii')
    return list(islice(unique_everseen(gen_keys()), amount_of_keys))

#------------------------------------------------------------------------------------
#   Needed for Martijn
#------------------------------------------------------------------------------------

def unique_everseen(iterable, key=None):
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

#------------------------------------------------------------------------------------
#   Benchmark and quality check
#------------------------------------------------------------------------------------

from timeit import timeit
from collections import Counter

def check(name, func):
    print()
    print(name)

    # Get 999999 keys and report the time.
    keys = None
    def getkeys():
        nonlocal keys
        keys = func(999999)
    t = timeit(getkeys, number=1)
    print(t, 'seconds.')

    # Report statistics about lengths and characters
    def statistics(label, values):
        ctr = Counter(values)
        least = min(ctr, key=ctr.get)
        most = max(ctr, key=ctr.get)
        print(len(ctr), f'different {label}s from', min(ctr), 'to', max(ctr))
        print(f'  Least common {label}', least, 'appeared', ctr[least], 'times.')
        print(f'  Most common {label}', most, 'appeared', ctr[most], 'times.')
    statistics('length', map(len, keys))
    statistics('character', ''.join(keys))
    statistics('first character', (k[0] for k in keys))
    statistics('last character', (k[-1] for k in keys))

for _ in range(2):
    check('Stefan', produce_amount_keys_stefan)
    check('Martijn', produce_amount_keys_martijn)

不错!你的代码再次变得更快了,因为它省略了int -> bytes和bytes -> int的转换。 - Martijn Pieters
请注意,您的“b36”数字实际上是反向的。虽然这在这里并不重要。但在我的情况下,它似乎是偏差的原因,因为我生成的整数值大于“36 **(所需长度)”,这会添加更多我再次丢弃的信息。这在长度为17时尤为明显,因为“17 / math.log(256,36)”几乎等于11,但并非完全相等。剩余的0.0139字节分数比其他值中的较大边距创建了更大的偏差。所有这些都是因为base36不能干净地划分2的幂。看起来我只能通过使用“randbelow()”来避免偏差! - Martijn Pieters
@MartijnPieters 是的,这就是为什么我将它从 base36 重命名为 b36 的原因。使用“base”这个词感觉不对,因为它听起来像是数学基数表示法。但只用“b”,我觉得可以,没有那么多负面含义。如果有的话,“b36”听起来像是编程中的编码方式,它们不会取一个任意大的数字,而是 字节,然后我认为我所做的类似于使用小端编码对数字进行编码。是的,randbelow 可能是避免偏差的最佳选择。或者在您的方法中,您也可以丢弃太大的字节,但这似乎很复杂。 - Stefan Pochmann

1

注意:这不是加密安全的。我想提供一个numpy的替代方案,来补充Martijn的好答案。

numpy函数并不是为了在小任务的循环中重复调用而进行优化的;相反,最好将每个操作批量执行。这种方法给出了比你需要的更多的密钥(在这种情况下非常大,因为我夸大了对过估计的需求),因此内存利用率较低,但仍然超级快。

我们知道所有字符串的长度都在12到20之间。一次性生成所有字符串长度。我们知道最终的set可能会修剪掉最终的字符串列表,因此我们应该预见到这一点,并生成比我们需要的更多的“字符串长度”。虽然20000个额外的长度有些过多,但这是为了说明问题:

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

不要使用for循环创建所有序列,而是创建一个足够长的1D字符列表,可被切成40000个列表。在最坏的情况下,(1)中的所有随机字符串长度均为最大长度20。这意味着我们需要800000个字符。

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)

1
@AdamBarnes 当然可以,但我需要几个小时才能到那台电脑。完成后会通知您更新。 - roganjosh
非常感谢。 - Adam Barnes
@AdamBarnes 在尝试设置测试用例的过程中,我认为你的输出可能存在问题。我测量了所有输出字符串的长度:len_dict = {12: 4451, 13: 4352, 14: 4492, 15: 26705}。然而,对于我来说,创建和耗尽生成器所需的时间相差不大(262毫秒±2.41毫秒)- 你的速度更快。 - roganjosh
@AdamBarnes 尽管如此,事实证明 string_lengths = np.random.randint(12, 20, 60000) 需要相对较长的时间。string_lengths = np.random.randint(12, 20, 42000) 更为合理,将我的计时降至 196 ms ± 1.72 ms per loop,因此很难给出确切的比较,因为我的方法并不是精确科学,总会有一些高估的情况。 - roganjosh
1
那最终变得非常简单;我只生成了长度为15个字符的位掩码。多傻啊。 - Adam Barnes
显示剩余2条评论

0

简单地说

如果您使用的是Python > 3.6版本

d = 100(您想要的任何长度)

或者,如果您想要一个随机范围

d = random.randrange(start=start_range,stop=stop_range)

import string
import random
random_str = ''.join(random.choices(string.ascii_uppercase +
                         string.digits, k = d))

如果您需要更安全的方式
random_str = ''.join(secrets.choice(string.ascii_uppercase + string.digits)
                                              for i in range(d))

0

另一种方法:通过创建独特性而非测试实现

对于您的问题,显然的方法是生成随机输出,然后检查其是否唯一。虽然我没有提供实现,但这里有一种替代方法:

  1. 生成看起来尽可能随机的输出
  2. 生成保证唯一且看起来有些随机的输出
  3. 将它们组合在一起

现在你有了保证唯一且看起来随机的输出。

示例

假设您想要生成长度为12到20的999999个字符串。当然,该方法适用于所有字符集,但让我们保持简单,假设您只想使用0-9。

  1. 生成长度从6到14的随机输出
  2. 随机排列数字000000到999999(是的,6位数字在表面上看起来相当随机,但是对于更大的字符集,您不需要这么多字符)
  3. 现在以必须保留独特性的方式将它们组合在一起。最简单的方法是简单地连接实体,但您当然可以考虑更不明显的解决方案。

小规模示例

  1. 生成随机性:

    sdfdsf xxer ver

  2. 生成唯一性:

    xd ae bd

  3. 组合:

    xdsdfdsf aexxer bdver

请注意,此方法假定每个条目至少有一定数量的字符,这似乎是您问题的情况。


1
除了缺乏熵之外,这个主要问题是仍然需要快速从允许的字符中构建一个字符串。Martijn和我使用base64库解决了这个问题,它接受字节并返回ASCII码,一旦你这样做了,你也可以将其交给urandom()字节。由于集合的存在,唯一性不会影响速度。没有检查唯一性的我的解决方案与检查唯一性的解决方案之间的时间差异非常小,以至于由于系统负载的随机性,其中一个比另一个更快。 - Adam Barnes
@AdamBarnes 感谢您的评论。我担心检查唯一性会使这种方法过于高效,不值得一试。我将其保留在此处以供娱乐价值。-- 最后一次提醒:您确定速度差异不是因为您已经接受了使用集合(用于检查唯一性)的潜在开销吗? - Dennis Jaheruddin
我很“有信心”,但并不“确定”。由于您没有提供代码示例,我无法测试您的实现。虽然我可以自己编写它,但我忙于扩展自己的答案到荒谬的长度...(对此感到抱歉)。如果您感觉有趣,请疯狂地拼凑出一个实现,并自行尝试。如果愿意,您可以针对我的存储库开放一个PR。 - Adam Barnes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接