Distinct Value Search(Hash탐색)

이전 포스팅에서 단순한 방법으로 Distinct Value List를 구하는 방법에 대해서 알아보았습니다.

 

이번에는 보다 빠른 속도로 Distinct Value List를 구하는 방법으로, Hash 탐색을 이용하는 방법입니다.

 

Hash 탐색방법은 이름 에서 알 수 있듯, Hash 알고리즘을 활용합니다.

teus-kiwiee.tistory.com/32?category=913862

Hash

Hash탐색을 활용 할 경우, Distinct Value의 존재 여부를 확인하는 범위를 축소시킬 수 있습니다.

단순 알고리즘과 Hash 알고리즘의 차이점 추상화 이미지

위 그림을 살펴보면, 단순 알고리즘의 경우 Distinct List전체와 N번째 Element를 비교해야 합니다.

 

하지만 Hash 알고리즘을 사용할 경우 해당 Hash_index에 해당하는 value들만 비교하면 됩니다!

 

Hash Index가 한곳에 모이는 Clustering이 없다면,

 

N번째 Element가 비교해야할 Element의 개수 k는 1에 근접할 것이고

 

점근성능 O(n)의 시간복잡도를 보여주는 알고리즘이 되겠습니다.

 

경우의수를 줄여서 보다 빠른 수행시간을 보장한다고 할 수 있습니다 :)

 

Python으로 구현된 Distinct Value 찾기 Hash 버전입니다.

#Hash Table에 사용될 Node 미리 선언(연결List방식)
class node:
    def __init__(self, value, n_node):
        self.value = value
        self.next = n_node

class distinct_h:
    def __init__(self, DT_list):        
        self.data = DT_list
        #hash code를 index로 해서 element를 삽입할 hash table을 선언합니다.
        self.hash_table = [node(None,None)]*100
        
    #중간제곱법을 이용한 Hash의 구현 
    def h_func(self, element):
        n = 0
        #element의 자리수 확인
        while True:
            if pow(10,n)>element:
                break
            else:
                n = n+1        
        #element의 제곱값에서 자리수 기존 자리수의 위치를 확인
        h_code = divmod((element * element),pow(10,n))[0]
        #기존 자리수에서 2개의 숫자를 확인(0~99)
        h_code = divmod(h_code,len(self.hash_table))[1]
        return h_code
    
    def cal(self):
        #Distinct Value를 저장할 List를 선언
        distinct_list = []
        #element를 hash table에 삽입
        for i in self.data:
            #Hash Table에 중복 Element가 있는지 여부를 확인하기 위한 변수
            valid = 0
            #연결List를 사용해서 구현한 Hash Table
            start_node = self.hash_table[self.h_func(i)]
            while True:            
                #해당 Node에 Element가 있는지 확인합니다.
                #없으면 해당 Node에 Element를 삽입하고 알고리즘을 종료
                if start_node.value == None:
                    start_node.value = i
                    #중복값이 없었다면 Distinct Value이므로
                    #Distinct List에 해당 Value를 추가합니다.
                    if valid == 0:
                        distinct_list.append(i)
                    start_node.next = node(None,None)
                    break
                #해당 Node가 이미 사용중이면 해당 Node에서 연결된 Node로 이동합니다.
                elif start_node.value != None:                
                    #해당 Hash Index의 연결리스트에 중복값이 있으면
                    #valid값을 갱신해줍니다.
                    if start_node.value == i:
                        valid = valid +1
                    start_node = start_node.next
        return distinct_list
                
import random
test_data = [random.randint(0,100) for i in range(10000)]
test= distinct_h(test_data)
#distinct list를 반환받습니다.
result = test.cal()
#Python 내장 정렬알고리즘을 사용해서 실제 Distinct Value만 포함되었는지 확인
result.sort()