生成组合的并行化过程

Question

问题

我需要从长度为n的主列表创建一个项目组合列表。对于主列表中的少量项，这可以在不并行的情况下完成，而且发生得很快。然而，当我尝试使用multiprocessing库来并行化列表的生成时，似乎需要更长的时间。举个例子：

假设我有一个名为item_list的项目列表（我将使用冰淇淋口味）

item_list = ['chocolate', 'strawberry', 'vanilla', 'pineapple']

我想用大小组合n_items生成所有口味组合，所以我编写了一个函数来实现这一点：

import itertools
def make_all_combinations_n_items(item_list, n_items):
    out = []
    for combo in itertools.combinations(item_list, n_items):
        out.append(combo)

    return out

如果我按sizen_items = 2调用它，它会快速生成元组列表。你知道吗

make_combinations_n_items(item_list, 2)

我知道当项目的数量增加时，可能的组合的数量增加为2^{n，我想并行化这个过程以更快地生成组合（基本上是让每个核心在不同的n_items值上工作）。我有4个核可用。你知道吗}

为了尝试并行化，我使用了multiprocessing库，由this example指导，如下所示：

import multiprocessing as mp

pool = mp.Pool(mp.cpu_count())

new_combos = [pool.apply(
    make_all_combinations_n_items,
    args = (item_list, n_items))
    for n_items in range(1, len(item_list) + 1)
]

pool.close()

这个过程没有这么快发生，事实上，我不知道这个过程是否有效。当我复制下面的示例代码并运行它时，得到了相同的结果。你知道吗

问题

我有两个问题：

1）这是并行化这个函数的正确方法吗？还是有更好/更有效/更快的方法？你知道吗

2）是否有更好/更快/更有效的方法来产生所有这些组合？你知道吗

我可以根据需要提供更多的信息。事先谢谢你的帮助。你知道吗

Answer 1

Q : 1) Is this the proper way to parallelize this function? Or is there a better/more efficient/faster way?
Q : 2) Is there a better/faster/more efficient way to produce all of these combinations?

展示复杂动物园内真正的双重麻烦地狱的绝佳案例：

