1. Introduction
파이썬에서 in 연산자는 검색이나 순회에 사용된다.
순회는 항상 전체를 순회하니까 효율의 개선이 필요하다고 느껴지 않지만, 검색은 그렇지 않다.
이번 포스트에서는 in의 검색 효율이 자료구조에 따라 어떻게 바뀌는지를 알아본다.
2. Detail
파이썬에서 리스트와 튜플은 array로 구현된다.
따라서, 알맞은 원소를 찾아내기 위해서는 array를 처음부터 끝까지 순회할 수 밖에 없다.
리스트와 튜플에 대한 in 연산자의 시간복잡도는 $O(n)$이다.
반면에, 셋과 딕셔너리는 hash로 구현된다.
hash에 검색 성능이 hash function에 의존하는 만큼, 성능이 최선일 때 $O(1)$에서 최악일 때 $O(n)$까지 요동친다.
웬만한 경우에서, 특히 고정된 리스트에서 검색을 여러번 해야 할 수록, 리스트를 셋으로 바꾼뒤에 검색하는 것을 추천한다. 만약 중복원소를 유지해야하기 때문에 리스트를 유지해야한다면, 리스트를 먼저 정렬한 다음에 이진검색을 사용하자.
