14장.탐색

Transcription

1 DATA STRUCTURES USING C CHAPTER 탐색 1/28

2 탐색 (search) 이란? 여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 2/28

3 맵 (map) 또는사전 (dictionary) 자료를저장하고키를이용해원하는자료를빠르게찾을수있도록하는자료구조 맵은키를가진레코드 (keyed record) 또는엔트리 (entry) 라불리는키 - 값쌍 (key, value) 을테이블에저장 맵의추상자료형 데이터키를가진레코드 ( 엔트리 ) 의집합연산 search(key): 탐색키 key를가진레코드를찾아반환한다. insert(entry): 주어진 entry를맵에삽입한다. delete(key): 탐색키 key를가진레코드를찾아삭제한다. 3/28

4 맵을구현하는방법 (1) 정렬되지않은배열을사용하는방법 (2) 정렬된배열을이용하는방법 (3) 이진탐색트리를이용하는방법 (4) 해싱을이용하는방법 4/28

5 순차탐색 (sequential search) 탐색방법중에서가장간단하고직접적인탐색방법 정렬되지않은배열을처음부터마지막까지하나씩검사 평균비교횟수 탐색성공 : (n + 1)/2번비교 탐색실패 : n번비교 8 을찾는경우 탐색성공 종료 9 8 탐색계속 5 8 탐색계속 8=8 탐색성공 2 를찾는경우 탐색계속 5 2 탐색계속 8 2 탐색계속 3 2 탐색계속 7 2 탐색계속 더이상항목이없음 탐색실패 5/28

6 순차탐색알고리즘 // int 배열 list 의순차탐색 int sequentialsearch(int list[], int key, int low, int high) { for(int i=low; i<=high; i++) if(list[i]==key) return i; return 1; } 시간복잡도 : O(n) 6/28

7 이진탐색 (binary search) 정렬된배열의탐색에적합 배열의중앙에있는값을조사하여찾고자하는항목이왼쪽또는오른쪽부분배열에있는지를알아내어탐색의범위를반으로줄여가며탐색진행 ( 예 ) 10 억명중에서특정한이름탐색 이진탐색 : 단지 30 번의비교필요 순차탐색 : 평균 5 억번의비교필요 7/28

8 이진탐색 5을탐색하는경우 7과비교 < 7이므로앞부분만을다시탐색 를 3과비교 > 3이므로뒷부분만을다시탐색 5 6 5==5 이므로탐색성공 5 6 2을탐색하는경우 7과비교 < 7이므로앞부분만을다시탐색 를 3과비교 < 3이므로앞부분만을다시탐색 1 2>1이므로뒷부분만을다시검색 1 더이상남은항목이없으므로탐색실패 8/28

9 이진탐색알고리즘 search_binary(list, low, high) middle low 에서 high 사이의중간위치 if( 탐색값 list[middle] ) return TRUE; else if ( 탐색값 < list[middle] ) return list[0] 부터 list[middle-1] 에서의탐색 ; else if ( 탐색값 > list[middle] ) return-1 return list[middle+1] 부터 list[high] 에서의탐색 ; 이진탐색구현 순환호출을이용한구현 반복을이용한구현 시간복잡도 : O(logn) 9/28

10 색인순차탐색 Indexed sequential search 인덱스 (index) 테이블을사용하여탐색의효율증대 주자료리스트에서일정간격으로발췌한자료저장 주자료리스트와인덱스테이블은모두정렬되어있어야함 복잡도 : O(m+n/m) 인덱스테이블 주자료테이블 인덱스테이블의크기 =m, 주자료리스트의크기 =n /28

11 보간탐색 interpolation search 사전이나전화번호부를탐색하는방법 ㅎ 으로시작하는단어는사전의뒷부분에서찾음 ㄱ ' 으로시작하는단어는앞부분에서찾음 탐색키가존재할위치를예측하여탐색하는방법 : O(log(n)) 이진탐색과유사하나리스트를불균등분할하여탐색 11/28

12 보간탐색 탐색위치계산예 12/28

13 해싱이란? 다른탐색방법들은키값비교하여항목에접근 해싱 (hashing) 키값에대한산술적연산에의해테이블의주소를계산 해시테이블 (hash table) 키값의연산에의해직접접근이가능한구조 아파트전체에대한하나의우편함 아파트의각호실별우편함 13/28

14 해싱의구조 해시테이블, 버킷, 슬롯 해시함수 (hash function) 탐색키를입력받아해시주소 (hash address) 생성 s 개의슬롯 해시함수 h(key) 주소 키 (key) 해시주소 3 M 개의버킷 i M-1 해시테이블 ht[] 14/28

15 충돌과오버플로 충돌 (collision): h(k1) = h(k2) 인경우 오버플로우 : 충돌이슬롯수보다많이발생하는것 주소 탐색키 해시함수 0 1 홍길동이순신장영실이율곡 M-1 M 개의버킷 해시테이블 15/28

