我正在寻找一种有效的方法来将数组拆分为具有相似直方图的 block 。
例如,给定数组:
l = np.array([1, 2, 3, 4, 1, 1, 1, 2, 3, 4, 55, 5, 5, 5, 5, 5, 3, 2, 2, 21, 2])
我想获得:
c1 = np.array([1, 4, 1, 5, 5, 3, 2])
c2 = np.array([2, 1, 3, 4, 5, 5, 2])
c3 = np.array([3, 1, 2, 55, 5, 2, 21])
不仅如此,每个 block 在给定函数 f 上应该具有相似的大小和相似的总和:
1. |sum(ci, f) - sum(cj, f)| < e, for i != j
2. |len(ci) - len(cj)| < e, for i != j
在哪里
sum(c, f) = f(c[0]) + ... + f(c[len(c)])
编辑:
澄清此举的用意。我想将列表上的流程并行化为 n
子流程,但成本必须在每个子流程之间平均分配。处理此列表中的元素的成本是数组 l
中相同位置的整数的函数 f
,其中 f 是该过程的计算复杂度。例如,f(i)=i^2
。因此,我希望所有进程都具有相同的计算成本,而不是让进程过早结束而其他进程永远持续下去。
最佳答案
让我们从一个非常弱的假设开始,即相似的直方图是按以下基本方式定义的:对于一组整数S1,直方图H(S1 )
类似于集合 S2 的直方图 H(S2)
如果 sum(S1) = sum(S2)
。
通常,您是在找到数组 A 的子集 S1、S2、...、SN 之后满足 f(S1) = f(S2) = ... = f(SN)
,以及在我们的假设下 f=sum
。不幸的是你有一个 k-Partition problem ,这是 NP 难的,如果你让某人找到一种有效的方法(即多时间)来做到这一点,正如你所要求的,结果将是 P=NP
首先在 stackoverflow 上被证明是正确的!
关于python - 将数组拆分为均匀分布的 block ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22862215/