对于某些问题 [被证明是 NP 难题] 我别无选择,只能穷举搜索。我有一组数据——为简单起见,S = ['A', 'B', 'C', ... ,'Z']
并想应用一个函数 f
到长度为 N < len(S)
的所有子集这套。我不能在这里使用列表,因为二项式系数 binom(len(S),N)
是几十亿。但是 f(x), x∈S
的结果对于 S
的几乎所有值都是零.因此,在简单的情况下,一切都很好
from itertools import ifilter, combinations
answer = list(ifilter(lambda x: f(x) > 0, combinations(S,N)))
但在现实生活中,len(S) ~ 10⁴
和 N ~ 10²
.我想要的是使用 ipyparallel
在 CPU 引擎之间分配工作.我有一个有一百个 CPU 内核的小型集群。但我仍然负担不起将组合存储为列表的费用,因此我需要类似单独生成器的东西。
有一个couple的 examples如何将生成器拆分成 block ,但据我了解它们仍然是连续生成器。还有一个 idea @minrk 是相关的,但由于某种原因它的表现非常糟糕。
所以问题是:
- 有没有办法实现
itertools.ifilter
直接与ipyparallel
? 或 - 是否可以将 python 生成器分成一组独立生成器(将它们独立发送到
ipcluster
引擎)?
最佳答案
无论您如何并行化,穷举搜索在这里都是毫无希望的。由于 len(S)
和 N
的数量级如此之高,您将需要搜索大约 6e241 个候选解。这远远超出了人类希望构建的任何计算系统的能力。
您将需要使用更智能的算法。
关于python - itertools.ifilter 与 IPython 并行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34855403/