[Python] 딕셔너리(dict)와 리스트(list)의 메모리 점유율 차이

 

dict는 python 프로그래밍에서 가장 많이 사용되는 복합자료형 중 하나입니다.

 

dict의 경우, 입력과 조회에서 평균 시간복잡도 O(1)을 차지하므로,

 

다양한 부분에서 빠른 작업을 해낼 수 있다는 장점이 있습니다.

dictionary는 그럼 단점이 없을까요?

모든 자료구조가 각각의 쓰임이 있듯, 딕셔너리도 모든 작업에서 만능인 것은 아닙니다.

 

다른 복잡 자료형들과 비교했을 때의 단점들은 다음과 같습니다.

임의의 인덱스 접근 불가

list의 경우, list[0], list[5:], list[1:-3] 등, 다양한 index 접근이 가능합니다.

 

증가하는 정수형의 인덱스를 갖고 있기 때문이죠.

 

하지만 key : value로 매핑되는 딕셔너리의 특성상, 이러한 임의, 범위 접근은 사실상 불가능합니다.

 

임의, 범위 접근이 필요할 때는 keys() 메서드를 통해 key 배열을 만들어서 접근해야 합니다.

메모리 사용률 차이

이번 포스팅의 주제이기도 한, 메모리 사용률의 차이입니다.

이는 어디까지나 알고리즘 문제 풀이에 활용하는 경우에 한한 것입니다.
실제 프로그램 개발에서 자료구조의 선택은 다양한 요인을 따져야 합니다.

백준 1620 - 나는야 포켓몬 마스터 이다솜 문제로 알아보자

해당 문제는 N개의 포켓몬 이름을 받은 뒤, M개의 질의가 들어오는데,

 

질의가 자연수일 경우 해당 순서의 포켓몬 이름을,

 

질의가 포켓몬 이름일 경우 해당 순서를 출력하는 문제입니다.

 

python으로 풀게 될 경우, 일반적으로 dict를 활용하도록 유도된 문제입니다.

 

두 가지 방법이 있는데,

pokemon = {}
for i in range(1, N+1)
    name = input()
    pokemon[name] = i
    pokemon[i] = name

 

위와 같이 딕셔너리 하나에 {이름:인덱스}와 {인덱스:이름}의 모든 경우 저장하는 것이고,

pokemon = {}
for i in range(1, N+1)
    pokemon[input()] = i

index_list = [0] + list(pokemon.keys()) # 인덱스가 0이 아닌 1부터 주어지므로

 

위와 같이 {이름:인덱스}의 dictionary를 만들고, list로 포켓몬 도감을 또 하나 만드는 것입니다.

 

Python의 dict형태는 입력순서가 보전되므로, keys() 메서드를 활용해 list를 만들어도 순서가 유지됩니다.

 

또한 리스트에 대한 임의 인덱스 접근(list[n])의 경우, 시간 복잡도가 고정 O(1)이므로 딕셔너리와 거의 같습니다.

 

두 번째 방법을 쓰는 이유는 메모리를 적게 쓰고, 빠를 수도 있기 때문입니다.

 

백준의 입력 예시를 넣은 뒤, sys.getsizeof(pokemon)으로 확인할 경우,

 

첫 번째 방법의 pokemon dict는 총 2264바이트를 점유하고 있고,

 

두 번째 방법의 pokemon dict는 832바이트를, index_list는 272바이트를 점유하여,

 

총 1104바이트를 점유하고 있는 것을 확인할 수 있습니다.

이는 내부 객체들의 값을 모두 더한 게 아니라, 해당 복합 자료형의 메모리만 계산한 것입니다!

 

첫 번째 방법 두 번째 방법에 비해 거의 두 배의 메모리를 점유하고 있는 것이죠.

 

두 방법을 모두 활용해 문제를 해결할 경우, 각각 풀이의 메모리 점유는 다음과 같습니다.

1. dict 안에 인덱스와 네임 키를 모두 넣은 경우

2.dict 네임 키, index list 따로 생성한 경우

 

백준에서 Python 런타임 환경은 약 31100kb를 점유하고 있으므로,

 

1번 방법은 26000kb 가량의 메모리를 사용했고,

 

2번 방법은 16000kb 가량의 메모리를 사용하고 있다고 할 수 있겠습니다.

 

딕셔너리는 키와 값의 조합을 따로 저장하며, 해시 테이블도 갖고 있기 때문에

 

점유하는 메모리가 리스트보단 클 수밖에 없습니다.

 

약 1.6배의 메모리 차이를 보이며, 풀이속도에서도 어느정도 유의미한 차이가 있었습니다.

 

딕셔너리의 경우, 키를 통한 접근에 평균 O(1)의 시간 복잡도를 가진다고 하는데,

 

사실 해시 함수 수행과 해시 충돌 문제로 인해 실제로는 그보다 조금 더 높을 수 있기 때문입니다.

정리

대부분의 알고리즘 문제 풀이에서는 사실 메모리 점유율보단 실행속도를 훨씬 우선시 하기 때문에

 

메모리 점유율은 딱히 고려의 대상이 되지 않는 편입니다.(물론 극단적인 문제가 분명 존재하긴 하지만)

 

다만, 딕셔너리를 사용한다고 하더라도 입력 순서를 지켜준다는 특성을 활용하면

 

실행 속도도 줄이고 메모리 점유율도 낮출 수 있는 방법을 찾을 수 있을 것이라 생각합니다!