如何近似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。