[파이썬] set에 대하여(리스트와 시간비교)

알고리즘 문제를 풀다가 다른 분께서 set을 이용하여 푸신 풀이를 보고 set의 특징에 대하여 적어볼까 합니다.

 

기본적으로 set이라 하면 중복이 없다고만 알고 지나쳤는데 그게 아니더라고요

공식적으로 unordered collection이라고 되어있는데 그게 무슨 뜻인지 봅시다

 

list와 비교해서 설명드리겠습니다.

list에 삽입할 때는 원하는 위치에 넣던지, 맨 뒤에 append해주게 되죠 우리는 그 위치를 알 수도 있고 원하는 구간을 잘라서 활용할 수도 있죠

 

list = [5,2,8,3,9]
list.append(1)
print(list)
print(list[2])

#[5, 2, 8, 3, 9, 1]
#8

이런식으로 말이죠

 

set에선 어떨까요?

set = {5,2,8}
print(set)
print(set[1])

#{8, 2, 5}
#TypeError: 'set' object is not subscriptable

에러가 발생합니다.

앞서 말했다시피 set은 순서가 없기에 인덱싱할수도, 슬라이스할 수도 없습니다.

그렇다면 인덱싱없이 어떻게 쓸 수 있을까요?

 

리스트와 비교해서 검색을 한번 해보겠습니다.

import time
start = time.time()

n_list = set(range(10000))

#m_list = list(range(10000))

for i in range(10000):
    if i in n_list:
        pass
print("time : ", time.time() - start)

#time :  0.00810694694519043	(set)
#time :  1.7379398345947266	(list)

set, list에 만 개의 원소를 갖게 생성을 하고 만 번씩 검색해봤습니다. 컴퓨터에 따라 다르겠지만 제 경우에는 200배의 시간차이가 발생했습니다. 왜그럴까요?

 

set은 hash를 이용해 만들어졌습니다. 따라서 검색을 할때 O(1) 시간복잡도를 가지게 되죠 따라서 list로 검색을 할 때 아무리 알고리즘을 잘 짠들 set을 이용한 검색보단 못 할 수 밖에 없습니다.

hash라는 점에서 다시 한번 unordered collection의 의미를 알 수 있겠네요