在 Python 中迭代 n 嵌套 for 循环的更有效方法

Question

我目前正在开发一个“去散列”脚本，它允许用户输入一个输入，连同散列方法，该脚本遍历字符列表，构建不同长度的字符串，并尝试检查如果任何字符组合（长度为 1-8）经过散列后等于用户提供的输入。

例如用户提供'password'的散列版本，算法取所有可能，从长度1开始：

长度 1: a, b, c, d, ..., z

长度 2: aa, ab, ac, ..., zz

长度 3: aaa, aab, aac, ..., zzz

依此类推，直到达到长度8（包括它）。

它会逐一散列所有可能性，并检查它们是否等于用户的输入。如果是，程序输出未散列的字符串并停止搜索。

我首先考虑对长度 1 使用 1 个 for() 循环，对长度 2 使用 2 个嵌套 for() 循环，依此类推，但认为我可能会复制和粘贴太多相同的内容代码，所以我用谷歌搜索了一些其他选项，我发现我可以使用 itertools.

这就是我生成 n 嵌套 for() 循环的方式：

chars = "abcdefghijklmnopqrstuvwxyz"
ranges = []
for i in range(0, length):
    ranges.append(range(0, len(chars)))
for xs in itertools.product(*ranges):
    # build the string here, hash it and check if it maches the user's input

我没有提供完整的实现，因为不仅仅是检查（如果找到什么就写入文件，输出东西等等）。这个想法是，我意识到这个算法对于长度 1-4 工作得很好。长度为 1、2 或 3 的字符串可在不到一秒内找到，而长度为 4 的字符串也可能需要几分钟。

我还“改进”了搜索，使用 multiprocessing 并在每个进程中搜索两个长度的组。

问题是，该算法仍然效率不够。例如，如果我想搜索长度为 5 的字符串，我将不得不等待几个小时，而且我很确定这是实现我实际所做的更有效的方法。

还测试了 n 嵌套正常 for() 循环与这种类型的 itertool 实现的执行时间，发现 for() 循环快 2 倍。不应该正好相反吗？

你对如何改进我的算法有什么建议吗？

Answer 1

您可以直接使用 chars 作为 itertools.product 的可迭代对象。此外，product 接受一个可选参数 repeat 如果您想要一个可迭代对象与其自身的乘积。参考the documentation.

product 生成元组。要从字符串元组中获取字符串，请使用 ''.join().

from itertools import product

def find_password(hashed, length, chars = "abcdefghijklmnopqrstuvwxyz"):
    for p in product(chars, repeat=length):
        if hash(''.join(p)) == hashed:
            return ''.join(p)
    return None

password = 'aaabc'
print( find_password(hash(password), len(password)) )
# aaabc

此外，您可以使用 from string import ascii_lowercase 而不是硬编码您自己的字母表：

from string import ascii_lowercase

print(ascii_lowercase)
# abcdefghijklmnopqrstuvwxyz

在 Python 中迭代 n 嵌套 for 循环的更有效方法

More efficient way to iterate through n-nested for loops in Python

python

algorithm

itertools