Python暴力破解算法优化：字符串模式搜索性能提升方案咨询

我尝试用Python内置库实现了一个简单的暴力破解方法来搜索目标字符串，代码如下：

from itertools import product
from multiprocessing import Pool
import time
import numpy as np

chars=np.array(['a','b','c','d', 'e', 'f', 'g', 'h', 'i', 'j'])
password='cgbjfifac'
min_length=1
max_length=9

def brute_force():
    for length in range(min_length, max_length + 1):
        for p in product(chars, repeat=length):
            guess = ''.join(p)
            if guess == password:
                return guess

这段代码在双核心Intel(R) Xeon(R) CPU @ 2.30GHz机器上运行耗时约87秒。我试过用Python标准库的多进程（Pool和map方法），但没得到性能提升。想请教下怎么进一步优化这个方法的性能，理想是能支持长度≥10的目标字符串。

首先得搞清楚为什么你的多进程方案没生效——大概率是因为你没合理拆分任务，或者进程间的通信开销抵消了并行带来的收益。下面给你几个针对性的优化方向，从易到难：

1. 修复多进程的任务拆分逻辑 #

itertools.product生成的序列如果直接丢给map，会因为任务粒度太细导致进程间调度开销过大。正确的做法是按长度拆分任务，每个进程负责一个或多个长度的猜解任务，并且在找到结果后立刻终止所有进程，避免无效计算：

from itertools import product
from multiprocessing import Pool

chars = ['a','b','c','d', 'e', 'f', 'g', 'h', 'i', 'j']
password = 'cgbjfifac'
min_length = 1
max_length = 9

def check_length(length):
    for p in product(chars, repeat=length):
        guess = ''.join(p)
        if guess == password:
            return guess

def brute_force_parallel():
    with Pool() as pool:
        # 按长度分配任务，用imap_unordered可以提前获取结果
        results = pool.imap_unordered(check_length, range(min_length, max_length+1))
        for result in results:
            if result is not None:
                pool.terminate()  # 找到结果立刻终止所有进程
                return result

if __name__ == '__main__':
    import time
    start = time.time()
    print(brute_force_parallel())
    print(f"耗时: {time.time() - start:.2f}秒")

2. 减少单进程内的冗余操作 #

你的原代码里有几个可以快速优化的点：

• 把chars从numpy数组改成普通Python列表——numpy擅长批量数值运算，字符串迭代场景下反而会带来额外开销
• 预计算目标字符串的长度，如果能确定密码长度，直接跳过其他长度的遍历（这能省掉大量无效循环）
• 避免不必要的字符串拼接操作，或者尽量减少拼接次数

优化后的单进程代码：

from itertools import product
import time

chars = ['a','b','c','d', 'e', 'f', 'g', 'h', 'i', 'j']
password = 'cgbjfifac'
password_len = len(password)  # 预计算目标长度

def brute_force_optimized():
    # 直接锁定目标长度，无需遍历所有长度
    for p in product(chars, repeat=password_len):
        if ''.join(p) == password:
            return ''.join(p)

3. 用JIT编译加速核心循环 #

Python的循环天生偏慢，用Numba把核心逻辑编译成机器码，能大幅提升速度。这里我们用数值索引代替字符串拼接，降低Python层面的开销：

from numba import jit
import time

chars = ['a','b','c','d', 'e', 'f', 'g', 'h', 'i', 'j']
char_indices = {c:i for i,c in enumerate(chars)}
password = 'cgbjfifac'
password_indices = [char_indices[c] for c in password]
password_len = len(password)
char_count = len(chars)

@jit(nopython=True)
def brute_force_numba():
    # 用数值索引模拟组合生成，避免字符串操作开销
    current = [0] * password_len
    while True:
        # 检查当前组合是否匹配
        match = True
        for i in range(password_len):
            if current[i] != password_indices[i]:
                match = False
                break
        if match:
            return current
        # 生成下一个组合
        i = password_len - 1
        while i >= 0:
            current[i] += 1
            if current[i] < char_count:
                break
            current[i] = 0
            i -= 1
        if i < 0:
            return None

def convert_indices_to_password(indices):
    return ''.join([chars[i] for i in indices])

if __name__ == '__main__':
    start = time.time()
    result_indices = brute_force_numba()
    result = convert_indices_to_password(result_indices)
    print(result)
    print(f"耗时: {time.time() - start:.2f}秒")

4. 策略层面的优化（非代码） #

暴力破解的时间复杂度是O(N^L)（N是字符集大小，L是字符串长度），当L≥10时，纯穷举的成本极高。可以通过策略减少搜索空间：

• 如果知道目标字符串的字符分布（比如某些字符出现频率更高），优先遍历这些字符的组合
• 提前过滤不符合格式的组合（比如已知目标开头是某个字符，直接跳过其他开头的组合）
• 结合字典攻击，先尝试常见字符串，再进行穷举

5. 底层语言扩展（进阶） #

如果以上优化还不够，可以用Cython把核心逻辑写成C级别的代码，进一步消除Python的解释开销。不过这个学习成本较高，但对于长字符串的暴力破解场景，收益非常明显。

内容的提问来源于stack exchange，提问作者anilsathyan7