[고성능파이썬] 사전(dictionary) 과 셋(set)

🔊 해당 포스팅은 고성능 파이썬 2판 책 서적을 읽고 개인적인 학습 목적 하에 작성된 글입니다. 포스팅에서 사용되는 자료들은 책의 내용을 참고하되 본인이 직접 재구성한 자료임을 알립니다.

 

출처 : 한빛출판네트워크

---

이번 포스팅에서는 파이썬의 자료구조 중 정렬되지 않은 데이터를 탐색하는 문제에 적합한 dictionary(이하 사전)과 set(이하 셋)에 대한 내용을 공부해보면서 알아두면 좋을 내용들에 대해 정리해보고자 한다.

1. 조회도 한 번에, 삽입도 한 번에!

셋과 사전은 특정 데이터를 고유하게 참조할 수 있는 별도 객체가 있는 상황에서 가장 이상적인 자료구조이다. 여기서 '고유하게 참조할 수 있는 별도 객체'란, 'key : value' 로 이루어진 자료구조 중 'key'에 해당하는 값이다. 이 key 라는 참조하는 객체는 일반적으로 문자열이지만 해시가 가능한 즉, hashable 한 어떤 타입이라도 상관없다. 

 

파이썬에서 특정 타입의 데이터가 hashable 여부를 판단하는 간단한 방법은 아래와 같다.

 

import typing

def is_hashable(*args):
    for a in args:
        print(a, type(a), '-> hashable:', isinstance(a, typing.Hashable))
        

int_data = 1000
float_data = 1000.1
string_data = '1000.1'
list_data = [1, 2, 3]
tuple_data = (1, 2, 3)

is_hashable(int_data, float_data, string_data, list_data, tuple_data)

 

위 코드를 실행하게 되면 알겠지만 위 코드에서 정의한 정수, 실수, 문자열, 튜플은 모두 hashable한 자료구조이지만 데이터 수정의 여지가 있는 리스트만 hashable한 자료구조가 아니다.

 

사전과 셋의 차이점이라고 한다면 데이터에 해당하는 값(value)가 없다는 점이다. 사전은 있고, 셋은 없다. 또한 셋은 유일한 key를 저장하는 자료구조이다. 그래서 집합 연산을 수행할 때 주로 사용된다. 물론 사전도 기존에 갖고 있는 key와 동일한 key를 갖는 데이터를 사전 자료구조에 넣으면 이후에 넣은 데이터가 덮어쓰기 된다.

 

이전 포스팅에서 정렬되지 않은 리스트와 튜플은 특정 데이터를 조회할 때 아무리 빨라도 $O(logn)$ 시간 복잡도가 걸린다고 배웠다. 하지만 사전과 셋은 특정 데이터(엄밀히 말하면 데이터의 index)를 조회할 때 $O(1)$ 시간 복잡도 밖에 걸리지 않는다. 또한 데이터 삽입의 경우 사전과 셋은 리스트, 튜플 때와 마찬가지로 $O(1)$ 시간 복잡도가 걸린다.

 

이렇게만 보면 사전과 셋이 장점만 있을 것 같지만, 사전과 셋은 상대적으로 메모리를 많이 사용한다. 그리고 방금 사전과 셋이 데이터를 조회/삽입할 경우 모두 시간복잡도 $O(1)$이 걸린다고 했지만, 엄밀히 말해서 이 속도는 사전과 셋이 사용하는 해시 함수에 전적으로 의존하게 된다. 만약 느린 해시 함수를 사용하는 사전과 셋이라면 데이터를 조회/삽입할 때 시간 복잡도 $O(1)$을 보장하지 못한다.

 

이제 이 해시 함수가 사전과 셋이랑 무슨 상관이 있는지 알아보도록 하자.

2. 사전과 셋의 동작 원리: 해시함수

