Python 자료구조

1. Introduction

Python에서 주로 사용되는 자료구조는 List, Tuple, Set, Dictionary 4종류가 있다. Python은 List를 배열처럼 취급하기 때문에 아이템을 검색하는 데 걸리는 시간은 선형적(Linear)으로 증가한다. 따라서, 용량이 큰 데이터를 저장하기에는 효율성이 떨어진다. Tuple은 List와 달리 변형이 불가능(Immutable)한 리스트로, 검색하는 데 걸리는 시간은 List와 동일하게 데이터 양과 비례하게 증가한다. Set은 List와 Tuple과 달리 순서가 없으며, 중복되는 아이템을 저장할 수 없는 특징이 있어 조회 업무 등에서 사용된다. Dictionary는 키(Key)를 값(Value)에 매핑한다. 같은 Dictionary에 포함된 Key들은 서로 다른 Data Type에 속할 수 있으며, value에 대한 Data Type도 제한은 없다. 여러 Tuple이 포함된 List에서도 Dictionary를 만들 수 있기 때문에 유용하다. list1 = [('key1', 'value1'), ('key2', 'value2'), ('key3', 'value3')]를 선언한 후, dict(list1)으로 List를 Dictionary로 변환할 수 있다는 의미다. 이에 대한 내용을 아래에서 코드를 활용해 간단히 설명하려 한다.

 

---

2. Example

1) List와 Set의 속도 비교

다음은 같은 크기의 List와 Set을 설정한 후, 특정 아이템을 찾는 데 걸리는 시간을 time 모듈을 통해 비교한 것이다.

import time

# list 내의 item 찾는 시간 측정
list1 = [str(i) for i in range(1000000)]
time1 = time.time()
'item' in list1
time2 = time.time()

# set 내의 item 찾는 시간 측정
set1 = set(list1)
time3 = time.time()
'item' in set1
time4 = time.time()

print(time2 - time1) # list
print(time4 - time3) # set

사용자의 환경에 따라 속도 차이가 발생할 수 있지만, List보다 Set에서 찾고자 하는 아이템을 훨씬 더 빨리 찾을 수 있는 것은 분명하다.

 

2) List를 Dictionary로 변환

List를 Dictionary로 만드는 방법은 2가지가 있다. 우선, enumerate를 사용해서 Key 값이 0부터 지정되는 것이다.

다른 방법은 사용할 Key 값을 지정한 후에 zip을 사용하는 것이다.

 

3. 시간 복잡도

시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력한 함수의 관계로, Python 자료구조에 대한 시간 복잡도는 다음과 같다.

List	Tuple	Set	Dictionary
O(n)	O(n)	O(logn)	O(logn)

 

이처럼 자료구조의 특성이 다르기 때문에, 데이터 Type과 Volume에 따라 적합한 자료구조를 선택할 필요가 있다.