Python 검색 알고리즘

< 선형 검색 >

 

 선형 검색이란(Linear search) 직선 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다. 배열 맨 앞부터 순서대로 원소를 스캔하는 원소의 값이 정해지지 않은 배열에서 검색할 때 사용하는 유일한 방법이다. 

 

                                                    #ssearch_while.py

seq_search 함수로 입력한 원소의 개수만큼 i와 a의 길이가 같으면, 값 검색에 실패 하였으므로 -1을 반환, a에 찾고자 하는 key값이 있다면 그 배열의 인덱스를 return하는 기본적인 검색 알고리즘 구조이다.

 

for i in range(len(a)):                        <--  seq_search함수의 while 문 대신 for문으로 더 짧고 간결하게 나타낼 수 있다. 

   if a [i] ==key:

      return i

return -1

 

 

 

# ssearch_test2.py

 

 

 

 3개의 배열에서 특정 인덱스를 각각 검색하는 프로그램입니다. 튜플 a에서 int형 정수, float형 실수가 있어도 검색하는데 문제는 없고, str형 문자열 b안에서 문자를 검색할 수도 있습니다.

 

 

 

 

 

 

 

 

 위의 선형 검색은 반복할 때마다 2가지 종료 조건을 체크합니다. 단순한 판단이지만 이 과정을 계속 반복하면 종료 조건을 검사하는 비용(cost)을 무시할 수 없습니다. 이 비용을 반으로 줄이는 방법이 앞으로 배울 보초 법(sential method)입니다. 찾고자 하는 값이 원래 데이터에 존재하지 않아도 끝 인덱스까지 스캔하는 단계에서 선형 검색의 종료 조건을 성립시킬 수 있습니다. 또한 선형 검색의 종료 조건은 판단할 필요는 없는데 이유는 검색할 값이 마지막 인덱스까지 같은 값이 없더라도 추가하기 때문입니다. 이처럼 보초는 반복을 종료하는 판단 횟수를 줄이는 역할을 합니다.

 

                                                        #ssearch_sential. py

배열 seq를 a로 복사하고, a의 마지막에 보초인 Key를 추가합니다.그러면 원래의 배열 맨 끝에 보초를 추가한 새로운 배열이 완성됩니다. ssearch_while.py 안에서 if문이 2개 있었습니다. 하지만 보초법에서는 if i == len(a)의 조건이 필요 없기때문에 반복을 종료하기 위한 판단 횟수가 절반으로 줄어듭니다.

 

 

 

 

< 이진 검색 >

 

 이진 검색(binary search)은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘입니다. 이진 검색 범위는 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 한다면 값은 0, n-1, (n-1)//2로 초기화시킵니다. 하나씩 이동하여 검색하는 선형 검색과 달리 주목할 점은 검색할 원소의 범위 중앙으로 단숨에 이동합니다. 이진 검색에서 범위를 좁히는 과정은 2가지로 볼 수 있는데

1) a [pc] < key : 중앙(pc)에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝 pl로 지정하고, 검색 범위를 뒤쪽 절반으로 좁힌다.

2) a[pc] > key : 중앙(pc)에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝 pr로 지정하고, 검색 범위를 앞쪽 절반으로 좁힌다.

 

 

                                              #bsearch. py

bin_search의 while문에는 범위를 좁히는 과정과 제약 조건이 들어가 있고, 아래의 for문을 보면 앞서 입력한 값과 그 다음 인덱스의 관계를 if 문으로 설정해놓은것을 확인할 수 있는데 이유는 정렬된 데이터여야 하기 때문이다.

 

 

cf) 복잡도(complexity)

 

 프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라집니다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 합니다.

1. 시간 복잡도 - 실행하는 데 필요한 시간을 평가합니다.

2. 공간 복잡도 - 메모리와 파일 공간이 얼마나 필요한지를 평가합니다.

 

 

 

 

< 해시 법 >

 

 해시 법(hashing)은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말합니다. 원소의 검색뿐 아니라 추가, 삭제도 효율적으로 수행할 수 있습니다. 원소의 값을 원소 개수로 나눈 값을 해시값이라고 합니다. 해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 합니다. 하지만 키와 해시값의 대응 관계가 1:1일 필요는 없는데 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 합니다. 

 해시 법에서 충돌이 발생한 경우 2가지 방법으로 대처할 수 있는데 첫 번째는 체인 법, 두 번째는 오픈 주소법이라고 합니다. 체인 법은 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결하는데, 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드(head node)를 참조하는 것입니다.

 

 

 #chained_hash. py

 

 01~14행은 Node 클래스를 만드는 과정입니다. Node 클래스는 개별 버킷을 나타내며 그 안에 3개의 필드가 있습니다. key(키), value(값), next(뒤쪽 노드를 참조)인데 Node 클래스는 키와 값이 짝을 이루는 구조입니다. Node형 인스턴스를 초기화하는 __init__() 함수는 3개의 인수를 전달받아 각각 대응하는 필드인 self.key, self.value, self.next에 대입합니다.

 

 17~34행은 ChainedHash 해시 클래스를 만드는 과정입니다. capacity는 해시 테이블의 크기를 나타내고, table은 해시 테이블을 저장하는 list형 배열을 나타냅니다. 모든 원소는 None으로 지정.

