3

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

我当前的代码（这是最内层循环的主体）在 2^(1.5 * n) 个总和的时间内执行此操作，因为我将在 A 的（平均）2^(n/2) 个元素上迭代每个 i。

  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 只是 j 在“1”状态下具有来自 i 的 most_significant 位。这将我的时间减半，但这还不够（实际问题规模仍然需要数小时和数天）：

  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
    }
  }

你能推荐更好的算法吗？

附加图像，i 和 j 的列表为每个 i 求和，n=4：

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]

4

1 回答 1

4

分而治之？现在不到位。

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];
  }
}
于 2011-05-15T22:12:35.847 回答