考虑两个 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);
}
这工作得相当好,但我不确定是否可以做得更好。非常感谢对此事的任何评论。
最佳答案
我喜欢 2 uint32_t
,但我认为您的实际计算有点浪费
只是一些小问题:
我不确定引用(通过
const &
获取a
和b
)——这增加了一个级别与将它们放在堆栈上相比是间接的。当代码这么小(可能是几个时钟)时,这很重要。尝试按值传递,看看会得到什么
不幸的是,__builtin_popcount
可能效率很低。我自己用过,但发现即使是我写的一个非常基本的实现也比这快得多。但是 - 这取决于平台。
基本上,如果平台有硬件 popcount 实现,__builtin_popcount
会使用它。如果不是 - 它使用非常低效的替代品。
关于c++ - 三元 vector 的快速内积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19732598/