[Python] Set(세트) vs List(리스트) 검색 속도 비교

 변수나 자료형 등이 중복으로 나타나는지와 같은 확인을 위해 'in'이라는 키워드를 많이 사용한다. 이때 Set와 List 중 어떤 것을 사용하느냐에 따라 속도의 차이가 매우 커질 수 있다. Set가 List에 비해 일반적으로 빠른 성능을 보이는데 이는 Set가 Hash Table로 구현이 돼있는 반면, List는 배열로 구현돼있기 때문이다.

 Hash Table의 경우 검색(lookup), 삽입(isertion), 삭제(deletion)에 대해 O(1)의 시간 복잡도를 갖지만, 배열의 경우 O(n) 을 갖기 때문이다. 아래 코드를 통해 시간의 차이를 확인할 수 있다.

import time

my_list = list(range(1000000))
my_set = set(my_list)

start_time = time.time()
999999 in my_list
end_time = time.time()
list_time = end_time - start_time

start_time = time.time()
999999 in my_set
end_time = time.time()
set_time = end_time - start_time

print("List retrieval time:", list_time)
print("Set retrieval time:", set_time)

Google Colab에서 실행할 시 아래와 같은 결과가 나왔다.

: List retrieval time: 0.01374053955078125
Set retrieval time: 7.700920104980469e-05