[Python] list vs dictionary

파이썬의 자료구조 중 dictionary 를 공부하던 도중 dictionary 는 list 에서 index 대신에 key를 썼다? 이런 차이 밖에 되지 않나..뭐 더 다른게 있나? 의문을 품고 있던 중 dictionary 가 list 보다 검색 속도가 빠르다는 정보를 보고 직접 비교하는 시간을 가져보았습니다.

list와 dictionary를 동일한 조건으로 테스트하기 위해서 list는 n x 2 의 2차원 배열로 생성 후 각각 key 와 value를 할당 후 랜덤한 순서로 append 하였습니다.

그 후 특정 key 위치의 value의 데이터를 찾는 데 걸리는 시간을 python의 내장 모듈인 time을 이용하여 비교하였습니다.

test code

import time
import random

'''
## Dictionary과 List에서 탐색의 성능 비교 ##

- 비교 상황 key 값이 n(0~1000000) 인
value를 찾는 시간을 비교

조건 1. list와 dict의 key와 value는 동일
조건 2. list와 dict에 값을 넣는 순서 동일
조건 3. key값은 중복없이 랜덤(0~1000000)
조건 4. value는 랜덤(0~100)

'''
#1. 랜덤 값 생성
def create_data (n):
    # key 값 생성
    keys = [i for i in range(n)]
    # key 값 섞기 (중복없는 랜덤)
    random.shuffle(keys)
    # value값 생성 
    # random.randrange(시작, 끝) -> 범위 내 랜덤 출력
    values = [random.randrange(0,100) for i in range(n)]
    
    # 두가지 데이터로 [key, value] array를 생성
    data = [[keys[i],values[i]] for i in range(n)]
    #print(data)
    return data 

def create_dict (li):
    d = {}
    KEY = 0
    VALUE = 1
    #랜덤값을 딕셔너리에 대입
    
    for i in li:
        d[i[KEY]] = i[VALUE]
    #print(d) 
    return d

def find_list(key, li):
    start = time.time()
    for i in li:
        if i[0] == key:
            t = (time.time() - start) * 1000 #ms
            return {'key': i[0] ,'value': i[1], 'time' : t}
    return -1

def find_dict(key, d):
    start = time.time()
    try:
        value = d[key]
        t = (time.time() - start) * 1000 #ms
        return {'key': key ,'value': value, 'time' : t}
    except:
        return -1

def time_test(n, key):
    # 리스트 생성
    NUM_DATA = n # n개의 데이터
    KEY = key # 찾으려는 Key 값
    li = create_data(NUM_DATA)

    # 딕셔너리 생성
    d = create_dict(li)
    #시간 측정(리스트)
    t_li = find_list(KEY, li)
    #시간 측정(딕셔너리)
    t_d = find_dict(KEY, d)
    
    return {'list': t_li, 'dict': t_d}

if __name__ == '__main__':

    print('[10개 탐색 시]')
    r = time_test(10, 1)
    print(f'리스트 탐색: {r["list"]}')
    print(f'딕셔너리 탐색: {r["dict"]}')
    print(f'{r["list"]["time"] / r["dict"]["time"]}배 차이\n')
    
    print('[10^2개 탐색 시]')
    r = time_test(100, 1)
    print(f'리스트 탐색: {r["list"]}')
    print(f'딕셔너리 탐색: {r["dict"]}')
    print(f'{r["list"]["time"] / r["dict"]["time"]}배 차이\n')

    print('[10^4개 탐색 시]')
    r = time_test(10000, 1)
    print(f'리스트 탐색: {r["list"]}')
    print(f'딕셔너리 탐색: {r["dict"]}')
    print(f'{r["list"]["time"] / r["dict"]["time"]}배 차이\n')

    print('[10^6개 탐색 시')
    r = time_test(1000000, 1)
    print(f'리스트 탐색: {r["list"]}')
    print(f'딕셔너리 탐색: {r["dict"]}')
    print(f'{r["list"]["time"] / r["dict"]["time"]}배 차이\n')

결과

list 의 경우 시간이 자료의 크기 비례하여 늘어나지만 dictionary 의 경우 거의 일정한 시간으로 탐색을 완료했음을 확인 할 수 있었습니다.

마무리

처음에는 단순히 탐색시간 비교를 위해서 테스트를 작성해보다가 dictionary는 hash table을 이용한다는 것을 알 수 있었습니다. hash table은 key값에 따라 value가 저장될 위치가 결정됩니다. 그래서 탐색시 key값이 있으면 굳이 배열의 전체를 탐색하지 않고도 value를 얻을 수 있었고, list와 dictionary의 탐색속도가 결과와 같이 차이가 발생함을 알 수 있었습니다.