python - 可以并行生成排列吗？

Question

我想知道我是否可以加快排列的生成。具体来说，我使用 [a-z] 中的 8 个，我想使用 [a-zA-Z] 中的 8 个和 [a-zA-Z0-9] 中的 8 个。我知道这会很快占用大量时间和空间。

即使是小写 ASCII 字符的长度为 8 的排列也需要一段时间并生成千兆字节。我的问题是我不了解底层算法，所以我无法开始弄清楚是否可以将问题拆分成更小的任务，然后再合并在一起。

我用来生成排列列表的 python 脚本:

import string
import itertools
from itertools import permutations

comb = itertools.permutations(string.ascii_lowercase, 8)

f = open('8letters.txt', 'w')
for x in comb:
        y = ''.join(x)
        f.write(y + '\n')

f.close()

有谁知道如何将其划分为子任务并稍后将它们组合在一起？有可能吗？

我可能只是尝试一种(可能)更快的方法来做这件事，但我在使用 C++ 及其 std::next_permutation() 时遇到了麻烦，所以我无法验证它是否可以加快速度，哪怕只是一点点还没有。

如果我可以将它分成 16 个任务，并在 16 个 Xeon CPU 上运行，然后加入结果，那就太好了。

Answer 1

如果它只是替换的排列，那将非常简单:只需并行化字符串的第一个字母，然后让每个线程添加字符串的尾部。这将为您提供 26 个独立任务。如果这还不够，您可以并行化前两个字母。

您想要一个排列无需替换，因此问题不会平凡分解。如果只想从一组 26、52 和 62 中挑选 8 个字母，则可以做一件天真的粗暴事情:在第一个字母上并行化，让线程只创建带替换的尾部并丢弃包含重复项的生成字符串。但是当你想从 26 个字母中挑选 25 个时，这就变得非常浪费了。

考虑到这个想法，我们可以做得更好!我们对字符串的第一个字母进行并行化处理，然后使用集合中的七个元素生成所有排列，不包括我们开始的字母。这样我们可以有 26 个任务(或 52 或 62)并且仍然使用该算法。这可能看起来像这样:

# Use whatever chars you want as the set.
chars = set(string.ascii_lowercase)

# We iterate through all the possible heads. This exact loop will be
# parallelized in the end.
for head in chars:
    # Exclude the head from the set.
    remaining_chars = chars - set(head)

    for tail in itertools.permutations(remaining_chars, 7):
        string = head + ''.join(tail)

        # Store the string in your list/file.

为了利用多个核心，我们使用了一个池。为此，我们首先需要一个函数来映射。这只是上面的一点重构:

def make_strings(head):
    remaining_chars = chars - set(head)
    strings = [
        head + ''.join(tail)
        for tail in itertools.permutations(remaining_chars, 7)]

    return strings

现在我们可以在其他地方创建一个池并让它映射到头上:

with multiprocessing.Pool() as pool:
    all_strings = pool.map(make_strings, chars)

池只获得了 Python 3 所需的 __enter__ 和 __exit__ 属性，所以我假设我们使用它。

完成后，将列表列表展平为普通字符串列表:

strings = [
    string
    for sub_list in all_strings
    for string in sub_list]

由于 26 是 16 个内核的奇数，我们可以考虑使用 itertools.permutation(remaining_chars, 2) 创建头部，然后使用集合减法生成最后 6 位数字。

---

这是 Python 3 的完整工作脚本，总结了所有内容:

import itertools
import multiprocessing
import string


chars = set(string.ascii_lowercase)


def make_strings(head):
    remaining_chars = chars - set(head)
    strings = [
        head + ''.join(tail)
        for tail in itertools.permutations(remaining_chars, 3)]

    return strings


def main():
    with multiprocessing.Pool() as pool:
        all_strings = pool.map(make_strings, chars)

    strings = [
        string
        for sub_list in all_strings
        for string in sub_list]

    print(strings[:100])


if __name__ == '__main__':
    main()