Python으로 프로그래밍을 할때, 궁금한 점이 있었다. 파이썬에서는 다른 언어들과는 다르게 in이라는 키워드를 지원한다. in을 사용하려면 해당 자료형이 __contains__ 를 구현해야 하는데 아무튼 in의 효율이 얼마나 좋은지 확인하고 싶어졌다.
어떤 num_list에 num을 삽입하려고 하는데 이 num_list에 중복된 요소가 없어야 한다고 가정하자. 이때 우리가 생각해볼 수 있는 로직은
if not num in num_list:
num_list.append(target)또는
num_list.append(num)
num_list = list(set(num_list))이렇게 둘로 갈릴 것 같다.
첫 번째는 일반적으로 우리가 편히 사용하는 방식이다. in을 이용해 포함되지 않은 num만 num_list에 추가하는 것이다.
두 번째는 일단 아이템을 추가하고 list를 set으로 변환해 중복을 제거해주는 것이다. 물론 원래 list였으니 다시 list로 캐스팅한다.
어느 정도 예상이 갈 것 같다. 캐스팅을 두번이나 하는 후자가 더 느릴 것 같지 않은가?
num과 num_list를 다음과 같이 정의하고 실행해보자.
num_list = [i for i in range(10000000)]
num = 5000000실행 결과
전자: 0.031238794326782227
후자: 0.37149858474731445
확실히 전자가 빠르다. 이번엔 리스트 바깥값으로 실행해보자
num_list = [i for i in range(10000000)]
num = 100000000실행 결과
전자: 0.07778191566467285
후자: 0.3787510395050049
전자의 시간이 2배가 증가했음에도 압도적으로 전자가 빠른 것을 알 수 있다.
그렇다면 또 궁금한 점은 캐스팅을 하지 않는다면 어느 것이 더 빠를까?
num_list = [i for i in range(100000000)]
import time
num = -1
#in을 사용한 경우
start = time.time()
if not num in num_list:
num_list.append(num)
print(time.time() - start)
#set에 바로 삽입한 경우
set(num_list)
start = time.time()
num_list.append(num)
print(time.time() - start)전자: 0.7329707145690918
후자: 0.0
후자의 시간이 너무 작아서 표시가 되지 않는다. 사실 리스트의 크기도 10배로 늘렸다. 그래도 표시되지 않아서 좀 놀랐다. 어쩌면 set 자료형이라고 하면 당연한 결과이기도 하다. 그 이유는 set은 해시를 이용하기 때문에 삽입, 삭제, 검색에서 통계적으로 O(1)을 보장한다.(해시 충돌이 없을 때)
Referenced: https://rexiann.github.io/2020/11/28/set-in-python.html
그럼 이제 남은 것은 하나다. in은 어떻게 작동하는 걸까?
list와 tuple에서는 모든 원소를 순회하는 방식으로 구현되었다고 알려진다. __contains__ 를 구현하는 문서를 확인할 수 없어서 확실하게 알 수는 없었다.
set과 dict에서는 해시를 이용하기 때문에 위에서 말했다시피 O(1) 수준의 시간복잡도를 가진다.
그런데 혹시라도 for문을 이용해 n개의 원소에 대해 비교를 수행할 경우 n이 충분히 클 때, set으로 캐스팅을 통해 중복을 제거하는 방법의 효율이 좋아졌다. in은 순차 탐색을 하므로 원소가 적절히 shuffle된 상태이고 input 원소 수가 100개를 족히 넘어간다면 캐스팅을 통해 효율을 잡아보는 것을 추천한다.
심심해서 해본 실험인데 생각보다 솔깃한 정보였던 것 같다. 아무튼 Python의 in 키워드는 최선의 시간복잡도를 보장하므로 대부분의 경우에 편하게 사용하면 될 것 같다.
