0

问题

我需要从长度的主列表中创建项目组合列表n。由于主列表中的项目数量很少，这可以在没有并行化的情况下完成并且很快就会发生。但是，当我尝试使用该multiprocessing库来并行化列表的生成时，似乎需要更长的时间。这是一个例子：

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

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

我想生成所有口味的组合，以及 size 的组合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

如果我称它为 size n_items = 2，它会快速生成元组列表。

make_combinations_n_items(item_list, 2)

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

为了尝试并行化它，我使用了这个示例multiprocessing指导的库，如下所示：

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）是否有更好/更快/更有效的方法来产生所有这些组合？

我可以根据需要提供更多信息。在此先感谢您的帮助。

4

1 回答 1

0

问：1）这是并行化此功能的正确方法吗？还是有更好/更有效/更快的方法？
问：2）是否有更好/更快/更有效的方法来产生所有这些组合？

在 Complexity-ZOO 中展示真正的双重麻烦地狱的绝佳案例：

所有人都可能已经检测到这里的实际复杂性大约增长。O( ~n!/k!/(n-k)! )在[SPACE]（RAM）和类似的大约。但是，接近 100.000 x 更慢的访问时间即将到来，并且将......因为它将停止为纯 RAM 内计算提供足够的 RAM（一个人可以通过耗尽内存轻松挂起 64 位 O/S -由设计不当的生产和存储组合数据进行管理，这些数据仅针对来自少至 100 个候选人的 N 元组。O( ~n! / k! / (n-k)! ) [TIME][SPACE]

虽然我们可能并且将会尽可能多地从标准 python 开销中卸载，但使用带有处理set()-s而不是list-manipulations (的散列技巧和智能迭代器list在这里很昂贵，因为它必须保持顺序，而这些组合不会)，但 RAM 消耗仍将推动[SPACE]由此[TIME]产生的成本。

从 10 个候选人中选择对几乎不需要 RAM[SPACE]和成本：~ 30 [us][TIME]

>>> 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]开始变得很重要，而且很多：

从大约 100 个候选人中选择对仍然相当便宜1.3 ~ 1.6 [ms] = 1300 ~ 1600 [us]，产生近 ~ 5000 个合法对：

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

选择三元组进入about的范围，~ 33 ~ 35 [ms]因为它产生和存储 about~ 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

从一百个候选者中选择 5 个元组将需要 8 GB 的 RAM（或者将开始出现毁灭性的交换，与 RAM 中的情况相比，处理速度要慢约 100.000 倍），仍然只需要生成一些~ 452.000.000 [us]并将small -s~ 75.287.520的最便宜数据类型的合法 5 元组存储在 about 中：int6.1 GB

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

CPU-monitor 证实了这一点，仅显示30% - 40%CPU 负载 问题很快就会进入内存[SPACE]绑定问题，其中[TIME]成本与内存管理和内存分配以及 mem-I/O 相关，而不是与内存的性质有关。计算。

如果在这种情况下，人们会尝试实例化一些（更糟糕的许多）[CONCURRENT]进程来工作（基于线程的尝试在这里将无济于事，由于 python 中央 GIL 锁，这是已知的重新 - [SERIAL]-ise所有线程工作，这实际上可以防止任何形式的并发处理和仅在极端情况下，延迟屏蔽可能有助于为在标准python中进行多线程付出努力产生任何积极的回报（加上 - 注意成本在所有multiprocessing与实例化相关的成本中-对-再次，[SPACE]相关和[TIME]相关成本很重要乘以尝试生成多少实例（以及如何生成））

如果为了将 N 元组的问题减少为仅在 4 个 CPU 内核上协调生成的 (N-1) 元组而尝试拆分工作（这可能看起来很有吸引力[CONCURRENT]）时尚，预期的加速（生成（N-1）元组而不是全面的 N 元组）将花费巨大的附加成本来管理部分结果的重新组装，[SPACE]从只是[CONCURRENT]--管道和内存管理成本是昂贵的，如果只是重新加入部分结果，在仍然多运行内存绑定处理期间，任务正在等待通过人工拆分连接 4-CPU 处理-cores 协调工作流程。

一些确凿的事实，上面展示了从少至 100 个候选者创建的 N 元组，这是一个很好的机会来测试任何更好的方法（如果有的话），以克服[SPACE]-和-[TIME]绑定阶乘中的双重麻烦 -规模化的教科书问题。

我向您的计算机科学教授致以最诚挚的问候，让您进入复杂性动物园地狱的这个角落……并弄脏您的手。

恢复 ：

虽然对于小尺寸（元组、三元组）来说，纯处理的成本[SPACE]和成本都很小，如果不是可以忽略不计的话，它永远不会证明尝试产生新的 4进程（在显着增加-on cost ) 来利用所有 4-CPU 内核，然后为将“分布式”进程的结果重新组装回主 python 进程而提供额外的昂贵附加成本。[TIME][SERIAL][CONCURRENT]

这永远无法证明一次性支付所有附加费用是合理的。

智能的矢量化代码，numpy如执行，而是使用低级语言编码的函数，在多核上工作，而无需将任何数据传输到远程进程，而是让其他 CPU 内核在原始数据多个区域上独立进行智能计算，使用 smart-在预取的相干内存块内进行对齐缓存相关的好处。

由于尺寸较大，计算可能会在某种程度上享受分工，标准 python 代码的巨大[SPACE]相关成本将很快破坏任何严重的亚线性加速，因为附加成本主要来自结果重新组装回主 python 进程加上所有 4[CONCURRENT]个工作单元将在它们的拆分计算“骑行”期间毁灭性地竞争资源共享池（ RAM ），再次以巨大的内存管理不利成本（不提到交换引发的系统窒息，这可能很容易挂断所有 O/S 努力，以在所有请求进程之间公平交易资源并遵守所有系统设计的优先级计划）

最后但并非最不重要的 - 奖金部分：

对于语法，检查这个。

有关性能调整的想法。

对于将数据传输到/从生成的进程的附加成本进行基准测试（基准测试事实在那里令人惊讶地讨厌，所以不要被负票的歇斯底里分心，案例 B、C 和 D 的基准测试代码是重要的价值重复使用）。

有关正确计算实例化更多进程的所有附加成本以及（参数那里+结果返回）通信成本以及工作原子性对最终、实际可实现的加速的影响的更多详细信息，请不要错过并感受免费阅读当代对架空天真的阿姆达尔定律的批评

于 2019-08-22T22:00:50.980 回答