사전과 셋은 해시 테이블이라는 것을 사용하기 때문에 데이터를 조회, 삽입하는 시간 복잡도가 모두 $O(1)$이다. 이 해시 테이블이란 무엇일까? 해시 테이블을 이해하기에 앞서 해시 함수라는 것부터 알아야 한다. 최근에 뜨거운 감자였던 비트코인, 블록체인 분야에 대해 조금이라도 관심있는 사람들은 해시 함수에 대해 들어본 적이 있을 것이다. 해시 함수는 간단하다. 입력을 넣으로 출력을 내뱉는 간단한 함수이다.

 

해쉬 함수는 결정론적이다

 

그러면 사전과 셋에서의 해쉬 함수는 어떤 것을 입,출력으로 받는 걸까? 입력은 임의의 key이고, 출력은 리스트의 index(색인)을 출력한다.

 

 

해시 테이블은 이러한 해시 함수를 효율적으로 활용한 것이다. 즉, 데이터의 key를 list의 색인 처럼 사용하도록 변환하는 작업을 해시 함수가 수행해주면 해시 테이블은 list와 같은 성능을 낸다. 그리고 해시함수와 리스트(list)는 나중에 검색을 하지 않고도 특정 데이터가 제대로 들어있는지 확인하는 용도로 사용한다.

 

방금 알아본 것처럼 해시 테이블은 전적으로 해시 함수의 성능에 의존한다. 따라서 해시 함수를 정의하는 부분은 자료구조의 성능을 좌우할 만큼 중요하다. 물론 파이썬에서는 대부분의 타입에 대해서 해시 함수를 제공하므로 예외 상황이 아니라면 직접 해시 함수를 작성할 일은 거의 없다. 그래서 해당 포스팅에서는 해시 함수를 활용하는 사전과 셋의 구체적인 동작 원리에 대해서는 스킵하고 넘어간다. 이에 대해 궁금한 분들은 원본 책을 참조하도록 하자.

 

이번 포스팅에서는 사용자 정의 클래스를 활용할 때, 해시 함수를 커스텀하게 조작하는 사례에 대해 알아보자. 먼저 이 사례가 필요한 경우에 대해 예시를 들어보자. 만약 아래와 같은 사용자 정의 클래스가 있다고 가정해보자.

 

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

 

위 클래스에 대해서 2개의 객체를 아래처럼 생성해보자.

 

p1 = Point(1, 1)
p2 = Point(1, 1)

 

그런데 위처럼 생성한 변수 p1 과 p2는 동일한 객체일까? 여기서 동일하다고 하는 것은 메모리 주소까지 동일한 객체인지를 의미한다. 동일한 객체인지 확인하기 위해 위 변수들은 셋 자료구조에 넣어보면 알게될 것이다.

 

p1 = Point(1, 1)
p2 = Point(1, 1)

temp = set([p1, p2])
print(temp) # {<__main__.Point object at 0x105d5e560>, <__main__.Point object at 0x10636eb60>}

 

출력을 보면 p1은 '0x105d5e560' 라는 메모리 주소를 p2는 '0x10636eb60' 라는 서로 다른 메모리 주소를 갖고 있고, 이에 따라 셋 자료구조에 담더라도 2개가 들어있음을 볼 수 있다. 만약에 이 2개의 객체가 서로 동일하다고 간주하도록 해주려면 어떻게 해야할까?

 

이를 구현하기 위해서 우리는 두 개의 객체가 서로 동일하다라는 것을 검증하는 조건을 메모리 주소가 아닌 실제 내용(데이터)을 기반으로 하는 사용자 정의 함수를 작성하면 된다. 여기서 작성한다는 사용자 정의 함수는 다음과 같다. 사용자 정의 클래스에도 기본 해시 함수와 비교 함수가 존재하는데, 기본 해시 함수인 __hash__ 라는 매직 메서드는 메모리 주소를 반환하는 내장 메소드인 id()를 이용해서 특정 객체의 메모리 주소를 반환한다. 그리고 비교 함수인 __eq__ 매직 메서드는 객체의 메모리 위치 여러 개를 서로 산술 비교한다.(참고로 Python2.x 버전대에서는 __cmp__ 매직 메서드가 사용되었지만 Python3.x 버전대로 오면서 deprecated 되었다)

 

