들어가며

알고리즘 문제들을 풀 때, 문제 속에서 정수든 문자열이든 어떤 요소가 존재하는지 검사하는 로직이 필요한 경우가 많습니다. 파이썬은 느린 언어기 때문에 시간복잡도를 까다롭게 잡는 문제의 경우 조금이라도 시간을 줄이려는 노력이 필요합니다. 리스트와 딕셔너리, 그리고 집합을 비교해봅니다.

문자열 key

실험 방법

• 영문 소문자, 대문자 8자리로 이루어진 무작위 문자열을 500,000개를 생성해 리스트에 넣습니다. (100자리로 실험했을 때도 결과는 유사했습니다.)
• 같은 자릿수 무작위 문자열을 만들고 찾는 시간을 비교합니다.
• 무작위 문자열로 이루어진 리스트 생성 코드

from random import randint
from string import ascii_letters

def randstr(n):
    return ''.join([ascii_letters[randint(0, len(ascii_letters) - 1)] for _ in range(n)])
    
arr = [randstr(8) for _ in range(500000)]

만드는 시간 비교

코드

%timeit aset = set(arr)
%timeit adic = {k: 1 for k in arr}

결과

• Dict: 58.57 ms
• Set: 38.90 ms
• Comment
  • Set이 더 유리했습니다.
  • 자리수와 갯수를 바꾸어 봐도 유사한 결과가 도출되었습니다.

찾는 시간 비교

코드

aset = set(arr)
adic = {k: 1 for k in arr}

%timeit randstr(8) in aset	# 집합
%timeit randstr(8) in adic	# 딕셔너리
%timeit randstr(8) in arr	# 리스트

결과

• Dict: 9.88 µs
• Set: 9.79 µs
• List: 8.15 ms
• Comment
  • 알려진 시간 복잡도는 집합과 딕셔너리가 O(1), 리스트가 O(n) 입니다.
  • 딕셔너리와 집합은 거의 무의미한 차이였으며, 리스트와는 약 1,000배 정도 차이가 났습니다.
  • 여러 개의 요소를 검사하는 경우에는 만드는 시간보다 찾는 시간 비용이 더 비쌀 것으로 예상되므로 집합을 만들어놓고 찾는 것이 가장 빠르고, 그렇지 않은 경우에는 그냥 한 번 O(n)만 도는 것이 더 빠르기 때문에 각 상황에 맞게 자료형을 만들어야 하겠습니다.
  • 단순 존재성 검사 이외에도 어떤 값을 저장하거나 갯수를 세야 하는 경우에는 딕셔너리를 활용하는 것이 바람직합니다. 만약 key가 정수라면 정수 리스트를 만들어놓는것이 빠릅니다.

정수 key

실험 방법

• 0 <= n <= 1,000,000 의 숫자 500,000개를 무작위 생성해 리스트로 만들었습니다.
• 같은 범위의 무작위 숫자를 생성해 존재성을 검사합니다.
• 리스트의 경우 이번에는 단순 리스트 내 요소검사가 아닌 인덱스: 0 or 1로 존재를 저장했습니다. (만드는 시간 소요)
• 무작위 생성 코드

from random import randint
max_n = 10000000
arr = [randint(0, max_n) for _ in range(5000000)]

만드는 시간 비교

코드

%timeit aset = set(arr)
%timeit adic = {k: 1 for k in arr}
%%timeit
array = [0 for _ in range(max_n + 1)]
for item in arr:
    array[item] = 1

결과

• Dict: 75.1 ms
• Set: 48.5 ms
• List: 72.3 ms
• Comment
  • 이번에도 집합 자료형 만드는 시간이 가장 적었습니다.

찾는 시간 비교

코드

%%timeit 
   ...: if randint(0, max_n) in aset:
   ...:     pass
   ...: 
%%timeit
   ...: if randint(0, max_n) in adic:
   ...:     pass
   ...: 
%%timeit
   ...: if matrix[randint(0, max_n)]:
   ...:     pass

결과

• Dict: 1.43 µs
• Set: 1.41 µs
• List: 1.38 µs
• Comment
  • 시간복잡도는 모두 O(1) 입니다.
  • 배열에 직접 접근하는 리스트 형식이 조금이나마 더 빨랐지만, 유의미한 차이는 아니었습니다.

마치며

• 한 번 자료형을 만들고 반복문을 여러 번 돌며 여러 요소에 대해 존재만 검사하는 경우에는 고민할 필요 없이 Set을 사용하면 될 것 같습니다.
• 횟수, 방문여부, 중복검사등을 수행하기 위해 key에 대한 value가 필요한 경우 문자열은 Dict, 정수형은 List를 사용하면 될 것 같습니다.
• 최소한 item in list만 사용하지 않아도 불필요한 O(n^2)을 피할 수 있습니다.