4.1 관계

Size: px

Start display at page:

Download "4.1 관계"

병국 개
4 years ago
Views:

1 심볼테이블 사전 (dictionary) 철자검색기, 시소러스, 데이터베이스관리응용에서데이터사전 로더, 어셈블러, 컴파일러에의해생성되는심볼테이블 컴퓨터분야에서는심볼테이블이라는용어를사용 심볼테이블 이름 - 속성쌍의집합 C++ 에서 map<string, int> words ; words[ time ] = 1 ; 시소러스는이름은단어, 속성은동의어 컴파일러는이름은식별자로, 속성은초기값과그식별자를사용하는행의리스트

2 structure SymbolTable(SymTab) objects: 일련의이름-속성의쌍이며이름은중복이없다. functions: 모든 name 이름, attr 속성, symtab SymbolTab, max_size 정수에대하여 SymTab Create(max_size) ::= 최대용량 max_size인빈심볼테이블생성 Boolen IsIn(symtab, name) ::= if (name이 symtab에있으면 ) return 참 else return 거짓 Attribute Find (symtab, name) ::= if (name이 symtab에있으면 ) return 해당하는속성 else return 널속성 SymTab Insert(symtab, name, attr) ::= if (name이 symtab에있으면 ) 현재속성을 attr로대치 else symtab에 (name, attr) 의쌍을삽입 SymTab delete(symtab, name) ::= if (name이 symtab에없으면 ) return else symtab에 (name, attr) 를삭제

3 심볼테이블의표현 5.7 절의이진탐색트리를사용하면, n 개의식별자가들어있다면최악의경우시간복잡도는 O(n), 10 장에서의이진탐색트리는 O(log n) 해싱 (hashing) 은탐색을수행하지않고해싱함수라는수식에기반하여탐색, 삽입, 삭제를수행 O(1)

4 해싱테이블 b개의버켓으로분할된연속적인메모리공간 ht[0], ht[1], ht[b-1] 각버켓은 s개의슬롯을가짐 x ht[0] ht[1]. 해싱함수 f(x) 식별자 x를해싱테이블내의주소로변환 일련의식별자를 0부터 b-1 사이의정수로사상 Ht[b-1] 0 1 s-1 식별자밀도 (identifier density) n/t, n 은테이블에있는식별자의수, T 는총사용가능식별자수, 식별자의길이가 6 문자이고, 첫문자는알파벳문자이고, 나머지문자는알파벳또는숫자로제한하면 T = 26 x 36 x 36 x 36 x 36 x 36 > 1.6 x 10^9 적재밀도, 적재인수 (loading density, loading factor) a = n/(sb) f

5 동거자 (synonym) 버켓수 b 는총사용가능식별자수 T 보다아주작으므로해싱함수 f 는여러상이한식별자를동일버켓에사상시켜야하는경우가발생, f(i_1) = f(i_2) 인 i_1, i_2 버켓이빈슬롯을가지고있으면동거자를저장 오버플로 : 새로운식별자를가득찬버켓에해싱시키는경우 충돌 : 두상이한식별자가동일한버켓에해싱되는경우 버켓의크기가 1 인경우오버플로와충돌이동시에발생 예제 8.1 : b=26 개의버켓과 s=2 인해싱테이블 ht, c 라이브러리함수명으로 10 개의상이한식별자를고려할 적재인수는 a = 10 / 52 = 0.19 해싱함수 f(x) 는 x 의첫문자 a-z 를 0-25 로사상 라이브러리함수 acos, define, float, exp, char, atan, ceil, floor, clock, ctime 은각각버켓 0, 3, 5, 4, 2, 0, 2, 5, 2, 2 에해싱,

6 처음 8 개의식별자 슬롯 0 슬롯 1 0 acos atan 1 2 char ceil 3 define 4 exp 5 float floor 식별자 acos 와 atan 은동거자, float 와 floor, ceil 과 char 역시동거자, clock 은 ht[2] 에해싱되는데이버켓이가득차있으므로오버플로가발생하므로이를처리하는방법은 절

