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

TOC

• 작업 동기
• in연산자 소요 시간 비교
  • 비교방법
  • 결과
• 이유
  • List
  • Set
• 결론

작업 동기

파이썬에서 list와 set에서 in 연산자를 사용할 때의 시간 복잡도 차이가 발생하는 이유에 대해 알게 되어 정리하고자 한다.

접근 동기는 투포인터를 사용하는 문제라고 생각되는 문제(풀이 링크)를 풀었는데, 다른 유저들의 풀이를 살펴보다가 특이한 풀이를 발견했고, 이해가 되지 않는 부분이 있어서 알아보다 처음 알게 되었기 때문이다.

참고: 링크

in연산자 소요 시간 비교

복잡할 것도 없이 바로 비교해보겠다.

비교방법

from time import time
start = time()

arr = list(range(1, 1000001))

cnt = 0
for k in range(10000):
    cnt += (k+100000 in arr)

end = time()
print(end - start)

time 모듈을 이용하였고, 100만 크기의 배열에서 k에 10만을 더한 값이 있는지 확인한 뒤 이 결과를 cnt에 더하는 연산을 한다. 이를 1만 번 반복한 뒤, 소요 시간을 출력하였다.

set의 경우 range를 list로 감싸주는 자리에 set만 바꿔 넣어 주었다.

결과

자료형	list	set
소요시간	19646ms	75ms
상대 소요시간	262	1

list의 경우 set에 비해 약 262배나 많은 시간을 요구했다.

이유

왜 이런 결과가 나타나는 걸까?

List

• list는 in 연산자를 사용하면 처음부터 끝까지 원소 중에서 일치하는 것이 있는지 비교
• 이때 일치한다면 연산 종료
• 때문에 비교하는 원소가 없거나 뒤에 있을수록 소요시간이 선형적으로 증가
• 시간복잡도: O(n)

Set

• 반면 set과 dictionary는 hash table을 사용
• 때문에 맨 끝 값과 맨 앞 값의 조회 시간 차이가 없음
• 연산 시간은 hash 함수 연산 시간만큼 소요
• 데이터 크기와 상관 없이 일정한 속도 보장
• 시간복잡도: O(1)

결론

• List에서 in 연산은 **O(n)**의 선형시간, Set에서의 in 연산은 **O(1)**의 상수시간 소요
• hash table을 사용함에 따라 Set은 공간복잡도(메모리) 소폭 증가
• 빠른 검색이 필요한 경우 Set 활용하자.