6

考虑两个向量，A和B，大小为n， 7 <= n <= 23。A和B都仅由 -1、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);
}

这工作得相当好，但我不确定是否可以做得更好。对此事的任何评论都将受到高度赞赏。

4

4 回答 4

3

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

只是几个小点：

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

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

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

于 2013-11-01T18:16:29.363 回答
0

这里的一个严重问题是对正向量和负向量的psign和变量的重用。pvalue以这种方式混淆您的代码，对您的编译器和您自己都没有任何好处。

于 2013-11-01T18:20:59.100 回答
0

您是否可以将您的三元状态编码为 astd::bitset<2>并根据 定义产品and？例如，如果您的三元类型是：

 1 = P = (1, 1)
 0 = Z = (0, 0)
-1 = M = (1, 0) or (0, 1)

我相信您可以将他们的产品定义为：

1 *  1 =  1 => P * P = P => (1, 1) & (1, 1) = (1, 1) = P
1 *  0 =  0 => P * Z = Z => (1, 1) & (0, 0) = (0, 0) = Z
1 * -1 = -1 => P * M = M => (1, 1) & (1, 0) = (1, 0) = M

然后内积可以从元素的位开始，然后......我正在研究如何将它们加在一起。

编辑：

我的愚蠢建议没有考虑到(-1)(-1) = 1，我提出的表示无法处理。感谢@user92382 提出这个问题。

于 2013-11-01T18:33:33.583 回答
0

根据您的架构，您可能希望优化掉临时位向量——例如，如果您的代码要编译到 FPGA 或布局到 ASIC，那么就速度而言，一系列逻辑操作会更好/能量/面积比存储和读取/写入两个大缓冲区。

在这种情况下，您可以这样做：

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

这将非常好 - (a.value & b.value & ... ) 可以启用/禁用 XOR 门，其输出分成两个带符号的累加器，在累加之前记录第一个路径。

于 2017-07-11T17:19:32.697 回答