时间戳

首页 > 解决方案 > 可以并行生成排列吗？

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

问题描述

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

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

我用来生成排列列表的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 上运行，然后加入结果，那就太好了。

标签： pythonparallel-processingpermutationcombinatorics

解决方案

如果只是替换的排列，那将非常容易：只需在字符串的第一个字母上并行化，然后让每个线程添加字符串的尾部。这将为您提供 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()

推荐阅读