[Python] List와 Set에서의 in 연산자 성능 비교하기.

 

in 연산자를 쓸 때는 set으로 바꿔서 쓰면 빠르다.

List에서 in 연산자를 사용하면 사실 상 for문을 한번 도는 것이기 때문에 선형 시간인 O(n)의 시간 복잡도를 가집니다.

제 주변에서 이를 모르고 사용하다가 알고리즘 문제에서 Timeout이 걸리는 경우를 종종 보았는데,

List에서 set으로 바꾸고 in 연산을 하면 이러한 부담이 많이 줄어들게 됩니다.

 

 

List 자료형에서는 in 연산자의 시간 복잡도는 O(n)입니다.

a = list(range(1, 10000001))
print(1 in a) # 첫번째 값
print(10000000 in a) # 마지막 값

<걸린 시간>
0.17809176445007324
0.45179247856140137

그래서 1 ~ 10,000,000의 값을 가진 리스트에서 맨 첫번째 값을 검색했을 때는 1번만 검사하지만,

맨 마지막 값을 검색했을 때는 처음부터 끝까지 10,000,000번을 검사하게 되는 것입니다.

따라서 List에서의 in 연산은 데이터가 커지거나 연산이 많을 수록 선형적으로 시간이 늘어나게 됩니다.

 

하지만 set이나 dict 자료형에서는 in 연산자의 시간 복잡도는 O(1)입니다.

a = set(range(1, 10000001))
print(1 in a) # 첫번째 값
print(10000000 in a) # 마지막 값

<걸린 시간>
0.5380706787109375 -> List에서 in 연산 시간
0.6510920524597168 -> Set에서 in 연산 시간

set은 해시 함수와 해시 테이블을 이용해서 만든 자료구조이기 때문에 List처럼 선형적으로 탐색하지 않습니다.

그래서 맨 첫번째 값을 검사하나, 맨 마지막 값을 검사하나 시간에는 큰 차이가 없는 것을 확인할 수 있습니다.

따라서 set의 경우에는 해시 함수 연산 시간만큼 걸리므로, 데이터가 커지더라도 일정한 속도가 보장됩니다.

그래서 무언가 값이 있는지 확인하려면 set() 으로 변경한다음 in 연산을 사용하는 것이 좋습니다.

그런데, 위에 시간을 봤을 때는 set이 더 느려보이는데 어떻게 된 일 일까요?

 

 

데이터를 한번 키워서 다시 실험을 해보겠습니다.

# 데이터 범위: 10,000,000개
# 연산 횟수: 1,000번

# List에서 in 연산
a = list(range(1, 10000000))
for i in range(1000):
    print(i+8000000 in a)

# set에서 in 연산
b = set(range(1, 10000000))
for i in range(1000):
    print(i+8000000 in b)

121.49746608734131 -> List에서 in 연산 시간
0.5296247005462646 -> Set에서 in 연산 시간

확실히 연산을 1000번으로 늘리고 다시 실험해보니 차이가 크게 나타나는 것을 볼 수 있습니다.

심지어 set은 1000번이나 연산이 늘어났음에도, 아까 1번 연산을 했을 때와 속도가 비슷한 것을 확인할 수 있네요;;

 

 

정리해보자면,

• 어떤 값이 data 안에 있는지 확인하기 위해서 List에서 in 연산을 사용하는 경우가 많다.
• 하지만 List에서 in 연산은 O(n)으로 선형시간으로 탐색한다. 반면에 set이나 dict는 O(1)로 상수시간으로 탐색한다.
• 따라서 많은 양의 데이터에서 in으로 값을 검색하고자 할 때는 set으로 변환하면 더 빠르다!
• 이는 데이터와 연산이 굉장히 많을 때, 더욱 빛을 발한다.

 

출처

TimeComplexity - Python Wiki

[Python] 파이썬 'in' 연산자 시간 복잡도(Time Complexity)