带有多种掩码规则的字符串笛卡尔积解析

Vvvvvoid

众所周知,有一些社区是需要邀请注册的, 也就是会员可以生成邀请码, 来分享给为注册的朋友来使用.
但是很多时候, 别人分享出来的邀请码都是带有掩码的, 比如 “cp2iv*qpz*y*q*12” 这种.
同时 * 号可能是任意的字母或者数字.

我们可以简单分析一下,
任意的字母或者数字为 , “abcdefghijklmnopqrstuvwxyz0123456789” , 长度为 36
假如有4位掩码的话 , 一共有 36*36*36*36 = 1679616 组合

聪明的同学可能想到了使用递归来遍历每一位来生成, 具体实现如下:

[Python] 纯文本查看 复制代码

str_mask = "cp2iv*qpz*y*q*12"

def generate_real_codes():
    real_codes = []
    mask_length = len(str_mask)

    def generate_codes_helper(current_code, index):
        if index == mask_length:
            real_codes.append(current_code)
            return
        if str_mask[index] == '*':
            for char in "abcdefghijklmnopqrstuvwxyz0123456789":
                generate_codes_helper(current_code + char, index + 1)
        else:
            generate_codes_helper(current_code + str_mask[index], index + 1)

    generate_codes_helper('', 0)
    print(len(real_codes))  # 1679616
    return real_codes

输出:
1679616
Time taken: 1.39秒

有没有更高效的方法呢? 当然有的

[Python] 纯文本查看 复制代码

def generate_real_codes_v2():
    real_codes = []

    possible_chars = []
    for ch in str_mask:
        if ch == '*':
            possible_chars.append("abcdefghijklmnopqrstuvwxyz0123456789")
        else:
            possible_chars.append(ch)
    for code in product(*possible_chars):
        real_codes.append(''.join(code))
    print(len(real_codes))
    return real_codes

输出:


1679616
Time taken: 0.60秒

可以看到, 速度快了一倍.

这段改进后的代码之所以更高效，主要有以下几个原因：

1. 使用了itertools.product函数：在原始代码中，使用嵌套的循环来生成所有可能的解码结果。而在改进后的代码中，我们利用了itertools.product()函数，它接受多个可迭代对象作为参数，并返回它们的笛卡尔积。这样一来，我们可以将多个可迭代对象（包括包含掩码字符和实际字符的字符串）传递给product()函数，它会自动为我们生成所有可能的组合结果。这种方式避免了嵌套循环的使用，简化了代码结构，并且在性能上更为高效。

2. 减少了字符串拼接的次数：在原始代码中，每次生成一个解码结果时，都会使用''.join(code)来进行字符串拼接。而在改进后的代码中，我们将字符串拼接的操作移动到了最后。通过将每个解码结果存储为字符列表code，然后在生成完所有解码结果后，再一次性地进行字符串拼接，可以减少了字符串拼接的次数，提高了效率。

综上所述，通过优化字符集构建、使用itertools.product()函数和减少字符串拼接次数，改进后的代码在生成所有实际代码的过程中更高效。这使得我们能够更快地处理包含多种掩码规则的字符串，节省时间和资源。


到现在, 看似问题解决了, 但是还是不行
因为有些同学可能比较皮, 掩码很个性, 比如这种 “cp2iv★qpz★y★q*12”
而且这个同学还说 ★ 是随机数字, 而 * 是随机字母+数字.
因为我们脚本需要稍作优化.需要把具体的匹配规则抽出来, 当成可以配置变更的.,如下:

[Python] 纯文本查看 复制代码

mask_rule = {
    '*': "abcdefghijklmnopqrstuvwxyz0123456789",
    '★': "0123456789",
}

def generate_real_codes_v2_plu():
    invite_codes = []
    possible_chars = []
    for ch in str_mask:
        if ch in list(mask_rule.keys()):
            possible_chars.append(mask_rule.get(ch))
        else:
            possible_chars.append(ch)
    for code in product(*possible_chars):
        invite_codes.append(''.join(code))
    return invite_codes

------
感谢@hrh123 提供优化建议:

确实，如果生成的 invite codes 数量非常大，将它们全部存储在列表中可能会消耗大量的内存。
使用生成器（generator）可以避免这个问题，因为生成器会逐个生成 invite code，而不是一次性生成所有代码并存储在内存中。有点像是 懒加载.
代码如下:

[Python] 纯文本查看 复制代码

def generate_real_codes_v2_plu_plu():
    possible_chars = []
    for ch in str_mask:
        if ch in mask_rule:
            possible_chars.append(mask_rule[ch])
        else:
            possible_chars.append(ch)
    for code in product(*possible_chars):
        yield ''.join(code)

生成器对象本身并不直接支持获取长度，因为生成器是一种惰性计算的机制，它并不实际生成所有的元素。
为了获取生成器对象的长度，你可以使用一个辅助函数或技巧来实现。下面是一种可能的方法，使用生成器对象的元素逐个迭代，并计数它们的数量：

[Python] 纯文本查看 复制代码

invite_codes = generate_real_codes_v2_plu_plu()
# 使用计数器来获取生成器对象的长度
count = sum(1 for _ in invite_codes)

-----------


至此, 就基本结束了,
在搭配一些 爬虫脚本, 就可以实现某些社区 自动扫码 + 自动注册机制了

hrh123

事实上,你的第一个程序时间复杂度是O(a^k),其中a是字符串长度,k是str_mask的长度,因为需要进行a^k次递归调用,每次调用的时间是常数
而第二个程序的时间复杂度是O(k * a^k),因为当我们调用product(*possible_chars)时,相当于调用了product函数k次,并且每次传入了一个长度为a的序列作为参数,因此,product(*possible_chars)的时间复杂度是O (k* a^k);再来看for循环,这个循环是用来遍历product(*possible_chars)返回的迭代器.并将每个元组拼接成字符串.并添加到real_codes列表中.这个循环的时间复杂度也是O(k*a^k),因为迭代器中有a^k个元组，每个元组有k个字符，所以拼接字符串需要O (k)的时间,添加到列表需要O (1)的时间,所以总共需要执行O (k * a^k)次操作.综上所述,这个程序的时间复杂度是O(k*a^k)
而第二个程序比第一个运行起来快的主要原因是递归会导致栈溢出和重复计算的问题,增加函数调用的开销
你这2个程序都会创建一个巨大的列表对象,我的建议是用生成器来写

ccber

感觉像是一级棒的注册邀请码

ccber

ccber 发表于 2023-8-7 19:09
感觉像是一级棒的注册邀请码

赶紧收藏，以备不时之需。

lookfeiji

我知道生成器，也知道迭代器，但是整个看到一脸懵,好像值得细啃，收藏先

derong2006

收藏先，学习一下