优化数组求和（子集问题）

Question

在我的程序中最热门的部分（根据gprof，占用90%的时间），我需要将一个数组 A 加到另一个数组 B 中。这两个数组都是2^n（n在18..24之间）大小的整数数组（为简单起见，实际存储的元素是mpz_t或小整数数组）。加法规则是：对于每个 i 在0..2^n-1之间，设置B[i]=sum(A[j])，其中j是位向量，并且j&~i==0（换句话说，如果i的第k位不是1，则不能将任何j的第k位设为1）。

我的当前代码（这是最内层循环的主体）需要2^(1.5 * n)次求和运算，因为我将迭代每个 i 在 (平均而言) 2^(n/2) 个A元素上。

  int A[1<<n]; // have some data
  int B[1<<n]; // empty
  for (int i = 0; i < (1<<n); i++ ) {
    /* Iterate over subsets */
    for (int j = i; ; j=(j-1) & i ) {
      B[i] += A[j];  /* it is an `sum`, actually it can be a mpz_add here */
      if(j==0) break;
    }
  }

我提到过，几乎任何数都可以从之前相加的值重新计算出来。我建议有一段代码可以在 n* 2^n 次求和的时间内完成同样的任务。

我的第一个想法是 B[i] = B[i_without_the_most_significant_bit] + A[j_new]; 其中 j_new 是只有 i 中最高位为 '1' 的 j。这使我的时间减少了一半，但这还不够（在实际问题规模上仍需要数小时或数天）：

  int A[1<<n];
  int B[1<<n];
  B[0] = A[0]; // the i==0 will not work with my idea and clz()
  for (int i = 1; i < (1<<n); i++ ) {
    int msb_of_i = 1<< ((sizeof(int)*8)-__builtin_clz(i)-1);
    int i_wo_msb = i & ~ msb;
    B[i] = B[i_wo_msb];
    /* Iterate over subsets */
    for (int j_new = i; ; j_new=(j_new-1) & i ) {
      B[i] += A[j_new];  
      if(j_new==msb) break; // stop, when we will try to unset msb
    }
  }

你能推荐更好的算法吗？

附加图片，对于n=4，列出每个i的i和j之和列表：

i  j`s summed
0  0
1  0 1
2  0 2
3  0 1 2 3
4  0 4
5  0 1 4 5
6  0 2 4 6
7  0 1 2 3 4 5 6 7
8  0                8
9  0 1              8 9
a  0 2              8 a
b  0 1 2 3          8 9 a b
c  0 4              8 c
d  0 1 4 5          8 9 c d
e  0 2 4 6          8 a c e
f  0 1 2 3 4 5 6 7  8 9 a b c d e f

请注意这些图形的相似性。

PS：msb魔术来自这里：在单词（int32）[C]中取消最高有效位。

- osgx

---

我很想知道你在这里做什么 - 这可能有助于我们提出优化策略的建议。 - Will A

你需要所有的2^n个子集吗？你可以通过一种中间相遇的方式来解决子集和问题，将输入分成两个相等的部分A和B，并枚举它们的子集。然后要找到目标和c，在A中枚举每个元素a，并在B中搜索c-a。 - Rob Neuhaus

我建议优化代码，使循环k从n到0，在其中可以计算k位前缀i和j的子和。 - osgx

Answer 1

分而治之？现在不是原地操作。

void sums(int *a, int n, int *b) {
  if (n <= 0) {
    *b = *a;
    return;
  }
  int m = 1 << (n - 1);
  sums(a, n - 1, b);
  sums(a + m, n - 1, b + m);
  for (int i = 0; i < m; i++) {
    b[m + i] += b[i];
  }
}

- sped

---

为了获得更高的速度，可以将基本情况扩大并使用restrict。 - sped

在执行中，将对 a 和 b 元素进行多少次加法操作？是否有一个检查，判断 j 的二进制位集合是否是 i 的子集？我应该如何命名这个函数？ - osgx

@osgx 这是O(n 2^n)的加法。检查在递归调用中是隐含的。a、b和n对应于您的A、B和n。 - sped

太棒了！速度如此之快！使用大小，只需1-2分钟即可完成，而该解决方案在速度是两倍更快的计算机上需要数小时。欢迎来到stackoverflow，这是一个不错的起始答案！ - osgx

当b包含来自a和b状态的值时，如何在a=b（或原地执行相同操作）的情况下重写它，以避免破坏b的状态？ - osgx