LUT 인덱스를 근사하는 방법은 무엇입니까?

Question

나는 배열

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

주어진 a 값 b 찾기 위해 C를 사용하여 가장 빠른 방법은 무엇입니까 있나요? 나는 근사치가 필요하다고 생각해? 예를 들어 a = 851 일 때 나는 가능한 한 빨리 -29을 찾고 싶습니다.

Answer 1

가장 빠른 범용 알고리즘은 2 진 검색입니다. 매핑 배열의 크기에 따라 검색을 직접 코딩하는 것을 고려할 수 있습니다. 그 크기 32에 대한 그럴듯한 수도 있지만, 나는 더 크게 가지 않을 것입니다. 마이크로 컨트롤러의 경우 완전히 확장 된 이진 검색은 운이 좋다면 50 % 빨라질 수 있습니다.

그러나 매핑이 너무 비선형 적이 지 않으면 좋은 대안이 있습니다.

각 범위 종점의 매핑이 하나와 동일하거나보다 1이되도록 k 맵핑 배열 내의 엔트리들의 수보다 훨씬 더 큰 아니다 k 동일한 크기의 범위로 a의 범위를 분할

다음 범위 끝점. (이것이 가능하다면 그것은 내가 너무 비선형 적이 지 않음을 의미한다.) 각 끝점을 원래 배열의 인덱스로 매핑하는 다른 배열을 만듭니다. 엔드 포인트가 고르게 쌓여 있기 때문에 인덱스 만 필요합니다. 각 범위에 대해 맨 아래 끝점의 해당 인덱스 값은 범위의 맨 위 끝점보다 작지 않은 원래 배열의 가장 작은 값 a의 인덱스입니다. 위에 제시된 요구 사항으로 인해 모든 범위에서 최대 하나의 a 값이있을 수 있으므로 각 끝점의 인덱스는 항상 범위 끝의 a 값을 가리키고 해당 값의 시작 부분의 값은 a입니다. 범위는 항상 동일하거나 이전 색인 일 것입니다.

이제 값을 검색하기 위해 간단한 선형 계산 ((val - minval)/k) 인 적절한 범위 색인을 계산 한 다음 비교 색인을 찾아 값을 표시된 a 값과 비교합니다. 값이 조회 된 값인 a보다 작 으면 인덱스에서 1을 뺍니다. 그런 다음 색인에서 b 값을 반환하십시오.

이러한 알고리즘의 예는 내 대답 here을 참조하십시오.