并行化生成组合的过程
Parallelize process of generating combinations
问题
我需要根据长度为 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
如果我为大小 n_items = 2 调用它，它会快速生成元组列表。
make_combinations_n_items(item_list, 2)
我知道当项目数量增加时，可能的组合数量会增加 2n，我想并行化这个过程以更快地生成组合（本质上有每个核心都在 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) 这是并行化此函数的正确方法吗？还是有better/moreefficient/faster的方法？
2) 是否有 better/faster/more 有效的方法来生成所有这些组合？
我可以根据需要提供更多信息。在此先感谢您的帮助。
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?
在 Complexity-ZOO 中展示真正的双重麻烦地狱的绝佳案例：
所有人可能已经检测到这里的实际复杂性增加了大约。 O( ~n!/k!/(n-k)! ) 在 [SPACE]（RAM）中，同样大约。 O( ~n! / k! / (n-k)! ) [TIME] 但是，跳入 100.000 x 较慢的访问时间即将到来并将...作为[SPACE] 将不再为纯粹的内存内计算提供足够的 RAM（人们可以很容易地挂起 64 位 O/S 只需通过设计不当的生成和存储组合数据耗尽内存管理就可以了来自少至 100 个候选的 N 元组。
虽然我们可能并且将会从标准 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] 的成本开始变得重要，而且很多 :
从大约一百个候选人中选择对仍然相当便宜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
选择三元组进入 大约 ~ 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
从仅仅一百个候选者中选择 5 元组将需要 8 GB 的 RAM（或者毁灭性的交换将开始出现，与 RAM 中的情况相比，处理速度慢大约 100.000 倍的额外成本），仍然仅承载 一些 ~ 452.000.000 [us] 来生成和存储 ~ 75.287.520 合法的小 int-s 最便宜数据类型的 5 元组大约 6.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-loads
这个问题很快就变成了内存-[SPACE]-绑定问题，其中[TIME]成本更多地与内存相关管理和内存分配和mem-I/O，而不是计算的性质。
如果在这种情况下，人们会尝试实例化少量（越多越糟糕）-[CONCURRENT] 进程来工作（基于线程的尝试在这里无济于事，因为 python 中央 GIL 锁，已知重新 [SERIAL]-ise 所有线程工作，实际上阻止任何形式的并发处理和只是极端情况，延迟屏蔽可能有助于生成任何在标准 python 中投入多线程的积极回报（加上 - 注意所有与 multiprocessing 相关的实例化成本 - 正确 - 再次与 [SPACE] 相关和 [TIME] 相关成本是一个人尝试生成多少实例（以及如何生成）的倍数）
如果为了将 N 元组的问题简化为协调生成 4-[=167= 的 (N-1) 元组，是否尝试拆分工作（这看起来很有吸引力） ]-cores in a just-[CONCURRENT]-pipeline fashion，预期的加速（生成 (N-1)-tuples 而不是全面的 N-tuples）将会在管理部分结果的重新组装方面花费巨大的附加成本，来自 just-[CONCURRENT]-pipeline 的 [SPACE]-size 和内存管理成本是昂贵的，如果只是重新加入部分结果，在仍然多对运行内存绑定的处理任务中等待通过人工拆分连接 4-CPU-cores 编排的工作流程进行处理。
上面在从少至 100 个候选对象创建的 N 元组上展示的一些确凿的事实是测试任何更好的方法（如果有的话）以克服 [SPACE]-和-[TIME]-绑定因子尺度教科书问题。
我向你的计算机科学教授致以最诚挚的问候，让你进入复杂性动物园地狱的这个角落......并弄脏你的手。
继续：
虽然对于小尺寸（元组、三元组）来说，[SPACE] 和 [TIME] 成本都非常小，如果不是这样的话，已经显示为纯 [SERIAL] 处理可以忽略不计，它永远不会证明尝试产生一个新的 4-[CONCURRENT]-processes（以显着的附加成本）来利用所有 4-CPU-cores，然后容纳额外的昂贵附加 -关于将 "distributed" 流程的结果重新组装回主要 python 流程的成本。
这永远无法证明所有附加费用的一次性总付是合理的。
智能的矢量化代码，如 numpy，可以 "cooperate" 在具有多核生产力的非冲突操作中，但具有接近零附加成本，因为它没有实例化单独的进程来传输 "remote"-执行的作业，而是使用低级语言编码函数，这些函数在多核上工作而无需将任何数据传输到远程-处理，而是让其他 CPU 核心在原始数据多个区域上独立进行智能计算，使用智能对齐缓存相关的好处，从预取的连贯内存块中进行计算。
具有更大的尺寸，计算可能在某种程度上享受拆分工作，标准 python 代码巨大的 [SPACE] 相关成本将很快破坏任何严重的次线性加速，由于附加成本，主要来自将结果重新组装回主要 python 过程加上所有 4-[CONCURRENT]-work-units 将毁灭性地竞争共享资源池（RAM），在他们的拆分计算期间-"ride"，再次以内存管理的巨大不利成本（更不用说由交换引起的系统窒息，这可能很容易挂断所有 O/S 之间公平交易资源的努力所有询问进程并遵守所有系统设计的优先级安排）
最后但并非最不重要的 - 奖励部分：
有关语法，请检查 。
关于性能调优的想法this。
用于对传输数据的附加成本进行基准测试 to/from 产生的进程 this（基准测试事实令人惊讶地讨厌那里，所以不要被减票的歇斯底里分心，基准测试代码对于案例 B、C 和 D 是重用的重要值）。
有关正确计算实例化更多进程的所有附加成本以及（那里的参数 + 结果返回）-通信成本以及工作原子性对最终实际可实现的加速的影响的更多详细信息， 不要错过，随时阅读 contemporary criticism of overhead naive Amdahl's law
问题
我需要根据长度为 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
如果我为大小 n_items = 2 调用它，它会快速生成元组列表。
make_combinations_n_items(item_list, 2)
我知道当项目数量增加时，可能的组合数量会增加 2n，我想并行化这个过程以更快地生成组合（本质上有每个核心都在 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) 这是并行化此函数的正确方法吗？还是有better/moreefficient/faster的方法？
2) 是否有 better/faster/more 有效的方法来生成所有这些组合？
我可以根据需要提供更多信息。在此先感谢您的帮助。
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?
在 Complexity-ZOO 中展示真正的双重麻烦地狱的绝佳案例：
所有人可能已经检测到这里的实际复杂性增加了大约。 O( ~n!/k!/(n-k)! ) 在 [SPACE]（RAM）中，同样大约。 O( ~n! / k! / (n-k)! ) [TIME] 但是，跳入 100.000 x 较慢的访问时间即将到来并将...作为[SPACE] 将不再为纯粹的内存内计算提供足够的 RAM（人们可以很容易地挂起 64 位 O/S 只需通过设计不当的生成和存储组合数据耗尽内存管理就可以了来自少至 100 个候选的 N 元组。
虽然我们可能并且将会从标准 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] 的成本开始变得重要，而且很多 :
从大约一百个候选人中选择对仍然相当便宜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
选择三元组进入 大约 ~ 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
从仅仅一百个候选者中选择 5 元组将需要 8 GB 的 RAM（或者毁灭性的交换将开始出现，与 RAM 中的情况相比，处理速度慢大约 100.000 倍的额外成本），仍然仅承载 一些 ~ 452.000.000 [us] 来生成和存储 ~ 75.287.520 合法的小 int-s 最便宜数据类型的 5 元组大约 6.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-loads
这个问题很快就变成了内存-[SPACE]-绑定问题，其中[TIME]成本更多地与内存相关管理和内存分配和mem-I/O，而不是计算的性质。
如果在这种情况下，人们会尝试实例化少量（越多越糟糕）-[CONCURRENT] 进程来工作（基于线程的尝试在这里无济于事，因为 python 中央 GIL 锁，已知重新 [SERIAL]-ise 所有线程工作，实际上阻止任何形式的并发处理和只是极端情况，延迟屏蔽可能有助于生成任何在标准 python 中投入多线程的积极回报（加上 - 注意所有与 multiprocessing 相关的实例化成本 - 正确 - 再次与 [SPACE] 相关和 [TIME] 相关成本是一个人尝试生成多少实例（以及如何生成）的倍数）
如果为了将 N 元组的问题简化为协调生成 4-[=167= 的 (N-1) 元组，是否尝试拆分工作（这看起来很有吸引力） ]-cores in a just-[CONCURRENT]-pipeline fashion，预期的加速（生成 (N-1)-tuples 而不是全面的 N-tuples）将会在管理部分结果的重新组装方面花费巨大的附加成本，来自 just-[CONCURRENT]-pipeline 的 [SPACE]-size 和内存管理成本是昂贵的，如果只是重新加入部分结果，在仍然多对运行内存绑定的处理任务中等待通过人工拆分连接 4-CPU-cores 编排的工作流程进行处理。
上面在从少至 100 个候选对象创建的 N 元组上展示的一些确凿的事实是测试任何更好的方法（如果有的话）以克服 [SPACE]-和-[TIME]-绑定因子尺度教科书问题。
我向你的计算机科学教授致以最诚挚的问候，让你进入复杂性动物园地狱的这个角落......并弄脏你的手。
继续：
虽然对于小尺寸（元组、三元组）来说，[SPACE] 和 [TIME] 成本都非常小，如果不是这样的话，已经显示为纯 [SERIAL] 处理可以忽略不计，它永远不会证明尝试产生一个新的 4-[CONCURRENT]-processes（以显着的附加成本）来利用所有 4-CPU-cores，然后容纳额外的昂贵附加 -关于将 "distributed" 流程的结果重新组装回主要 python 流程的成本。
这永远无法证明所有附加费用的一次性总付是合理的。
智能的矢量化代码，如 numpy，可以 "cooperate" 在具有多核生产力的非冲突操作中，但具有接近零附加成本，因为它没有实例化单独的进程来传输 "remote"-执行的作业，而是使用低级语言编码函数，这些函数在多核上工作而无需将任何数据传输到远程-处理，而是让其他 CPU 核心在原始数据多个区域上独立进行智能计算，使用智能对齐缓存相关的好处，从预取的连贯内存块中进行计算。
具有更大的尺寸，计算可能在某种程度上享受拆分工作，标准 python 代码巨大的 [SPACE] 相关成本将很快破坏任何严重的次线性加速，由于附加成本，主要来自将结果重新组装回主要 python 过程加上所有 4-[CONCURRENT]-work-units 将毁灭性地竞争共享资源池（RAM），在他们的拆分计算期间-"ride"，再次以内存管理的巨大不利成本（更不用说由交换引起的系统窒息，这可能很容易挂断所有 O/S 之间公平交易资源的努力所有询问进程并遵守所有系统设计的优先级安排）
最后但并非最不重要的 - 奖励部分：
有关语法，请检查
关于性能调优的想法this。
用于对传输数据的附加成本进行基准测试 to/from 产生的进程 this（基准测试事实令人惊讶地讨厌那里，所以不要被减票的歇斯底里分心，基准测试代码对于案例 B、C 和 D 是重用的重要值）。
有关正确计算实例化更多进程的所有附加成本以及（那里的参数 + 结果返回）-通信成本以及工作原子性对最终实际可实现的加速的影响的更多详细信息， 不要错过，随时阅读 contemporary criticism of overhead naive Amdahl's law