c - 如何近似 LUT 索引？

Question

我有一个数组

...
//a      b
{860,   -30},
{853,   -29},
{846,   -28},
{838,   -27},
{830,   -26},
{822,   -25},
{814,   -24},
...

使用 C 查找b给定a值的最快方法是什么？我想这需要一些近似值？例如，当a = 851我想尽快找到时-29。

Answer 1

最快的通用算法是二分查找。根据映射数组的大小，您可以考虑手动编码搜索；这对于 32 号来说可能是合理的，但我不会更大。在微控制器上，如果幸运的话，完全扩展的二进制搜索可能会快 50%。

但是，如果映射不是太非线性，那么还有一个不错的选择。

将范围划分a为k大小相等的范围，其中k不比映射数组中的条目数大多少，以便每个范围端点的映射与下一个范围端点相同或多一个。（如果这是可能的；这正是我所说的“不太非线性”的意思）。创建另一个数组，将每个端点映射到原始数组的索引。（您只需要索引，而不需要端点，因为端点是均匀分布的。）对于每个范围，底部端点对应的索引值是a原始数组中最小值的索引，不小于该范围的顶部端点。请注意，由于上述要求，最多可以有一个a每个范围内的值，因此每个端点的索引将始终指向a范围结束的值，并且范围a开始的值将始终是相同的或前一个索引。

现在，要查找一个值，您首先要找出适当的范围索引，这是一个简单的线性计算 ( (val - minval)/k)，然后a通过查找索引来将该值与指示值进行比较以进行比较。如果该值小于查找的值a，则从索引中减去 1。然后b从索引中返回值。

有关此类算法的示例，请参阅我的答案here。