三元载体的快速内积

Question

考虑两个矢量,甲和乙,大小的Ñ,7 <= Ñ <= 23,这两个甲和乙仅由-1s,0和1.

我需要一个快速算法来计算A和B的内积.

到目前为止,我已经考虑过uint32_t使用以下编码将符号和值存储在单独的s中:

• 符号0,值0→0
• 符号0,值1→1
• 符号1,值1→-1.

我想到的C++实现如下所示:

struct ternary_vector {
    uint32_t sign, value;
};

int inner_product(const ternary_vector & a, const ternary_vector & b) {
    uint32_t psign = a.sign ^ b.sign;
    uint32_t pvalue = a.value & b.value;
    psign &= pvalue;
    pvalue ^= psign;
    return __builtin_popcount(pvalue) - __builtin_popcount(psign);
}

这种方法运行得相当不错,但我不确定是否可以做得更好.对此事的任何评论都非常感谢.

Answer 1

我喜欢 2 uint32_t，但我认为你的实际计算有点浪费

只是几个小点：

• 我不确定引用（ geta和bby const &） - 与将它们放在堆栈上相比，这增加了一定程度的间接性。当代码这么小（可能是几个时钟）时，这很重要。尝试按值传递，看看会得到什么

• __builtin_popcount不幸的是，效率可能非常低。我自己使用过它，但发现即使是我编写的非常基本的实现也比这快得多。但是 - 这取决于平台。

基本上，如果平台有硬件 popcount 实现，__builtin_popcount就使用它。如果不是 - 它使用非常低效的替代品。