Distinct Value Search(단순탐색)

 

이번 포스팅은 주어진 Data에서 Distinct Value로 구성된 List를 구하는 알고리즘 입니다.

 

현재 가장 유명한 방법은 Hesh Map을 사용하는 방법이지만, 해당 방법 이전에

 

Brutal Algorithm 방법으로 구하는 Distinct Value를 구하는 방법에 대해서 알아보겠습니다.

 

알고리즘의 추상화된 동작 이미지

해당 알고리즘은.

1. Random List에서 N번째 원소를 Pick한다

2. N번째 원소가 Distinct List에 있는지 확인한다.

3. 있으면 Pass하고, 없으면 Distinct List에 추가한다.

4. 모든 Random List의 원소를 확인할 때까지 1~3반복

알고리즘이 너무 직관적이라, 특별히 설명이 필요 없어보입니다 ^_^;;

 

해당 알고리즘은 n개의 Element에 대해서, k번(distinct list의 원소의 개수)만큼의 비교가 필요합니다.

 

때문에 Distinct value가 매우 작으면 O(n)에 근접한 성능을 보이지만

 

대부분이 겹치는 값이 없는 경우 최악의성능 O(n^2)의 시간복잡도를 보여주게 됩니다. 

 

Python으로 빠르게 구현한 Distinct Value List찾기 단순 버전입니다 :)

class distinct:
    def __init__(self, DT_list):
        self.data = DT_list
        #distinct value를 저장 할 list
        self.result = []
    
    def cal(self):
        #원본 Random List에서 순서대로 Element를 Pick합니다.
        for i in self.data:
            #distinct list에 Value가 있는지 확인하기 위한 변수
            valid = 0
            for j in self.result:
                #한번이라도 같은 값을 확인하면 Valid를 증가시켜
                #중복여부를 확인 할 수 있게 합니다.
                if i == j:
                    valid = valid + 1
            #중복이 없었다면 distinct list에 해당 value를 추가합니다.
            if valid == 0:
                self.result.append(i)
        return self.result


import random
test_data = [random.randint(0,20) for i in range(10000)]
temp = distinct(test_data)
#distinct list를 반환받습니다.
temp_result = temp.cal()
#Python 내장 정렬알고리즘을 사용해서 실제 Distinct Value만 포함되었는지 확인
temp_result.sort()