인덱스 매핑

Index mapping
지도 제작에 도움이 되는 색인 맵과 혼동하지 마십시오.

컴퓨터 과학의 인덱스 매핑(또는 직접 주소 지정 또는 사소한 해시함수)은 각 위치가 가능한 값의 우주에서 키에 해당하는 배열의 사용을 설명한다.[1]이 기법은 가능한 모든 키에 대해 한 위치의 배열을 할당할 수 있도록 키의 공간이 합리적으로 작을 때 가장 효과적이다.그 효과성은 배열에서 임의의 위치를 일정한 시간에 검사할 수 있다는 사실에서 비롯된다.

적용 가능한 배열

유효값이 작은 범위 내에서 제한되는 데이터의 실제적인 예가 많다.사소한 해시함수는 그러한 데이터가 조회 키 역할을 해야 할 때 적절한 선택이다.일부 예는 다음과 같다.

  • 해당 연도 월(1-12)
  • 당일의 (1~31)
  • 요일(1~7)
  • 인간 나이(0–130) – 예: 생명표지 보험계리표, 정기 주택담보대출
  • 공통 수학 연산자 기호, 숫자, 구두점 및 영어 알파벳을 포함하는 ASCII 문자(0–127)

예

사소한 해시함수를 사용하면, 비반복적인 테이블 검색에서 조건부 테스트와 분기를 완전히 제거하여 컴퓨터 프로그램의 명령 경로 길이를 줄일 수 있다.

분기 피

로저 세일(Roger Sayle)은 스위치 문으로 인해 발생하는 다방향 분기를 제거하는[2] 예를 제시한다.

횡대로 바가지 긁다 HasOnly30Days(인트로 m) {  바꾸다 (m) {  케이스 4:  // 4월  케이스 6:  // 6월  케이스 9:  // 9월  케이스 11: // 11월   돌아오다 진실의;  체납:   돌아오다 거짓의;  } }

테이블 조회로 대체할 수 있는 항목:

횡대로 바가지 긁다 HasOnly30Days(인트로 m) {  정태의 경시하다 바가지 긁다 T[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };  돌아오다 T[m-1]; }

참고 항목

참조

  1. ^ Cormen, Thomas H. (2009). Introduction to algorithms (3rd ed.). Cambridge, Mass.: MIT Press. pp. 253–255. ISBN 9780262033848. Retrieved 26 November 2015.
  2. ^ Sayle, Roger Anthony (June 17, 2008). "A Superoptimizer Analysis of Multiway Branch Code Generation" (PDF). Proceedings of the GCC Developers' Summit: 103–116. Retrieved 26 November 2015.