在我的程序中最热门的部分(根据gprof,占用90%的时间),我需要将一个数组 A 加到另一个数组 B 中。这两个数组都是2^n(n在18..24之间)大小的整数数组(为简单起见,实际存储的元素是mpz_t或小整数数组)。加法规则是:对于每个 i 在0..2^n-1之间,设置
我的当前代码(这是最内层循环的主体)需要2^(1.5 * n)次求和运算,因为我将迭代每个 i 在 (平均而言) 2^(n/2) 个A元素上。
请注意这些图形的相似性。
PS:msb魔术来自这里:在单词(int32)[C]中取消最高有效位。
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]中取消最高有效位。