자료구조

Data_structure/Simple Unsorted_map Implementation/해쉬 자료구조 기초)

swdream 2019. 11. 4. 23:58
반응형

어떤영상에서 봤던가, 해쉬는 프로그래머의 기본기라고... 그래서 우선 map이라는 자료구조를 파이썬을 통해 정의해보고자 합니다.{ key , value } pair 로 저장하는 자료구조를 우선 map이라고 해봅시다. (뭐 map 자료구조를 사용하면 시간복잡도가 O(1)이니 이런 것들은 우선 나중에 생각합시다.) 우선, 아래와 같은 정의만 이용해서 python을 통한 simple unsorted map 을 구현합니다. 

I tried to define the basic hash data structure because Hash is the Basic Skill that Programmer should have. Let the data structure, map that save a {key, value} pair. Using the Definitions Below, I can Implement the Simple Unsorted_map 

  • key, value 쌍으로 저장하는 자료구조 / Data Structure that saved as {key, value} pair
  • 한 키에는 하나의 값이 있어야 합니다. / one Value per one Key
  • 따라서, 키 값이 같다면, 그것은 동치입니다. /So, if key is the same, that means these are equivalent.

단, key를 찾거나, 새로운 key, value 쌍을 저장할 때의 Time Complexity = O(n)입니다. 

When You find a key or you save a new pair of {key, value}, its Time Complexity is O(n).

 

먼저, Base Class 인 Mutable Mapping을 상속하며, Map 자료구조를 정의할 MapBase Class를 만듭니다. Nested Class로 _Item이라는 class를 정의합니다. 이 아이템이 우리가 추후에 저장하고 생성하고 지우기도 하는 Map에 저장될 데이터 클래스입니다. 왜 Nested Class로 _Item 을 정의하는지를 생각해보면, 아래와 같다고 합니다. 

[why use nested class?]

  1. It is a way of logically grouping classes that are only used in one place.

  2. It increases encapsulation.

  3. Nested classes can lead to more readable and maintainable code.

  4. Child to parent class connection is simpler as it visually illustrates the variables and methods of each class

아마 종합해보건데, Encapsulation을 강화시킨다는 것은 _Item 으로, 해쉬에 담길 아이템을 생성할 때, 클래스 내에서도 또 _Item(k,v)를 통해  아이템을 생성해줘야 하므로 캡슐화를 강화시키는 효과가 있고, _Item의 자료형을 변형하는 상황이 올 때, _Item을 사용하는 클래스 내 타 method에서 더욱 의존성을 _Item으로부터 분리시킬 수 있다. 클래스간은 최대한 의존성을 줄이는 것이 유지보수에 바람직하다. 아마 이래서 Nested Class를 사용하지 않았나 싶다.  

<mapbase.py>

from collections import MutableMapping
class MapBase(MutableMapping):

    class _Item:

        __slots__ = '_key', '_value'

        def __init__(self, k, v):
            self._key = k
            self._value = v

        def __eq__(self, other):
            return self._key == other._key

        def __ne__(self, other):
            return not (self == other)

        def __It__(self, other):
            return self._key < other._key

__aaa__, 즉 double Underscore 함수는 매직함수라고 파이썬에서 불린다. 가장 상위의 클래스에서 Built In 으로 정의된 함수를 의미하며, 마치 수학으로 치면 공리와 같이 사전에 약속된 함수라고 생각하면된다. 그럼에도 여기서 double Underscore함수를 다시 써서 굳이 정의해주는 이유는 기존에 정의된 함수에 overriding하여, 좀 더 우리가 구현하고자 하는 해쉬 자료구조에 맞게 기본 함수를 커스터마이징하기 위함이다. 

자, 그럼 여기까지 MutableMapping 을 BaseClass로 갖고, 이를 subclass 로 갖는 MapBase를 알맞게 정의했다. Class 관계를 보면, BaseClass < MutableMapping 이겠다. 다음으로는, hash 자료형이 읽고 쓰고 넣고 길이 등을 구하기 위한, 실질적인 해쉬의 사용을 위한UnsortedTableMap 클래스를 작성해보자. 구조로는, UnsortedTableMap < BaseClass < MutableMapping 이다. 아래 보면, __setitem__이라는 magic method는 주로 list 에서 쓰는 list a[2] = 3 이라고 하면,  idx 값과 그에 따른 value값으로 저장을 하게되는 magic function 인데, 이를 key, value 값으로 저장하며, 사전에 정의된 _table을 순회한다. Nested Class나 내부적으로 쓰는 (private Interface) 데이터나 클래스 등에 파이썬은 single Underscore 로 시작하며 변수를 명명한다. 딴 얘기지만, 들여쓰기같은거 조심하자. (아래 주석에도 있음)

<unsortedtablemap.py>

from mapbase import MapBase

class UnsortedTableMap(MapBase):

    def __init__(self):
        ''''Create an Empty map when Initialize'''
        self._table = []

    def __getitem__(self, k):
        ''' Return value associated with key k (raise Key Error if Not Found) '''
        for item in self._table:
            if k == item._key:
                return item._value        
        raise KeyError('Key Error: ' + repr(k))

    def __setitem__(self, k, v):
        #Assign value v to key k, overwriting existing value if present. 
        for item in self._table:
            if k == item._key:
                item._value = v
                return
            #self._table.append(self._Item(k,v)) -> 들여쓰기 조심 
            # In case that did not find match for key
        self._table.append(self._Item(k,v))

    def __delitem__(self, k):
        '''Remove item associated with key k (Raise Key Error if not found)'''
        for j in range(len(self._table)):
            if k == self._table[j]._key:
                self._table.pop(j)
                return 
        raise KeyError('Key Error: '+repr(k))

    def __len__(self):
        '''Return Number of items in the map'''
        return len(self._table)

    def __iter__(self):
        '''Generate iteration of the map's keys.'''
        for item in self._table:
            yield item._key

 

최종적으로는 이를 다 끌어모아서 마침내 마지막 클래스로 오브젝트를 만들어 함수를 실행하는 코드이다. 

<unsortedmap_main.py>

from unsortedmap import UnsortedTableMap

def main():
    map = UnsortedTableMap()

    map[3]=2
    map[4]=100
    print(len(map))
    print(map[4])
    
if __name__ == '__main__':
    main()

자, 출력 결과는 뭘까? 

반응형