分布式电源

Question

考虑到 powerset 操作（生成给定集合的所有可能子集）及其规模（时间复杂度为 O(n*2^n) ），我正在尝试水平扩展它（分布式解决方案）。不知道这是否容易实现（因此出现问题），但我会尝试分解问题并使其尽可能清楚。

考虑以下使用 python 的示例：

import itertools

s = [1, 2, 3, 4, 5]

for l in range(1, len(s)+1):   # this can be distributed

    for subset in itertools.combinations(s, l):
        print(subset)

可以（并且很容易）根据子集长度分配工作量。例如，如果我们有一个长度为 5 的集合，我们可以让每个工作人员计算长度为 N 的所有子集——在这种情况下，我们将有 5 个工作人员。为什么这对我没有吸引力是很明显的——工作负载分配根本不平衡。一组长度为 20 的集合将生成 184756 个长度为 10 的子集，而只有 20 个长度为 1 的子集（这意味着中间工人总是有更多的处理工作要做）。

问题

在这种情况下，有没有办法线性分配工作量，如何分配？重新表述问题 - 对于长度为 L 的集合，我可以分配工作以使用 N 个均衡的 worker 来计算幂集吗？

Answer 1

首先，这不是解决问题的好方法。指数增长意味着所需机器的数量也将呈指数增长。几乎在每种情况下，正确的答案都是 "Figure out how not to compute the power set."

就是说，这是分解事物的最简单方法。取前 'x' 个元素，并计算这些元素的所有子集。这为您提供了“2^x”份工作。将这些作业相对均匀地分配给 y 台机器。每台机器完成每个作业的计算子集并产生输出。

作为进一步的优化，在工作人员完成时分配工作。那样的话，如果一些工人运行很慢，你会让每个人都工作直到你完成。

（还有更多平衡的方法，但它们涉及担心你的幂集算法是什么。）

Answer 2

如果您使用整数的 n 位来表示 n 项子集中的项，您可以从 0 开始变量，并递增它以到达下一个子集。因此，为了在 k 个处理器之间平均分配工作，您可以简单地让处理器 #i 从 i 开始它的整数变量，并在每个步骤中将 k 添加到它。每个子集都将由一个处理器处理。

请记住，这对解决大问题没有多大帮助。如果你可以在一台计算机上解决大小为 x 的问题（我估计在今天的计算机上大约有 20 <= x <= 30），那么即使购买 1024 台计算机你也只能解决大小问题x+10.

分布式电源

Distributed Powerset

python

algorithm

distributed

powerset