c++ - 三元 vector 的快速内积

Question

考虑两个 vector ，A 和 B，大​​小为 n，7 <= n <= 23 . A 和B 都只包含-1、0 和1。

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

到目前为止，我一直在考虑使用以下编码将符号和值存储在单独的 uint32_t 中:

• 符号 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，但我认为您的实际计算有点浪费

只是一些小问题:

• 我不确定引用(通过 const & 获取 a 和 b)——这增加了一个级别与将它们放在堆栈上相比是间接的。当代码这么小(可能是几个时钟)时，这很重要。尝试按值传递，看看会得到什么

不幸的是，

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

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