7 해싱함수 식별자 x 를해싱테이블내의버켓주소로변환 식별자밀도 n/t 가작으므로충돌을피할수는없다 b 개의버켓각각에임의의 x 가대응될확률이같은균일해싱함수가좋음, 예제 8.1 의함수는적합하지않음 해싱함수의종류 : 중간제곱, 제산, 접지, 숫자분석 중간제곱함수 식별자를제곱한후에그결과의중간에있는적당한수의비트를취하여버켓주소로한다. r 비트가사용된다면 2^r 크기의해싱테이블로사상 제산함수 f(x) = x % M M 은 20 보다작은소수로나누어지지않는수이면충분

8 접지함수 식별자 x 를여러부분으로나누어각부분을더하여해싱주소를만든다. x_1 = 123, x_2 = 203, x_3 = 241, x_4 = 112, x_5 = 20 이라할때, 이동접지는마지막비트를마지막자리와일치하도록맞춘뒤서로더하게되므로 699 의해싱주소를얻게된다. 경계접지는식별자의각부분들을분할경계에서접는다. 두번째와네번째를역으로하여 x_2 = 302, x_4 = 211 을얻은후에나머지모두와더하여 = 897 이해싱주소가된다. 숫자분석함수 모든식별자를미리알고있는경우에유용하며, 각식별자의숫자를조사하여편향된분포를가진숫자는제거되고, 해싱테이블의주소로쓰이는만큼의숫자만을남긴다.

9 충돌과오버플로를감지하는방법 선형개방주소법 (linear open addressing) 또는선형조사법 체인법 (chaining) 선형개방주소법 해싱테이블은 0 부터 N-1 의범위로인덱싱이가능한일차원배열 #define MAX_CHAR 10 /* 식별자의최대문자수 */ #define TABLE_SIZE 13 /* 최대테이블의크기 = 소수 */ typedef struct { char key[max_char] ; // 문자열을이용한키 /* 다른필드들 */ } element ; element hash_table[table_size] ;

10 테이블초기화 충돌과오버플로를감지하려면모든슬롯을비어있는초기상태로만들어야한다. 각슬롯을 null 로초기화 void init_table(element ht[]) { int i ; for (i=0; i<table_size; i++) ht[i].key[0] = NULL ; }

11 해싱테이블에식별자를삽입하기위해서는먼저키필드를숫자로변화한뒤에적당한해싱함수를적용해야한다. int transform(char *key) { /* 간단한덧셈방식으로정수범위내의자연수를생성 */ } int number = 0 ; while (*key) number += *key++ ; return number ; int hash(char *key) { /* 키를자연수로변환하여테이블크기로나눈나머지를복귀시킴 */ } return (transform(key) % TABLE_SIZE) ;

12 해싱테이블에새로운식별자를삽입 해싱주소의해당슬롯이비어있다면저장 버켓이가득차있다면가장가까이있으면서빈슬롯이있는버켓을찾음 : 선형개방주소법 예 ) for, do, while, if, else, function 의경우에해싱값을얻는과정, if 와 function 이같으므로, function 은그다음빈곳, ht[0] 에저장 식별자덧셈식변환 X 해싱 for do while if else function

13 0 function 1 2 for 3 do 4 while else if

14 선형조사법의구현 식별자 x 에대한 f(x) 를계산한후, ht[f(x)], ht[f(x)+1], ht[f(x)+2] 를차례로조사하여, 1. ht[f(x)+j] == x: x 가이미테이블에저장되어있으므로응용에따라중복식별자임을보고하던지, 다른필드값을변경 2. ht[f(x)+j] 가널 : 이위치에삽입 3. ht[f(x)+j]!= x: 다른문자열이저장된경우므로계속해서다음버켓을조사 4. 3 의경우에모든버켓을조사한후다시 ht[f(x)] 로돌아오면오류 함수 linear_insert() 가구현예

