"보간 된"테이블 조회 용 데이터 구조

Question

1 변수 함수를 나타내는 2 차원 점 집합이 있습니다. 임의의 입력 값이 주어지면 가장 가까운 값을 선택해야합니다. 예 :

곡선 : (1,5) (2,8) (5,9)

입력 3 출력 : 8

내 주요 관심사 속도 공간은 '케이 만큼 중요합니다. 어떤 데이터 구조가 가장 좋을까요?

EDIT : 표는 정적이며, 그것은 런타임

Answer 1

이 테이블은 정적 또는 동적인지의 여부에 의존하는 동안 변화하지 않을 것이다.

정적 데이터 인 경우 간단한 정렬 된 배열 및 이진 검색으로 작업이 완료됩니다. 키를 찾지 못하면 키를 검색하여 위와 아래의 인덱스를 확인하여 검색 키에 더 가까운 키를 확인하고 관련 지을 수 있었던 값을 돌려줍니다.

데이터가 동적 인 경우 B + Tree 변형을 사용합니다 (모든 균형 트리 구조가 작동해야 함). 본질적으로 동일한 알고리즘이지만 인접한 배열 셀을 검사하는 대신 형제 노드를 검사해야합니다.

Answer 2

테이블이 정적이며 런타임 중에 변경되지 않는다고합니다. 그런 다음 탁월한 성능이 필요하고 테이블이 너무 크지 않으면 하드 코드 된 이진 검색을 수행하기가 어렵습니다. 당신이 준 테이블에 대한 , 그것은 다음과 같습니다

result = (x < 3.5 
      ? (x < 1.5 
       ? 5 
       : 8 
      ) 
      : 9 
     ); 

메인 프로그램에서 당신이 그것을 포함 할 수 있도록, 입력으로 테이블을, 그리고 출력으로 코드를 생성하는 작은 프로그램을 작성 할 수 있습니다 .

매크로를 사용하여 괜찮다면, 당신은 다음과 같이 조금 더 쉽게 작성 할 수 있습니다 이길 수있는 유일한 방법은 하드 코딩 된 해시 검색 함께

#define M(a,middle,b) (x < (middle) ? (a) : (b)) 

result = M(M(5, 1.5, 8), 3.5, 9); 

(사용

switch 문).

테이블이 실행 중에 변경 될 수있는 경우 프로그램이 시작될 때마다 코드를 생성하고 컴파일하여 dll에 링크하고 dll을로드 한 다음 실행합니다. 약 1 초가 걸릴 수 있습니다. 그리고 나서 고속이됩니다.