c - 使用查找表进行优化

Question

我为一个程序编写了一些 c 代码，该程序对声音数据进行了一些心理声学处理。

有一段代码运行得很慢。

我认为最好使用查找表。一个人将如何实施它？

任何指示或帮助将不胜感激！:)

score 6 · Accepted Answer

你的价值观不是等距的，所以这并不容易。但它仍然是可能的：取所有条件值的最大公约数（这里是 50），然后制作你的表格

byteout = lut[差异/50 + 12];

在查找表中，您可以按照发布的顺序使用您的值，如果您的步进为 100，您可以在其中复制条目。

顺便说一句，有一个错误，你所有的负面案例都被你的第一个案例捕获<=0（我的例子假设你想省略第一个案例）。

score 2 · Accepted Answer

首先，看看你想要第一次检查 0 的位置，因为它会让你所有的否定检查变得毫无意义。

其次，我可能会构建一个查找表作为 1300 个元素的数组，偏移 500（您的最低负值）。当您查找该数字时，每个元素都是您想要的结果。如果您正在寻找小于 -500 的值，请不要检查数组。

所以它看起来像这样：

table[0] = 0b0110; // -500 through -599
table[1] = 0b0110;
...
table[100] = 0b0101; // -400 through -499
table[101] = 0b0101;
...

查找将是：

if (value <= -600) {
    return 0b0111;
}
else {
    return table[value + 600];
}

这是一个足够小的值，数组的大小不会令人望而却步。在程序开始时使用循环进行初始化。

score 1 · Accepted Answer

二进制搜索获胜。

将所有可能的值存储在一个数组中，并确保对它们进行排序。

从中间开始，看看是否difference小于那个值。如果是这样，请移动到光标左侧的中间，然后重试。如果没有，请向右移动。继续前进，直到找到所需的值，然后使用它。

您的数组可能是具有最小值和相应byteout值的结构。

编辑：为了消除可能的误解，“每个可能的值”我并不是指 -1400 到 1400 之间的每个数字，只是您在原始代码中检查的值。

score 0 · Accepted Answer

让我们看一下第一部分：

if (difference <= 0)
  byteout = 0b0000;
else if (difference <= -600)
  byteout = 0b0111;

假设您的值为 -601。

它 <= 0 吗？是的，所以byteout = 0b0000;

你永远不会达到-600。如此有效，所有负值都是0b0000. 这可能是也可能不是设计使然，但如果是这样，您可以摆脱所有其他负值。

否则，我会考虑将其简化为公式（尽可能少的分支）或使用@Ebomike 的预计算查找表和二进制搜索解决方案。

4 回答 4