[Python] Best Practice - 두 리스트 간 교집합 찾기

두 리스트 간 교집합 찾기

방법 1 - 리스트 순환

import random
import time

# 문제 : 각 2만개의 랜덤한 값을 가진 리스트에서 겹치는(intersection) 원소 찾기
list_a = [str(random.randint(0, 10000)) for _ in range(20000)]
list_b = [str(random.randint(0, 10000)) for _ in range(20000)]

# 대조군 : list 순환
start = time.time()
intersection_1 = []
for b in list_b:
    if b in list_a:
        intersection_1.append(b)
print(time.time() - start)

3.3787968158721924

방법 2 - set 으로 변환 후 & 연산

코드

import random
import time

# 문제 : 각 2만개의 랜덤한 값을 가진 리스트에서 겹치는(intersection) 원소 찾기
list_a = [str(random.randint(0, 10000)) for _ in range(20000)]
list_b = [str(random.randint(0, 10000)) for _ in range(20000)]

# 실험군 : set(집합) 으로 변환한 뒤 & 연산
# 원리 : set 연산은 hash 연산을 사용하여 빠른 연산이 가능하다.
start = time.time()
intersection_2 = list(set(list_a) & set(list_b))
print(time.time() - start)

# 원소가 동일한지 확인
print(set(intersection_1) == set(intersection_2))

0.006021976470947266
True

원리

• (1) set은 hash table 기반으로 비교하므로 빠르며
• (2) & 연산은 각 원소를 “더 작은 set 에서 순회하며” hash lookup으로 검사하기 때문에 빠름
• (3) 또한 Python의 for-loop 구조에서는 내부적으로 수행되는 작업이 있는데, 이를 수행하지 않아도 돼서 빠르다.

방법3 - set 의 intersection 메서드 사용

import random
import time

# 문제 : 각 2만개의 랜덤한 값을 가진 리스트에서 겹치는(intersection) 원소 찾기
list_a = [str(random.randint(0, 10000)) for _ in range(20000)]
list_b = [str(random.randint(0, 10000)) for _ in range(20000)]

# 실험군 2 : set의 intersection 메서드 사용
start = time.time()
intersection_3 = set(list_a).intersection(set(list_b))
print(time.time() - start)

# 원소가 동일한지 확인
print(set(intersection_1) == set(intersection_3))

0.004326936173957672
True

• 원리는 & 연산과 동일 (내부적으로 동일한 C 함수를 호출)

방법 2 원리 설명

set은 hash table 기반으로 비교해 빠르다

• x in list_a 와 같이 리스트에서 접근하는 경우, 앞에서부터 하나씩 비교하며 O(n) 시간복잡도
• x in set(list_a) 와 같이 집합에서 접근하는 경우, hash(x) 계산을 통해 바로 위치로 접근해 O(1) 시간복잡도

더 작은 set에서 순회

• 파이썬에서 & 연산을 할 때에는 크기가 더 작은 쪽에서 순회를 하는 특징이 있다.

len(A) = 1000000
len(B) = 10

• 위 코드에서 A & B 연산을 하면 Python은 아래와 같이 동작한다.
• (1) 작은 쪽(B)를 순회한다 – 총 10회
• (2) 각 원소를 A에서 lookup 한다 – O(1)
• 결과적으로 10 * O(1) = O(10) 의 시간복잡도

반면에, 큰 쪽(A)에서 순회를 한다고 가정하면
1000000 회 * O(1) = O(1000000) 의 시간복잡도가 발생한다.

hash lookup

• 값을 하나씩 비교하지 않고, hash(value) 로 계산한 위치에 바로 가서 존재 여부를 확인하는 방식
• 반면에 list lookup은 앞에서부터 하나씩 값을 비교해가는 작동 방식이다.
• 따라서 hash lookup 은 O(1) 의 시간복잡도 를 가지며
• list lookup 은 O(n) 의 시간복잡도 를 가진다.
• Python에서 hash lookup을 하는 자료구조는 set, dict 등이 있다.

# hash lookup
x in set(list_a)

# 동작 방식  
h = hash(x)
index = h % table_size # 그 칸에 x가 있는지만 확인

# -> O(1)

# list lookup
x in list_a

# 동작 방식
list_a[0] == x ?
list_a[1] == x ?
...
list_a[n] == x ?

# -> O(n)

Python의 for-loop 구조를 스킵

for x in list_a:
    if x in list_b:
        ...

• Python 에서는 for-loop 이 수행될 때 아래와 같은 작업이 동반된다.
• (1) 바이트코드 해석
• (2) 객체 타입 검사
• (3) 함수 호출
• (4) 조건 분기
• 이 모든 단계에 Python 인터프리터가 개입하므로, 수행되는 작업이 많다.
• 이러한 for-loop 구조를 스킵하면, 작업 시간을 크게 줄일 수 있다.