[python] 딕셔너리와 리스트 형태의 메모리 점유율 차이

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

dict와 list는 python 프로그래밍에서 가장 많이 사용되는 복합자료형일 것이다.

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

알고리즘 문제를 풀 때 가능하다면 list대신 dict를 활용해 시간복잡도를 줄일 수 있다.

dictionary는 그럼 단점이 없는 자료형인가?

이는 어디까지나 python의 list 형과 비교했을 때의 단점인데,

사실 두 자료형은 엄밀히 말해서 쓰여야 하는 때가 다르므로 단점이라 말할 수는 없다.

어디까지나 알고리즘을 풀 때, list 대신 dict를 썼을 때의 문제를 얘기하는 것이다.

임의의 인덱스 접근 불가

list 형태는 list[0], list[5:], list[1:-3] 등, 다양한 index 접근이 가능하다.

특정 값의 위치를 찾고 싶으면, list.index(‘value’)로 확인할 수 있다. (이 경우, O(index of value)가 된다.)

dict 형태는 기본적으로는 불가능하다.

다만, Python에서는 dict 타입에 값을 입력할 때 입력 순서가 유지되므로 이를 활용해 임의 인덱스 접근을 흉내낼 수 있다.

dictionary = {'c':1, 'b': 2, 'a': 3,}

print(dictionary.items())
print(dictionary.keys())
print(dictionary.values())

>>>

dict_items([('c', 1), ('b', 2), ('a', 3)])
dict_keys(['c', 'b', 'a'])
dict_values([1, 2, 3])

위와 같이, dict형태는 값을 입력한 순서를 유지한 채로 list 또는 tuple형태로 변환이 가능하다.

인덱스 접근이 필요한 경우, 위와 같은 방법으로 list를 변환하여 쓸 수 있는 것이다.

이는 python 3.7에서 값의 입력 순서 보전이 공식적으로 확정된 것이므로, 이전 버전의 경우 불가능할 수도 있다.

메모리 사용률 차이

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

이는 어디까지나 알고리즘 문제 풀이에 활용하는 경우에 한한 것이다. 당연하게도 실제 프로그래밍에선 해당 타입들을 적재적소에 활용하는 능력이 반드시 필요하다!

백준 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배의 메모리 차이를 보이며, 풀이속도에서도 어느정도 유의미한 차이가 있었다.

속도 차이는 값을 딕셔너리에 넣는 대신, keys() 메서드를 통해 한번에 리스트를 생성한 것 때문인듯 하다.

정리

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

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

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

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