따라서 __hash__, __eq__ 매직 메서드 이 2개를 아래처럼 오버라이딩 해보자.

 

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other: Point):
        return self.x == other.x and self.y == other.y

 

먼저 해시 함수에서 return 하는 값을 객체의 데이터 x, y를 하나로 묶어 해시 함수에 넣어주도록 하자. 이는 Point 라는 객체를 hashable한 객체로 만들어 주는 것이다. 그리고 난 뒤 두 개의 객체가 동일한지 여부를 검증하는 비교 연산자인 __eq__ 매직 메서드를 재정의하준다. 해당 메서드가 구현된 로직을 보면 객체의 속성 값인 x, y가 모두 동일하면 동일하다고 간주하는 것을 볼 수 있다.

 

이렇게 구현된 Point 객체를 새롭게 2개 생성하고, 셋 자료 구조에 담아보자.

 

p1 = Point(1, 1)
p2 = Point(1, 1)

temp = set([p1, p2])
print(temp) # {<__main__.Point object at 0x10636f250>}

 

그러면 이제 2개의 객체가 동일하다는 것이 간주되어 셋 자료구조에는 메모리 주소가 '0x10636f250'인 객체 하나 밖에 존재하지 않는 것을 볼 수 있다.

 

이렇게 해시 함수를 새롭게 정의하는 것은 새롭게 정의한 해시 함수의 엔트로피를 고려해야 한다. 여기서 엔트로피란, 해시 함수가 얼마나 균일한 분포로 해시값을 만들어내는지를 의미한다. 여기서는 해시 함수가 얼마나 균일한 분포로 list의 index를 생성하는지를 의미한다. 이 엔트로피가 최대인 것은 해시값이 균일한 분포이며 이는 곧 해시 함수가 최소 충돌을 보장하는 것이며 완전 해시함수를 의미한다. 이러한 해시 함수로 구현된 사전과 셋 자료구조는 매우 좋은 성능을 보인다.

3. 사전(dictionary) 탐색이 이루어지는 곳: 네임스페이스

지금까지 배운 것처럼 사전은 데이터를 조회(탐색)할 때 걸리는 시간이 매우 빠른 것을 알 수 있었다. 하지만 아무리 빠르다고 해도 불필요한 탐색은 코드 실행 속도를 떨어뜨리는 원인이 된다. 이러한 과도한 사전 탐색으로 인해 문제가 발생할 수 있는 부분이 바로 파이썬의 네임 스페이스 관리이다.

 

먼저 파이썬의 네임스페이스에 대해서 알아야 한다. 파이썬에서는 변수, 함수, 모듈이 사용될 때 그 객체를 어디서 찾아 불러올지 결정하는 계층이 있다. 이를 바로 네임스페이스라고 한다. 파이썬은 크게 아래와 같은 순서로 객체를 찾게 된다.

 

파이썬이 변수, 함수, 모듈을 찾기 위해 탐색하는 공간의 순서

 

파이썬은 가장 먼저 모든 지역 변수를 담은 지역 네임스페이스의 locals() 라는 배열에서 찾기 시작한다. 이 단계에서는 유일하게 사전 탐색을 수행하지 않는 부분이다. 이 locals() 배열은 함수를 호출 할 때 만들어지는 스택 프레임이라는 자료구조 안의 지역 변수 영역을 의미한다. 함수는 자신의 지역 변수에 접근할 때는 스택 프레임 내의 지역 변수 영역에 어떤 데이터가 몇 번째에 있는지 index 값을 미리 알고 있는 상태이기 때문에 사전 탐색을 하지 않고도 곧바로 접근할 수 있다.

 

다음으로 접근하는 곳은 전역 네임스페이스의 globals() 자료구조이다. 이 자료구조는 사전으로 구현되어 있기 때문에 사전 탐색을 수행한다.

 

