c - 如何近似LUT索引？

Question

我有一个数组

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

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

Answer 1

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

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

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

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

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