基本改进、集合和局部名称
使用集合,而不是列表,测试唯一性更快;集合成员测试独立于集合大小,需要常量时间,而列表需要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()
函数将结果限制为我们想要的数量:
from itertools import islice, repeat
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):
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),不再使用输出中的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):
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倍,因此我们最终会偏向于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方法一样快,但可以生成完整范围的密钥!