파이썬에서 "in list"에서 "in set"으로 바꾼 것만으로 폭속이 된 건과 그 이유

목록에 특정 요소가 있는지 찾는 프로세스

어떤 경기 프로그래밍에서 "대량의 요소군 안에 특정 요소가 들어 있는지 확인한다"라고 하는 처리를 구현할 필요가 있었습니다.

나는 아무것도 생각하지 않고 List 형으로 구현했습니다.

대체로 같은 일을 하고 있는 것이 이하의 코드가 됩니다.

list.py

import time
from random import randint

a = list()
for _ in range(100000):
    a.append(randint(1, 10000000))  # 1 ~ 10000000 の間の数値をランダムに 100000 個リストに append

for _ in range(10):  # 今回は実験のため、10回実行
    result = 0
    start_time = time.time()
    for _ in range(100000):
        num = randint(1, 10000000) # 改めて1 ~ 10000000 の間の数値をランダムに 100000 個選び、リスト中にあれば result を + 1 する
        if num in a:  # 要素がリスト中に存在するかチェック
            result += 1
    # print(result)
    print("elapsed_time:{time} sec".format(time=time.time() - start_time))

실행 결과

elapsed_time:240.42141199111938 sec
elapsed_time:227.7156150341034 sec
elapsed_time:220.98236417770386 sec
elapsed_time:216.4878408908844 sec
elapsed_time:213.12895107269287 sec
elapsed_time:214.8469820022583 sec
elapsed_time:218.6278579235077 sec
elapsed_time:215.24347305297852 sec
elapsed_time:223.3752110004425 sec
elapsed_time:218.8238799571991 sec

평균 3분 반이 소요됩니다.
이것은 늦었고 아무래도 규정의 초 이내에 끝나지 않았습니다.
그 취지를 Twitter로 어리석은 곳, 「List가 아니고 Set로 하면 고속화할 수 있어요」라는 하늘의 목소리를 받았습니다.
정말? 라고 생각해, 시험에 실장해 보았습니다.

같은 처리를 Set로 써 보자

그럼 , 같은 처리를 Set 형을 사용해 해 봅시다.

set.py

import time
from random import randint

a = set()
for _ in range(100000):
    a.add(randint(1, 10000000))  # 1 ~ 10000000 の間の数値をランダムに 100000 個を集合に add

for _ in range(10):  # 今回は実験のため、10回実行
    result = 0
    start_time = time.time()
    for _ in range(100000):
        num = randint(1, 10000000)  # 改めて1 ~ 10000000 の間の数値をランダムに 100000 個選び、集合中にあれば result を + 1 する
        if num in a:  # 要素が集合中に存在するかチェック
            result += 1
    # print(result)
    print("elapsed_time:{time} sec".format(time=time.time() - start_time))

실행 결과

elapsed_time:0.23300909996032715 sec
elapsed_time:0.22655510902404785 sec
elapsed_time:0.20099782943725586 sec
elapsed_time:0.23000216484069824 sec
elapsed_time:0.25554895401000977 sec

elapsed_time:0.2030048370361328 sec
elapsed_time:0.22499608993530273 sec
elapsed_time:0.24254608154296875 sec
elapsed_time:0.24500298500061035 sec
elapsed_time:0.21805286407470703 sec

빨리! 리스트 시간의 약 100배의 속도로 처리가 완료되고 있습니다.

왜 이렇게 차이가 나는가

파이썬에서 List 구현

Python에서 list() 는 "목록 구조"로 구현됩니다.
즉, 리스트 a 에 들어 있는 각 요소는 .append 가 불린 순서에 들어가 있는 것만으로, 요소를 찾을 때의 힌트는 없습니다.

if num in a: 의 처리를 실시하려면 , 리스트의 요소를 완전 탐색할 필요가 있습니다.


위를 계속 반복한다…

그 때문에 100000회 100000개의 요소의 전체 탐색이 달린 list판은 매우 실행에 시간이 걸렸습니다.

Python에서 Set 구현

Python에서 set() 은 "해시 테이블"로 구현됩니다. (이번 조사해 알았습니다…!)
즉, 실제의 수치 이외에 인덱스가 붙여진 탐색하기 쉬운 정수와의 페어로 값이 들어가 있습니다.


그 덕분에, 예를 들면 「집합중에 120이라고 하는 값이 있을까」라고 하는 탐색은, 해시값을 바탕으로 요소를 찾을 수가 있기 때문에, 검색은 매우 적은 횟수로 끝납니다. (CPython의 코드까지는 읽을 수 없었습니다만, 분명 굉장한 사람들이 굉장한 방법으로 구현하고 있는 것입니다…)


이것이 검색 시간에 압도적인 차이가 나온 이유입니다.
덧붙여서, dict() 의 키도 같은 해시 테이블이기 때문에, 사전형의 키의 탐색은 매우 고속으로 행해집니다.

Set 는 단순히 중복을 허락하지 않는 것이나, 화집합·차집합을 계산할 수 있을 뿐만 아니라, 이런 이점이 있었군요.
Python을 업무에서 3년 만지면서, 오이타 알고 있을 생각이었습니다만, 아직도였습니다.

참고

데이터 구조 — Python 3 문서

알고리즘 도감

파이썬에서 "in list"를 처리하는 것은 매우 느립니다.