我有三大向量集:A、B1 和 B2。这些集合存储在磁盘上的文件中。对于来自 A 的每个向量 a,我需要检查它是否可以表示为 a = b1 + b2,其中 b1 来自 B1,b2 来自 B2。向量有20个分量,所有分量都是非负数。
我现在是如何解决这个问题的(伪代码):
foreach a in A
foreach b1 in B1
for i = 1 to 20
bt[i] = a[i] - b1[i]
if bt[i] < 0 then try next b1
next i
foreach b2 in B2
for i = 1 to 20
if bt[i] != b2[i] then try next b2
next i
num_of_expansions++
next b2
next b1
next a
我的问题:
1. 关于如何使 if 更快的任何想法?
2、如何实现并行?
3. 当我有 B1, B2, ..., Bk, k > 2 时的问题 1, 2?
最佳答案
您可以按范数对 B1 和 B2 进行排序。如果 a = b1 + b2,则 ||a|| = ||b1 + b2|| <= ||b1|| + ||b2||,所以对于任意a和b1,你可以有效地消除B2中范数<||a||的所有元素- ||b1||。也可能有某种方式,利用B1和B2中范数的分布来决定是否要切换这两个集合中的角色。 (我不知道如何做到这一点,但在我看来,如果 B1 和 B2 中的范数分布明显不同,这样的事情应该成立。)
至于使其并行化,似乎每个循环都可以变成并行计算,因为一个内部迭代的所有计算都独立于所有其他迭代。
编辑
继续分析:因为 b2 = a - b1,我们也有 ||b2|| <= ||一个|| + ||b1||。因此,对于任何给定的 a 和 b1,您可以将 B2 中的搜索限制为范数在 ||a|| 范围内的那些元素。 ± ||b1||。这表明对于 B1,您应该选择平均范数最小的集合。
关于algorithm - 我怎样才能使这个矢量枚举代码更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5925370/