15 void linear_insert(element item, element ht[]) { } int i, hash_value ; i = hash_value = hash(item.key) ; while (strlen(ht[i].key)) { } if (!strcmp(ht[i].key, item.key)) { fprintf (stderr, Duplicate entry \n ) ; } exit(1) ; i = (i+1) % TABLE_SIZE ; if (i == hash_value) { fprintf (stderr, The table is full \n ) ; } ht[i] = item ; exit(1) ;

16 선형조사법은식별자를한군데로밀집하는경향이있음 예제 8.1 의 acos, atoi, char, define, exp, ceil, cos, float, atol, floor, ctime 을첫문자만을이용한해싱함수를이용하여 26 개의버켓을가진해싱테이블에삽입할때, 삽입할때까지의비교횟수 검색할경우에도평균 41/11 약 4 번소요 bucket x # of com parisons 0 aco s 1 1 ato i 2 2 ch ar 1 3 define 1 4 exp 1 5 ceil 4 6 cos 5 7 flo at 3 8 ato l 9 9 floor 5 10 ctim e 9 25

17 선형조사법의군집화문제를해결하기위해 1. 이차조사법 (quadratic probing) 사용 (f(x) + i) % b, 0 <= i <= b- 1 대신에 f(x), (f(x) + i^2) % b, (f(x) - i^2) % b 를검사 2. 재해싱 (rehashing) 사용 여러개의해싱함수 f_1, f_2,..., f_b 를사용 3. 임의조사법 : 연습문제

18 체인법 선형조사법에서는식별자를삽입할때서로다른해싱값을가진식별자와비교할경우가생겨서효율이좋지않음 atol 을삽입할경우처음두개와식별자가충돌할뿐이고그밖의식별자들과는충돌하지않지만빈슬롯을찾기위해비교해나간다. 하나의버켓을동거자리스트로구성하면식별자가다른것과는비교할필요없음,

19 #define MAX_CHAR 10 /* 식별자의최대문자수 */ #define TABLE_SIZE 13 /* 최대테이블의크기 = 소수 */ #define IS_FULL(ptr) (!(ptr)) typedef struct { char key[max_char] ; // 문자열을이용한키 /* 다른필드들 */ } element ; typedef struct list *list_pointer ; typedef struct list { element item ; list_pointer link ; }; list_pointer hash_table[table_size] ;

20 void chain_insert (element item, list_pointer ht[]) { /* 체인법을이용하여테이블에키를삽입 */ int hash_value = hash(item.key) // 해싱주소계산 list_pointer ptr, trail = NULL, lead = ht[hash_value] ; for(; lead; trail = lead, lead = lead->link) if (!strcmp(lead->item.key, item.key)) { fprintf(stderr, The key is in the table\n );exit (1) ; } ptr = (list_pointer) malloc (sizeof(list)) ; if (IS_FULL(ptr)) { fprintf(stderr, The memory is full\n ) ; exit (1) ; } ptr->item = item ; ptr->link = NULL ; if (trail) trail->link = ptr ; else ht[hash_value] = ptr ; }

21 어떤식별자를탐색하는평균비교횟수 acos, char, define, exp, float 에서는한번 atoi, ceil, floor 는두번, atol, cos 는세번 ctime 은네번이므로평균 21/11 = 1.91 [0] acos atoi atol [1] [2] [3] [4] char ceil cos define exp ctime [5] [6] [25] float floor

22 해싱함수에대한실험결과 : 그림 ,375, 24,050, 4909, 3072, 2241, 930, 762, 500 개의식별자를가진 8 개의테이블을탐색할때생기는평균버켓접근회수 체인이선형개방주소법보다오버플로처리성능우수 제산함수의성능이우수

14장.탐색

14장.탐색 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 탐색 1/28 탐색 (search) 이란? 여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열,