[Python]dictionary를 이용한 알고리즘 시간 단축(feat. hashtable)

파이썬 Dictionary( = C의 hashtable )를 왜 써야 하나?

- 파이썬 dictionary는 C의 Hashtable이랑 거의 같다고 보면 됩니다. 

- 알고리즘 문제에서 list 대신 dictionary에 key:value를 등록하여 사용하면 속도개선이 가능합니다.

- 특히 문자열 관련 검색 문제가 나왔을 때 list를 쓰면 거의 시간초과가 발생하고, dictionary를 써서 속도를 올려야 합니다. 

 

list vs dictionary 속도차이 비교

-  임의의 문자열 1000만건에대하여 list와 dictionary의 검색시간을 비교해 보겠습니다. 

import time
import random
import string

# Generate sample data
words = [''.join(random.choices(string.ascii_lowercase, k=5)) for i in range(10000000)]
word_to_search = 'zebra'

# List search
start = time.time()
if word_to_search in words:
    print("Found in list")
list_search_time = time.time() - start

# Dictionary search
words_dict = {word: None for word in words}
start = time.time()
if word_to_search in words_dict:
    print("Found in dictionary")
dict_search_time = time.time() - start

# Print times
print(f"List search time: {list_search_time}")
print(f"Dictionary search time: {dict_search_time}")

list vs dict 속도차이

- List는 0.18초 이상 걸리는반면 Dictionary는 표기도 안될 정도로 빨리 탐색됩니다.

 

알고리즘 문제 예시

- 보통 알고리즘 문제에서는 초기 자료구조를 세팅해 둔 뒤 Search 함수를 무수히 많은 수만큼 호출하는 방식으로 문제를 구성합니다. 그렇기에 자료구조 구현에는 시간에 조금 걸려도되지만, Search 명령의 시간을 줄이는 것이 유리합니다. 아래 예시는 문자열 1000만건에대해 100건의 검색을 통해 일치하는 문자열이 있는지 탐색하는 문제입니다.     

import time
import random
import string

# Generate sample data
words = [''.join(random.choices(string.ascii_lowercase, k=5)) for i in range(10000000)]
test_words = [''.join(random.choices(string.ascii_lowercase, k=3)) for i in range(100)]

# List search
total_start = time.time()
for test_word in test_words:
    start = time.time()
    cnt = 0
    for i in range(len(words)) :
        if test_word in words[i]:
            cnt+=1
    list_search_time = time.time() - start
    print(f"List search time: {list_search_time} / {cnt}")
total_search_time = time.time() - total_start
print(f"Total List search time: {total_search_time}  ")



# Dictionary search
total_start = time.time()
from collections import defaultdict
words_dict = defaultdict(int)
for word in words :
    for i in range(3):
        words_dict[word[i:i+3]] += 1

for test_word in test_words :
    dict_start = time.time()
    cnt = words_dict['ebr']
    dict_search_time = time.time() - dict_start
    print(f"Dictionary dict search time: {dict_search_time} / {cnt}")
total_search_time = time.time() - total_start
print(f"Total Dictionary dict search time: {total_search_time}")

list 검색 시간 ( 한 건 당 1.37초, 100회 137초 )

dictionary 검색 시간 ( 한건당 0초, 100회 16.7초 )

- list로 구현한 경우, 한 건 검색당 시간이 오래 걸려 100회 검색했을 때 137초 정도의 시간이 걸렸습니다. 반면 Dictionary로 구성했을 경우 자료구조를 구성하는데 시간이 16초만큼 소요되지만 검색 시 시간이 소요되지 않으므로 100회 검색 시 16.7초만큼 시간이 소요됩니다. 문자열 검색은 Dictionary를 사용해 시간을 줄이시기 바랍니다.