algorithm - 我怎样才能使这个矢量枚举代码更快？

Question

我有三大向量集: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?

Answer 1

您可以按范数对 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，您应该选择平均范数最小的集合。