[파이썬] DAY11 검색

검색

탐색 키: 자료를 구별하여 인식할 수 있는 키

삽입 / 삭제 작업에서의 검색: 원소를 삽입하거나 삭제할 위치를 찾기 위해 검색

 

1. 수행 위치에 따른 분류

내부 검색: 메모리에 있는 자료에 대해 검색 수행

외부 검색: 보조기억장치에 있는 자료에 대해 검색 수행

 

 

2. 검색 방식에 따른 분류

1) 비교 검색

검색 대상의 키를 비교하여 검색하는 방법

순차 검색, 이진검색, 트리 검색

 

2) 계산 검색★ (도서관의 책 위치 찾는 방식)

계수적인 성질을 이용한 계산으로 검색 하는 방법

값을 입력하자마자 계산값을 준다.

해싱 (가장 중요)

 

 

 

네이버 해싱 테이블 손 코딩으로 면접 본다.

 

자료 구조의 형태(큐, 스택 등등)와 자료의 배열 상태(정렬 되었느냐 안되었느냐)에 따라 최적의 검색 방법 선택

 

 

1. 순차 검색 = 선형 검색

일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법

하지만 자료가 많은 경우 비효율적이다. 즉 검색이 실패했을 때 비효율적이다. 

자료의 배열 상태에 따라 검색의 실패를 판단하는 방법이 달라진다. 즉 종료의 시점이 달라진다.

정렬되지 않은 데이터는 끝까지 읽어야 하지만

정렬되어 있는 데이터는 다음 번호가 나올 때까지 읽으면 데이터 검색의 실패를 판단할 수 있다.

좀 더 시간을 단축하기 위해

색인 순차 검색 -> 과학 분야 수학 분야 국어 분야 책꽂이 중에 수학 분야부터 시작

 

           ↓걸리는 시간 보완

1) 색인 순차 검색(순차 검색을 보완한 선형 검색)

정렬된 데이터에서만 사용할 수 있다.

정렬된 자료에서 인덱스 테이블을 추가로 사용한다.

자료가 저장되어있는 배열의 크기가 n 이고

인덱스 테이블의 크기는 m

배열에서 n/m 간격으로 떨어져있는 원소와 그의 인덱스를 인덱스 테이블에 저장

1-30 31-60 61-90 ... 이런 식으로 나눠 42를 찾는다면 31부터 시작하여 시간을 단축한다.

인덱스 테이블이 크면 각각의 데이터 범주가 작아지고

인덱스 테이블이 작으면 각각의 데이터 범주가 넓어진다.

밸런스 맞게 사용해야 한다.

 

시간 복잡도 : O(m+n/m)

 

---

 

2. 이진 검색

자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색 위치를 결정한다.

정렬된 데이터에서만 사용할 수 있다.

약간 이진 탐색 트리와 비슷하지만 루트도 없고 ??잉? 여튼 달라

찾는 키 값 > 원소의 키 값 : 오른쪽 부분에 대해 검색 실행

 

---

3. 해시

산술 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식

키값 -> 해싱 함수 -> 해시 주소(버킷 주소) -> 해시 테이블

해시 주소에 항목이 있으면 검색 성공, 없으면 검색 실패

 

1. 용어 정리

충돌

서로 다른 키 값에 대해 해시 주소가 같은 경우 -> 비어있는 슬롯에 동거자 관계로 키 값 저장

동거자

같은 버킷에 저장된 다른 키 값들

오버플로우

버킷에 비어있는 슬롯이 더 이상 없는 상태

 

키 값 밀도

= 실제 사용 중인 키 값의 개수 / 사용 가능한 키 값의 개수

 

적재 밀도 = 실제 사용중인 키값의 개수 / 해시 테이블에 저장 가능한 전체 키 값의 개수 = 실제 사용중인 키값의 개수 / (버킷 개수 X 슬롯 개수)

 

키 값 밀도가 높을 수록 적재 밀도가 낮을 수록 좋다.

 

 

 

2. 해싱 함수

충돌, 오버 플로우를 결정하는 가장 중요한 요소

1) 해싱 함수의 조건

계산이 빠르도록 쉬워야 한다.

충돌이 적어야 한다.

해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.

 

2) 해싱 함수의 종류

(1) 중간 제곱 함수

주소 = 키 값을 제곱한 결과 값의 중간에 있는 적당한 비트

(2) 제산 함수

주소 = 키 %(mod) M

M은 적당한 크기의 소수를 사용한다.

(3) 승산 함수

주소(정수값) = (키 X 정해진 실수)의 소수점 이하 부분 X M

(4) 접지 함수

- 이동 접지 함수

각 분할 부분을 이동시켜서 오른쪽 끝자리가 일치하도록 맞추고 더하는 방법

그냥 가위로 잘라서 (3자리씩 잘라서) 다 더한 값

- 경계 접지 함수

경계를 접어서 한다.

그냥 가위로 자른 다음 번갈아가면서 더해서 다 더한 값

(5) 숫자 분석 함수

공통된 부분을 제거하고 나만의 특정 값을 해시 주소로 사용

-> 키가 유일하게 가지고 있는 부분만 가지고 해시로 만들겠다.

 

 

3. 오버플로우

1) 오버플로우 처리 방법

(1) 선형 개방 주소법 = 선형 조사법

빈 슬롯에 데이터를 넣어버린다.

나중에는 해시테이블에 비어있는 부분이 없어진다.

-> 지정된 장소에 데이터가 없으면 순차 탐색을 하면서 데이터를 찾는다.