16 이상적인해싱과실제해싱 학생정보저장을위한해싱의예 이상적인해싱 학번자릿수만큼의테이블준비 시간복잡도 : O(1) 5자리학번 : 테이블의크기가 100,000 10자리학번 : 테이블의크기가 10,000,000,000 불가능 실제해싱 해시함수를이용함 테이블의크기를줄임 충돌과오버플로발생 시간복잡도 : O(1) 보다떨어지게됨 16/28

17 해시함수 좋은해시함수의조건 충돌이적어야한다 함수값이테이블의주소영역내에서고르게분포되어야한다 계산이빨라야한다 제산함수 h(k)=k mod M 해시테이블의크기 M 은소수 (prime number) 선택 폴딩함수 탐색키 이동폴딩 = 699 경계폴딩 = /28

18 해시함수 중간제곱함수 탐색키를제곱한다음, 중간의몇비트를취해서해시주소생성 비트추출함수 탐색키를이진수로간주하여임의의위치의 k 개의비트를해시주소로사용 숫자분석방법 키중에서편중되지않는수들을해시테이블의크기에적합하게조합하여사용 18/28

19 문자열탐색키의해시함수예 #define TABLE_SIZE 13 int transform(char *key) { int number=0; while (*key!= \0 ) number += (*key++); return number; } int hash_function(char *key) { return transform(key) % TABLE_SIZE; } 탐색키덧셈식변환과정 (transform()) 덧셈합계해시주소 do for if case else return function /28

20 오버플로처리방법 선형조사법 충돌이일어난항목을해시테이블의다른위치에저장 충돌이 ht[k] 에서발생했다면, ht[k+1] 이비어있는지조사 만약비어있지않다면 ht[k+2] 조사 비어있는공간이나올때까지계속조사 테이블의끝에도달하게되면다시테이블의처음부터조사 시작했던곳으로다시되돌아오게되면테이블이가득찬것임 조사되는위치 : h(k), h(k)+1, h(k)+2, 체이닝 각버켓에삽입과삭제가용이한연결리스트할당 20/28

21 선형조사법 (linear probing) 버킷 1단계 2단계 3단계 4단계 5단계 6단계 7단계 [0] function [1] [2] for for for for for for [3] do do do do do do do [4] [5] [6] [7] [8] [9] case case case case [10] else else else [11] return return [12] if if if if if 군집화 (clustering) 현상발생 21/28

22 맵의구현 ( 선형조사법 ) int transform(char *key){ } int hash_function(char *key){ } typedef struct Record { char key[128]; char value[128]; } Record ; Record ht[table_size]; void init_map( ) { } void print_map( ) { } void add_record(char* key, char* value){ } Record* search_record( char *key ) { } void main() { init_map( ); add_record( "do", " 반복 " ); add_record( "for", " 반복 " ); add_record( "if", " 분기 " ); add_record( "case", " 분기 " ); add_record( "else", " 분기 " ); add_record( "return", " 반환 " ); add_record( "function", " 함수 " ); print_map( ); search_record( "return" ); search_record( "function" ); search_record( "class" ); } 22/28

23 실행결과 23/28

24 군집과결합완화방법 이차조사법 (quadratic probing) 선형조사법과유사하지만, 다음조사할위치를아래식사용 (h(k)+i*i) mod M 조사되는위치 : h(k), h(k)+1, h(k)+4, 군집과결합크게완화가능 이중해싱법 (double hashing) 재해싱 (rehashing) 이라고도함 오버플로가발생하면다른별개의해시함수를사용 step=c-(k mod C) h(k), h(k)+step, h(k)+2*step, 24/28

25 체이닝 (chaining) 오버플로우문제를연결리스트로해결 각버켓에고정된슬롯이할당되어있지않음 각버켓에, 삽입과삭제가용이한연결리스트할당 버켓내에서는연결리스트순차탐색 ( 예 ) 크기가 7 인해시테이블에서 h(k)=k mod 7 의해시함수사용 입력 (8, 1, 9, 6, 13) 적용 25/28

26 체이닝의예 1단계 (8) : h(8) = 8 mod 7 = 1( 저장 ) 2단계 (1) : h(1) = 1 mod 7 = 1( 충돌발생-> 새로운노드생성저장 ) 3단계 (9) : h(9) = 9 mod 7 = 2( 저장 ) 4단계 (6) : h(6) = 6 mod 7 = 6( 저장 ) 5단계 (13) : h(13) = 13 mod 7 = 6( 충돌발생-> 새로운노드생성저장 ) 26/28

27 테이블의구조및실행결과 typedef struct RecordNode { char key[128]; char value[128]; struct RecordNode* link; } Node ; Node* ht[table_size]; 27/28

28 해싱의성능분석 적재밀도 (loading density) 또는적재비율 저장되는항목의개수 n 과해시테이블의크기 M 의비율 해싱과다른탐색방법의비교 28/28