그래도 없다면 마지막으로 접근하는 곳은 __builtin__ 라는 모듈 객체에서 찾는다. __builtin__ 은 모듈 객체이기 때문에 해당 모듈 내부의 locals() 사전 자료구조를 탐색한다. 참고로 가장 첫번째로 탐색하는 지역 네임스페이스 내의 locals() 때는 단순히 index로 접근하기 때문에 매우 빨랐지만, __builtin__ 모듈 객체의 locals() 에서는 사전이기 때문에 이름으로 탐색하기 때문에 상대적으로 속도가 느리다.

 

위처럼 탐색 순서와 각 단계에서의 특징을 머릿속에 두고 특정 함수 또는 모듈을 임포트하는 아래 예시 코드를 통해서 어떻게 작성된 코드가 가장 빠른 성능을 보장하는지 비교해보도록 하자.

 

import math

def test1(x):
    res = 1
    for _ in range(1000):
        res += math.sin(x)
    return res

 

이 방법에서는 사전 탐색을 2번 진행한 코드이다. 가장 먼저 math 라는 모듈을 로드할 때 1번, 그리고 math 라는 모듈 안에서 sin 함수를 찾기 위해 1번 총 2번을 진행한다.

 

다른 스타일의 코드를 살펴보자.

 

from math import sin

def test2(x):
    res = 1
    for _ in range(1000):
        res += sin(x)
    return res

 

이번엔 명시적으로 sin 함수를 임포트 했다. 이럴 경우, sin 이라는 함수는 전역 네임스페이스에서 접근이 가능해진다. 바로 직전의 코드보다 사전 탐색을 한 번 스킵할 수 있다. 이러한 스타일의 코드는 속도를 빠르게 해줄 뿐만 아니라 함수를 명시하여 어떤 기능이 필요한지 전달하게 되어 코드 가독성도 높힐 수 있다. 물론 이 코드도 아직까지는 전역 네임스페이스에서 sin 이라는 함수를 찾기 위해 사전 탐색을 한 번은 진행해야 한다.

 

마지막으로 아래 스타일의 코드를 살펴보자.

 

import math

def test3(x, func=math.sin):
    res = 1
    for _ in range(1000):
        res += func(x)
    return res

 

이번에는 math 모듈을 임포트하긴 했지만 test3 이라는 함수의 func 이라는 argument에 기본값을 math 모듈의 sin 함수를 지정했다. 이 경우도 math 모듈 안에서 sin 함수를 찾는 사전 탐색이 한 번 진행되지만, test3가 최초로 호출 될 때만 찾는다. 왜냐하면 test3 이라는 함수가 정의되고 나면 sin 함수에 대한 참조는 함수 정의 시 기본값으로 지정되어 있기 때문에 지역 변수에 저장되고 이는 가장 빠르고 가장 먼저 탐색하는 지역 네임스페이스의 locals() 배열에서 접근이 가능하기 때문이다. 해당 부분으로 인해 직전 코드보다는 좀 더 빠르게 동작한다.

 

그런데 여기서 알아두어야 할 점은 test3 함수가 정의된 스타일의 코드는 사실 pythonic한 코드는 아니다. 물론 이렇게 추가 사전 탐색을 스킵하도록 개선함으로써 성능 저하를 막을 수 있긴 하지만 보통 특정 함수를 엄청나게 많이 호출할 때에나 추가 사전 탐색으로 인한 성능 저하를 발견할 수 있다는 것이다. 따라서 해당 함수 호출을 많이 하지 않는 상황이라면 pythonic 한 코드를 유지하 test2 함수를 정의한 스타일의 코드가 더 적절할 수 있다.

---

이렇게 해서 파이썬의 자료구조인 사전과 셋, 그리고 더 나아가 사전 탐색을 수행하는 파이썬의 네임스페이스에 대해서도 추가로 알아보았다. 다음 포스팅에서는 메모리에 전체 데이터를 미리 저장하지 않고도 데이터 순서를 제어할 수 있는 제네레이터에 대해 알아보자.