데이터 구조에서 손가락 검색

데이터 구조에 대한 손가락 검색은 구조가 지원하는 검색 작업의 확장으로 정의되며, 쿼리와 함께 데이터 구조의 요소에 대한 참조(손가락)가 제공됩니다. 요소에 대한 검색 시간은 데이터 구조에서 요소 수의 함수로 가장 자주 표시되는 반면, 손가락 검색 시간은 요소와 손가락 사이의 거리의 함수로 처리됩니다.

m개의 요소 집합에서 두 요소 a와 b 사이의 거리 d(a, b)는 순위 차이입니다. 요소 a와 b가 구조에서 i번째 및 j번째로 큰 요소인 경우 순위의 차이는 |i - j|입니다. 어떤 구조에서 일반 검색이 일반적으로 O(f(m)) 시간을 소비한다면, 손가락 요소 b를 사용하여 요소 a에 대한 손가락 검색은 이상적으로 O(f(d)) 시간을 소비해야 합니다. d ≤ m이므로 최악의 경우 손가락 검색은 일반 검색만큼 나쁘다는 것을 알 수 있습니다. 그러나 실제로 이러한 퇴행성 손가락 검색은 일반 검색보다 더 많은 작업을 수행합니다. 예를 들어 f(n)이 log(n)이고 최악의 경우 손가락 검색이 일반 검색보다 두 배 많은 비교를 수행하면 d> √n일 때 손가락 검색이 느려집니다. 따라서 대상이 실제로 손가락에 가깝다고 합리적으로 예상할 수 있는 경우에만 손가락 검색을 구현해야 합니다.

구현

일부 인기 있는 데이터 구조는 실제 구조에 대한 추가 변경 없이 손가락 검색을 지원합니다. 요소 a에 대한 검색이 a가 발견될 수 있는 간격을 좁혀서 수행되는 구조에서, 요소 b로부터의 손가락 검색은 일반적으로 검색 간격이 요소 a를 포함할 만큼 충분히 클 때까지 b에서 검색 프로세스를 역으로 수행하여 수행됩니다. 어떤 포인트 검색이 정상적으로 진행되는지.

정렬된 연결 목록

연결 목록에서 일반적으로 한쪽 끝에서 다른 쪽 끝으로 이동하여 요소를 선형 방식으로 검색합니다. 연결 목록이 정렬되어 있고 요소 b를 포함하는 일부 노드에 대한 참조가 있는 경우 요소 b에서 검색을 시작하여 O(d) 시간에 요소 a를 찾을 수 있습니다.

정렬된 배열

정렬된 배열 B에서 일반적으로 이진 검색을 사용하여 B에서 요소 a를 검색합니다. 손가락 탐색은 B[j] =b에서 단측 탐색을 구현하여 수행됩니다. 이진 검색은 각 비교 후에 검색 공간을 절반으로 줄이는 반면 단측 검색은 각 비교 후에 검색 공간을 두 배로 늘립니다. 특히, 단측 탐색의 k번째 반복(a>b 가정)에서 고려 중인 구간은 B[j, j+2 ^k-1 입니다. ]. B[j + 2 ^k-1 과 동시에 확장이 중지됩니다. ] ≥ a, 이 간격은 요소 a에 대한 이진 검색입니다. 단측 검색이 요소 a를 포함하는 구간을 찾기 위해 k 반복을 사용하는 경우 d> 2 ^k-2 . 이 범위를 이진 검색하면 또 다른 k 반복이 소모됩니다. 따라서 b에서 손가락 검색은 O(k) =O(log d) 시간을 소비합니다.

.

목록 건너뛰기

건너뛰기 목록에서 이 지점에서 검색을 계속하면 b 요소를 포함하는 노드에서 요소를 손가락으로 검색할 수 있습니다. a b이면 순방향으로 검색이 진행됩니다. 역방향 케이스는 건너뛰기 목록에서 일반 검색과 대칭이지만 정방향 케이스는 실제로 더 복잡합니다. 일반적으로 스킵 리스트에서의 검색은 리스트의 시작에 있는 센티넬이 가장 높은 노드로 간주되기 때문에 빠를 것으로 예상됩니다. 그러나 우리의 손가락은 높이가 1인 노드일 수 있습니다. 이 때문에 검색을 시도하는 동안 거의 오르지 않을 수 있습니다. 평소에는 절대 일어나지 않는 일. 그러나 이러한 복잡성에도 불구하고 O(log d) 예상 검색 시간을 달성할 수 있습니다.

트립

Treap은 BST(Randomized Binary Search Tree)로 정의됩니다. Treap에서 검색하는 것은 다른 BST에서 요소를 검색하는 것과 유사합니다. 그러나 Treaps는 distanced의 두 요소 사이의 예상 경로 길이가 O(log d)로 표시되는 속성을 가지고 있습니다. 따라서 요소 a에 대한 요소 b를 포함하는 노드에서 손가락 검색을 하려면 요소 a의 조상이 발견될 때까지 b 요소에서 트리를 올라갈 수 있으며, 이 지점에서 일반적인 BST 검색은 일반적인 방식으로 진행됩니다. 노드가 다른 노드의 조상인지 계산하는 것은 중요하지 않지만 예상 O(log d) 손가락 검색 시간을 제공하기 위해 이 형식의 쿼리를 지원하도록 트리를 확장할 수 있습니다.

줄과 나무

로프(데이터 구조)의 구현은 일반적으로 코드 위치 반복자를 사용하여 문자열을 방문합니다. 반복자는 문자열의 특정 문자를 가리키는 손가락으로 간주할 수 있습니다. 대부분의 균형 잡힌 트리와 마찬가지로 로프는 트리의 루트만 제공될 때 트리의 한 리프에서 데이터를 검색하는 데 O(log(m)) 시간이 필요합니다. 트리의 모든 잎사귀를 읽는 데 O(m*log(m)) 시간이 필요한 것 같습니다. 그러나 약간의 추가 정보를 저장하면 O(1) 시간에 "다음" 잎을 읽고 O(m) 시간에 트리의 모든 잎을 읽도록 반복자를 구현할 수 있습니다.