快速点产品,适用于非常特殊的情况

Question

给定大小为L的向量X,其中X的每个标量元素来自二进制集{0,1},如果大小为L的向量Y由整数组成,则找到点乘积z = dot(X,Y)价值元素.我建议,必须有一种非常快速的方法来做到这一点.

假设L=4; X[L]={1, 0, 0, 1}; Y[L]={-4, 2, 1, 0}我们必须找到z=X[0]*Y[0] + X[1]*Y[1] + X[2]*Y[2] + X[3]*Y[3](在这种情况下会给我们-4).

很明显,X可以使用二进制数字表示,例如,对于L = 32,整数类型为int32.然后,我们要做的就是找到这个整数的点积和一个32个整数的数组.您是否有任何想法或建议如何快速完成？

Answer 1

这确实需要分析,但您可能需要考虑另一种选择:

int result=0;
int mask=1;
for ( int i = 0; i < L; i++ ){
    if ( X & mask ){
        result+=Y[i];
    }
    mask <<= 1;
}

通常,位移和按位运算比乘法更快,但if语句可能比乘法慢,但是对于分支预测和大L我的猜测是它可能更快.但是,您确实需要对其进行分析,以确定它是否会导致任何加速.

正如下面的评论中指出的那样,手动或通过编译器标志(例如GCC上的"-funroll-loops")展开循环也可以加快这一速度(忽略循环条件).

编辑
在下面的评论中,提出了以下好的调整:

int result=0;
for ( int i = 0; i < L; i++ ){
    if ( X & 1 ){
        result+=Y[i];
    }
    X >>= 1;
}