c - 查找表的 5 个整数中的唯一键

Question

我对图像数据使用了 5 交叉中值滤波器的变体在小型嵌入式系统上，即

    x
  x x x
    x

算法很简单，读取5个值，取最高的2并对这些进行一些计算并写回结果。

5个输入值均在0-20范围内。计算出来的值也在0-20范围内!

我想弄清楚是否可以使用查找表来加快速度事情顺利，但我未能生成可以使用的 key 。

举个例子，考虑输入是否在0-5范围内，生成唯一 key 的一种方法是采用二进制文件表示并连接数字，即

101 101 101 101 101

key = x[0] | x[1] << 3 | x[2] << 6 | x[3] << 9 | x[4] << 12

但是该 LUT 很大，大约有 23k 个项目。

由于 [5,0,0,0,5] 与 [5,0,5,0,0] 相同，因此进行了一种简化可能是使用 2 个 LUT，

LUT1 = [0, 1, 6, 31, 156, 781]

其中每一项都比 5 项的最大总和大 1之前的元素

然后 key 可以计算为(使用Python语法)

key = sum([LUT1[x[0]], LUT1[x[1]], LUT1[x[2]],
           LUT1[x[3]], LUT1[x[4]a]])

但同样，这种方法无法扩展到 0-20 的范围每个元素。

使用排序网络，如 Fastest sort of fixed length 6 int array不会提高性能；我只对2感兴趣最高值。

那么，是否有可能从五个正数中创建一个唯一的 key 0-20 范围内的整数，可用作索引查找表？

Answer 1

免责声明:这不是通用解决方案。

我遇到了类似的问题并通过以下方式解决:

1) 在位掩码中为 5 个值中的每一个设置一个位(至少 21 位，因此需要 32 位变量)。

2) 如果该位已设置(=重复值)，则索引变量(初始化为 -1)将设置为该值(如果它小于该值)。

3) 现在现在让解决方案“不通用”的部分，因为它的性能取决于非常快的位扫描指令的可用性(例如 x86 有一个):找到最高的位设置。它的索引是该对的第一个值。

4) 如果它等于“重复值”变量，那么第二个值也是这个值。

5) 否则，该对的第二个值是第二高位的索引。

6) 现在你有一对介于 0 和 20 之间的值，在我看来，21x21 的查找表已经足够小了。

在粗鲁的代码中:

int dup = -1;
uint_32 m = 0;
uint_32 vm;
int i;

for (i = 0; i < 5; ++i) {
   vm = 1 << val[i];
   if ((m & vm) && (dup < val[i])) {
       dup = val[i];
   }
   else {
       m |= vm;
   }
}

// Now the part that needs a very fast "get higest bit" function

top[0] = get_higest_bit(m);
if (top[0] == dup) {
    top[1] = top[0];
}
else {
    m &= ~(1 << top[0]);
    top[1] = get_higest_bit(m);
}

编辑:此外，面向位的运算符(<< 等...)必须足够快。 X86/x64 符合此要求。不保证在不同的 cpu 上。但至少表达式“1 << x”可以通过多种方式进行优化。