hash_value 함수에서 인수 key에 대응하는 해시값을 구할 수 있습니다. 추가로 key가 int인 경우와 아닌 경우를 나눠야 하는데 정수가 아닌 경우에는 그 값으로는 바로 나눌 수 없기 때문에 표준 라이브러리로 형 변환을 해야 해시값을 얻을 수 있습니다.

 

 

 

 

 

 

 

 

 37~47행은 키로 원소를 검색하는 search() 함수입니다. key인 원소를 검색하여, 찾으려는 값의 해시값을 구한 후 table [hash]이 가리키는 연결 리스트의 값이 None이면 검색 실패, 같은 값이면 성공. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔합니다. 

 

 50~64행은 원소를 추가하는 add() 함수입니다. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 합니다. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패, 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가합니다.

 

 67~83행은 원소를 삭제하는 remove() 함수입니다. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색합니다. 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제합니다. 그렇지 않으면 삭제에 실패합니다.

 

 

 

 

 

 

 

 

 

 86~95행은 원소를 출력하는 dump() 함수입니다.  해시 테이블의 내용을 한꺼번에 통째로 출력하는 것을 말합니다. 이 함수의 실행으로 해시값이 같은 버킷이 연결 리스트에 의해 체인 모양으로 묶인 모습을 확인할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

< 오픈 주소법 >

 

 해시 충돌이 발생할 때 해결하는 또 다른 방법으로 오픈 주소법(open addressing)이 있습니다. 오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시 법(closed hashing)이라고도 합니다.

 

 

 #open_hash. py

 

 

 

1행~11행은 각각 필요한 모듈의 함수 그리고 버킷의 속성을 담은 Status의 클래스. 그 안에 데이터가 저장되어있으면 값을 0, 비어있으면 1, 삭제되었으면 2로 저장한다.

 

 14~ 31행은 Bucket 클래스의 key, value, stat을 초기화 그리고 필드에 맞는 값을 설정하는 set함수, 속성을 설정하는 set_status로 구성.

 

 35행의 OpenHash클래스에는 오픈 주소법으로 구현하는 해시 클래스이고, 필요한 함수들의 구현, 앞의 chained_hash.py와 다른 것은 Bucket을 가지고 활용하는 것과 Node를 사용한다는 것이지만 별반 큰 차이는 없다. 

 

 

 

 

 

 

 

 

 

 

 37행 초기화 함수의 capacity 해시 테이블의 크기와, table은 해시 테이블의 개수.

 

 43행~51행은 hash_value함수는 앞의 chained_hash.py에도 있지만 차이점은 rehash_node함수가 있는 것이다. 해시값을 구했을 때 충돌이 발생, 실패한 경우 다음 테이블을 주목하게 해주는 재해시 함수가 있다.

 

 53행~75행은 seearch_node함수는 키가 key인 버킷을 탐색한다. 버킷의 상태를 확인 후 값의 stat을 가지고 69행의 search함수에서 원소의 검색이 이뤄진다.

 

 

 

 

 

 

 

 

 

 

 

 77행~90행은 원소의 추가 함수로 빈 버킷이 나올 때까지 재해시를 반복하여(+1씩 옆으로 이동) 수행되므로 선형 탐사법(linear probing)이라고도 합니다.

 

 94행~101행은 삭제 함수이지만 한 가지 주의해야 할 점이 있습니다. 5를 삭제한다 가정했을 때 인덱스가 5인 버킷을 비우면 될 것 같지만 실제로 그렇지 않습니다. 해시값이 같은 값인 18을 검색할 때 해시값이 5인 데이터는 존재하지 않는다고 착각하여 검색에 실패할 수 있기 때문입니다. 그래서 각 값의 상태를 (1. 데이터가 저장되어 있음 2. 비어있음 3. 삭제 완료) 3가지로 구분하여 수행됩니다.

 

 104~113행도 마찬가지로 3가지 상태로 분류되어 Bucket안의 값들이 출력됩니다.