所有人都可能已经检测到，这里的实际复杂性在^{>（RAM）中增长了约O( ~n!/k!/(n-k)! )，类似地，也增长了约^{>^{>，但是，跳转到10万倍的较慢访问时间即将到来，并且将。。。由于[SPACE]将不再为纯内存计算提供足够的RAM（一个人可以很容易地挂起64位的O/S，只需耗尽内存管理就可以了，因为设计不当，只需在N元组上生成和存储多达100个候选的组合数据。你知道吗

---

虽然我们可能也将尽可能地从标准python开销中卸载，但使用哈希技巧和智能迭代器来处理set()-s而不是list-操作（list在这里很昂贵，因为它必须保持顺序，而组合不需要），然而，RAM的消耗将在[SPACE]和[TIME]两个维度上驱动所产生的成本。你知道吗

从10个候选者中选择配对在[SPACE]中几乎不需要RAM，在[TIME]中花费~ 30 [us]：

>>> from zmq import Stopwatch     # Stopwatch methods {.start()|.stop()} used
>>> aClk = Stopwatch()            # for benchmarking ~ [us]-resolution timer
>>> import itertools              # for .combinations()
>>>
>>> aSet = set( range( int( 1E1 ) ) )
>>> aClk.start();_=[i for i in itertools.combinations(aSet,2)];aClk.stop()
30
30
30
53
30

同样，从10名候选人中选出三人，所需时间几乎相同：

>>> aSet = set( range( int( 1E1 ) ) )
>>> aClk.start(); _ = [ i for i in itertools.combinations( aSet, 3 ) ]; aClk.stop()
56
54
53
52
51

---

现在，将数据移动到[SPACE]的成本开始变得重要，而且很多：

从大约一百个候选者中挑选配对仍然相当便宜，产生了大约5000对合法配对：

>>> aSet = set( range( int( 1E2 ) ) )
>>> aClk.start();_=[i for i in itertools.combinations(aSet,2)];aClk.stop()
1963
1591
1322
1326
1547
1601

选择三元组进入约~ 33 ~ 35 [ms]的范围，因为它产生并存储约~ 162.000个合法三元组：

>>> aSet = set( range( int( 1E2 ) ) )
>>> aClk.start();_=[i for i in itertools.combinations(aSet,3)];aClk.stop()
34741
33505
35580
35932
32989
33434

选择四重奏将使我们到达~ 600 ~ 730 [ms]，因为它必须存储所有~ 3.921.225合法四重奏：

>>> aSet = set( range( int( 1E2 ) ) )
>>> aClk.start();_=[i for i in itertools.combinations(aSet,4)];aClk.stop()
592453
723026
721529
729759
699055
704901

从100个候选者中选择5个元组将需要8gb的RAM（或者破坏性的交换将开始出现，与in-RAM情况相比，处理速度慢了大约100.000倍），仍然承载着一些~ 452.000.000 [us]来生成和存储~ 75.287.520合法的5元组，这些合法的5元组中最便宜的数据类型是int-s，大约在6.1 GB：

>>> aSet = set( range( int( 1E2 ) ) )
>>> aClk.start();_=[i for i in itertools.combinations(aSet,5)];aClk.stop()
451758912

CPU监视器证实了这一点，显示的CPU负载不超过 这个问题很快就变成了一个内存绑定的问题，其中[TIME]成本更多地与内存管理、内存分配和mem-I/O有关，而不是与计算的性质有关。你知道吗

在这种情况下，如果尝试实例化几个（越糟的多）进程来工作（基于线程的尝试在这里没有帮助，因为python中央GIL锁，它被认为是重新初始化所有线程工作的，它实际上阻止了任何形式的并发处理，并且只是一些可能出现延迟掩蔽的情况帮助将为在标准python中使用多线程而付出的努力产生任何积极的回报（加上-小心所有multiprocessing相关的实例化成本-对-同样，与[SPACE]相关和[TIME]相关的成本事关尝试生成多少实例（以及如何生成）的次数）

---

如果为了把N元组的问题简化成4个CPU核上的（N-1）元组的协调生成，而试图将工作（这看起来很有吸引力）拆分成一个管道方式，预期的加速（去（N-1）元组生成而不是满标度的N元组）将在管理部分结果的重新组装上花费巨大的附加成本，从仅仅[CONCURRENT]管道和内存管理成本来看仍然是显著的[SPACE]大小，如果只是重新加入部分结果，在这期间，仍有许多要运行的内存受限处理任务等待通过人工拆分的join 4-CPU-cores编排的工作流进行处理。你知道吗

上面展示了一些关于由只有100个候选人是一个很好的机会来测试任何更好的方法，如果有这样的方法的话，来战胜[SPACE]-和-[TIME]绑定因子规模的教科书问题的双重麻烦。你知道吗

我向你的计算机科学教授致以最诚挚的问候，让你走进这个复杂动物园地狱的角落。。。把你的手弄脏。你知道吗

---

简历：

虽然对于小尺寸（元组，三元组）来说，纯处理的[SPACE]和[TIME]成本都很小，即使不可忽略，也永远无法证明有必要产生一个新的4 [CONCURRENT]进程（以显著的附加成本）来利用所有4-CPU核，接下来，为了适应将结果从“分布式”进程重新组装回主python进程而产生的额外昂贵的附加组件成本。你知道吗

这永远不会成为一次性支付所有附加成本的理由。你知道吗

像numpy这样的智能矢量化代码可以在非冲突操作中“协作”，具有多核生产力，但附加成本几乎为零，因为它不实例化单独的进程来传输作业以进行“远程”执行，而是使用低级别的语言编码函数，这些函数在多核上工作，而不需要任何附加成本曾经将任何数据传输到远程进程，而是让其他CPU核在多个区域的原始数据上独立地进行智能计算，使用智能对齐缓存相关的好处是在预取的一致内存块中进行。你知道吗

由于体积更大，计算可能会有点分散工作，标准python代码巨大的[SPACE]相关成本将很快摧毁任何严重的次线性加速，因为附加成本，主要是将结果重新组装回主python进程，再加上所有4-[CONCURRENT]工作单元，在它们的分裂计算“骑行”期间，它们将对共享资源池（RAM）进行毁灭性的竞争，同样要付出巨大的内存管理不利成本（更不用说源于交换的系统窒息，这可能很容易中断所有O/S在所有请求过程中公平交易资源的努力，并遵守所有系统设计的优先级计划）

---

最后但并非最不重要的一点-额外部分：

有关语法，请选中this。你知道吗

关于性能调优的想法this。你知道吗

对于基准测试，将数据传输到衍生流程或从衍生流程传输数据的附加成本this（基准测试事实在那里令人惊讶地令人讨厌，因此不要被负面投票的歇斯底里情绪分散注意力，案例B、C和D的基准测试代码是重用的重要价值）。你知道吗

有关实例化更多流程的所有附加成本的正确核算以及（参数+结果）通信成本以及工作原子性对最终实际可实现的加速的影响的更多详细信息，请不要错过并随时阅读contemporary criticism of overhead naive Amdahl's law