c - LUTインデックスを概算する方法は？

Question

私は配列を持っています

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

bCを使用して、指定されたa値の検索を見つける最も簡単な方法は何ですか？そのためにはある程度の概算が必要だと思いますか？たとえば、できるだけ早くa = 851見つけたいとき。-29

Answer 1

最速の汎用アルゴリズムは二分探索です。マッピング配列のサイズによっては、検索を手作業でコーディングすることを検討してください。サイズ 32 にはもっともらしいかもしれませんが、私はこれ以上大きくはしません。マイクロコントローラーでは、運が良ければ、完全に拡張された二分探索が 50% 高速になる可能性があります。

しかし、マッピングがあまり非線形でない場合は、優れた代替手段があります。

aの範囲をk同じサイズの範囲に分割します。ここkで、 はマッピング配列のエントリ数よりも大きくなく、各範囲の端点のマッピングが次の範囲の端点と同じか、それよりも 1 つ多くなります。（これが可能であれば、それはまさに「非線形すぎない」という意味です）。各エンドポイントを元の配列のインデックスにマップする別の配列を作成します。(端点は等間隔であるため、端点ではなくインデックスのみが必要です。) 各範囲について、下端点の対応するインデックス値はa、範囲の上端点以上の元の配列内の最小値のインデックスです。上記の要件により、最大で 1 つしか存在しないことに注意してください。aしたがって、各エンドポイントのインデックスは常にa範囲の終わりの値を指し、範囲aの始まりの値は常に同じか前のインデックスのいずれかになります。

ここで、値を検索するには、最初に単純な線形計算 ( (val - minval)/k) である適切な範囲インデックスを見つけaてから、比較のためにインデックスを検索して、値を指定された値と比較します。値が検索した値より小さい場合はa、インデックスから 1 を引きます。次にb、インデックスから値を返します。

このようなアルゴリズムの例については、こちらの回答を参照してください。