검색하는데 시간이 걸리지만 오버플로우를 방지할 수 있다.

그러나 데이터의 실제 위치가 원래 지정된 주소에서 너무 많이 떨어져있으면 탐색에 비효율적이다. (충돌이 많이 발생)

탐색 실패 판단 방법 1. 회전해서 확인했을 때 돌아왔는데 데이터가 없을 때 2. 맨 마지막 위치까지 갔는데 데이터가 없을 때

체이닝으로 극복

(2) 체이닝

연결 자료 구조 이용

버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해 연결 리스트를 사용한다.

각 버킷에 대한 헤드노드를 1차원 배열로 만들어 각 값들을 삽입해서 넣는다.

 

 

코드 1

class LinearProbing: # 선형 개발 주소법
   def __init__(self,size):    
      self.M = size # 해시 테이블의 크기           
      self.a = [None]*size    
      self.d = [None]*size    
                    
   def hash(self,key): # 해싱 함수를 제산함수로 만들었다.     
      return key%self.M

   def put(self,key,data): # 데이터를 찾기 위해 key값을 쓴다. 
      initial_position = self.hash(key) # 주소 넣는다.
      i = initial_position # i는 주소
      j = 0 

      while True:
         if self.a[i] == None: # 버킷이 비어있으면
            self.a[i] = key # 키값를 넣은 리스트
            self.d[i] = data # 데이터 값을 넣은 리스트
            return

         if self.a[i] == key : # 동일한 키 값이 있을 때
            self.d[i] = data # 데이터 값은 갱신해준다.
            return
         j+=1
         i = (initial_position +j)%self.M # 못 들어가니 1인덱스 앞에 들어간다.
         if i == initial_position:
            break
   def get(self,key): # 검색 작업
      initial_position = self.hash(key)
      i = initial_position
      j = 1
      while self.a[i]!=None: # 해당 주소에 데이터가 없을 때
         if self.a[i] == key:
            return self.d[i]
         i = (initial_position + j) % self.M # 다음 칸으로 넘어간다.
         j+=1
         if i == initial_position:
            return None
        
      return None
    
    
   def print_table(self): # 위 동작들을 실행해보기 위한 출력문
      print('\n')
      for i in range(self.M):
         print(f'{i}', " ", end="")
      print('\n')
        
      for i in range(self.M):
         print(f'{self.a[i]}', " ", end="")
      print('\n')
        
      pass
lb = LinearProbing(10) # 10개의 값들
lb.put(1,'data1') # 1인덱스로 간다.
lb.put(2,'data2')
lb.put(11,'data11') # 1 -> 2 -> 3인덱스로 간다.

lb.put(4,'data4')
lb.put(5,'data5')
lb.put(6,'data6')
lb.put(7,'data7')
lb.put(8,'data8')
lb.put(9,'data9')


lb.put(21,'data21') # 마지막으로 남은 0인덱스에 들어간다.
lb.put(33,'dat33') # 오버플로우 발생

lb.print_table()

print(lb.get(1)) # 키값이 1이라는 곳에 들어있는 데이터를 가져온다.
print(lb.get(11)) # 키값이 11%10 = 1이라는 곳에 갔는데 없어서 한칸씩 이동하다가 3인덱스에서 data11을 찾아온다.
print(lb.get(21)) # 너무 비효율적이다 -> 연결 리스트를 이용한 체이닝 사용

코드 2

class Chaining:
    class Node:
        def __init__(self,key,data, link): 
            self.key = key
            self.data = data
            self.next = link # 링크 값도 추가한다.
        
    def __init__(self, size):
        self.a = [None]*size
        self.size = size
    
    def hash(self,key): # 해싱함수: 제산함수로 작동하게 해준다.
        return key%self.size
 
    def put(self,key,data): # 주소에 데이터 값을 넣어준다.
        i = self.hash(key)
        p = self.a[i]
        
        while p != None: # 공간이 없으면 만들어 준다.
            if key == p.key:  
                p.data = data
                return 
            p = p.next  
        

        self.a[i] = self.Node(key, data, self.a[i])
        
        
    def get(self,key): # 연결 리스트에 있는 데이터를 가져온다. None으로 각 리스트가 끝났음을 판단한다.
        index = self.hash(key)
        
        this_time_node = self.a[index]

        while this_time_node:
            if this_time_node.key == key:
                return this_time_node.data # 데이터를 찾았을 때 데이터를 가지고 나온다.

            this_time_node = this_time_node.next

        return None # 끝지점임을 보여준다.

    
    
    def print_table(self): 
        
        for index, first_node in enumerate(self.a):
            print(index," ", end ="")
            
            this_time_node = first_node
            
            while this_time_node:
                print(f"-> [ {this_time_node.key}, {this_time_node.data}] ", end="")
                
                this_time_node = this_time_node.next
        
            print('\n')

t = Chaining(13) # 해시테이블의 크기는 소수로 정한다.
# 마음대로 데이터 만든다.
t.put(55,'data55') # 55 % 13 = 3에 저장한다.
t.put(18,'data18')
t.put(35,'data35')
t.put(22,'data22')
t.put(63,'data63')
t.put(50,'data50')
t.put(37,'data37')
             
t.print_table()

result = t.get(50)
print(result)

순차이면 선형 개방 주소법으로 순차가 아니면 체이닝으로 처리한다.

 

다음주는 Numpy Thread 통신 등등 4일 간

 

open cv 이미지 처리 정도