Sentinel 값

Sentinel value
센티넬 노드 또는 카나리 값과 혼동하지 마십시오.

컴퓨터 프로그래밍에서 sentinel 값(플래그 값, 트립 값, 로그 값, 신호 값 또는 더미 [1]데이터라고도 함)은 일반적으로 루프 또는 재귀 알고리즘에서 그 존재를 종료 조건으로 사용하는 알고리즘의 컨텍스트에서 특별한 값입니다.

sentinel 값은 대역 외 데이터(명시적인 크기 표시 등)가 제공되지 않은 경우 데이터의 끝을 검출할 수 있는 대역 내 데이터 형식입니다.이 값은 모든 법적 데이터 값과 구별되도록 선택해야 합니다. 그렇지 않으면 이러한 값의 존재가 데이터의 종료를 미리 알리는 신호(반증명서 문제)가 되기 때문입니다.파수꾼 값은 물리적 파수꾼으로 사용되는 농담 때문에 때때로 "카이로의 코끼리"로 알려져 있습니다.안전한 언어에서는 대부분의 sentinel 값을 옵션타입으로 대체할 수 있습니다.이 옵션타입은 예외적인 케이스의 명시적인 처리를 강제합니다.

예

일반적인 sentinel 값과 그 사용 방법의 예를 다음에 나타냅니다.

  • null 종단 문자열의 끝을 나타내는 null 문자입니다.
  • 연결된 목록 또는 트리의 끝을 나타내는 Null 포인터입니다.
  • 등간격 데이터 값 스트림의 최상위 비트. 예를 들어 8비트 ASCII 문자로 구성된 스트림의 8번째 비트. 특수 속성(역비디오, 굵은 글씨 또는 기울임꼴 등) 또는 스트림의 끝을 나타내는 8비트 바이트로 저장됩니다.
  • 음수가 아닌 정수 시퀀스의 끝을 나타내는 음수 정수

변종

약간 다른 상황에서 사용되는 관련 방법은 데이터 끝에 특정 값을 배치하여 일부 처리 루프에서 종료에 대한 명시적 테스트가 필요하지 않도록 하는 것입니다. 이 값은 다른 이유로 이미 존재하는 테스트에 의해 종료되기 때문입니다.위의 용도와 달리, 이것은 데이터가 자연스럽게 저장 또는 처리되는 방식이 아니라 종료를 확인하는 간단한 알고리즘에 비해 최적화입니다.이것은 일반적으로 [2][3]검색에 사용됩니다.

예를 들어, 정렬되지 않은 목록에서 특정 값을 검색할 때 모든 요소가 이 값과 비교되며, 동일한 값이 발견되면 루프가 종료됩니다. 단, 값이 없을 경우 각 단계에서 검색이 정상적으로 완료되지 않았는지 테스트해야 합니다.검색된 값을 목록 끝에 추가하면 검색이 실패하여 내부 루프에서 명시적으로 종료 테스트가 필요하지 않습니다.이후에도 일치 여부를 판단해야 합니다.단,[4] 이 테스트는 반복마다 1회만 실행할 필요가 있습니다.Knuth는 데이터 끝에 배치된 값을 Sentinel이 아닌 더미 값으로 호출합니다.

예

어레이

예를 들어, C의 배열에서 값을 검색하는 경우 다음과 같이 간단하게 구현할 수 있습니다. "no result"를 반환하는 반증명 문제를 해결하기 위해 음수(비활성 인덱스)를 사용합니다.

인트 발견하다(인트 arr[], size_t 렌, 인트 값) {     위해서 (인트 i = 0; i < > 렌; i++)         한다면 (arr[i] == 값)             돌아가다 i;     돌아가다 -1; // 찾을 수 없습니다. }

단, 루프가 반복될 때마다 값이 발견되었는지와 어레이 끝에 도달했는지의 두 가지 테스트가 수행됩니다.이 후자의 테스트는 sentinel 값을 사용하여 회피합니다.어레이를 1개의 요소(메모리 할당이나 청소 없이) 확장할 수 있다고 가정하면 다음과 같이 링크된 목록에 대해 보다 현실적입니다.

인트 발견하다(인트 arr[], size_t 렌, 인트 값) {     인트 i;      arr[렌] = 값; // sentinel 값 추가     위해서 (i = 0;; i++)         한다면 (arr[i] == 값)             브레이크.;     한다면 (i < > 렌)             돌아가다 i;     또 다른             돌아가다 -1; // 찾을 수 없습니다. }

의 테스트i < len는 아직 존재하지만 루프 외부로 이동했습니다.루프 외부에는 (값에 대한)1개의 테스트만 포함되어 있으며 sentinel 값에 의해 종료가 보증됩니다.sentinel 값이 히트한 경우 종료 시 체크가 1회 행해져 각 반복의 테스트가 대체됩니다.

특히 도달한 경우 어레이의 마지막 요소를 임시로 센티넬로 대체하여 처리할 수도 있습니다.

인트 발견하다(인트 arr[], size_t 렌, 인트 값) {     인트 지난;      한다면 (렌 == 0)         돌아가다 -1;     지난 = arr[렌 - 1];     arr[렌 - 1] = 값; // sentinel 값 추가     위해서 (인트 i = 0;; i++)         한다면 (arr[i] == 값)             브레이크.;     arr[렌 - 1] = 지난;     한다면 (arr[i] == 값)             돌아가다 i;     또 다른             돌아가다 -1; // 찾을 수 없습니다. }

「 」를 참조해 주세요.

레퍼런스

  1. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Second ed.). Addison-Wesley. pp. 213–214, 631. ISBN 0-201-03809-9.
  2. ^ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox 3 Representing Sequences by Arrays and Linked Lists (PDF). Springer. p. 63. ISBN 978-3-540-77977-3.
  3. ^ McConnell, Steve (2004). Code Complete (2nd ed.). Redmond: Microsoft Press. p. 621. ISBN 0-7356-1967-0.
  4. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and searching. Addison-Wesley. p. 395. ISBN 0-201-03803-X.