[Pandas] Best Practice - merge 를 통한 해시 기반 조인으로 Python-level 반복문 대체

잘못된 내용이 있는 경우, 댓글로 알려주시면 감사하겠습니다!

hash 기반 join을 통한 성능 향상

Intro

이전 포스팅들에서 반복 횟수 감소, 딕셔너리 캐싱 방법을 이용해 프로그램의 실행 속도를 개선해봤다. 이번 포스팅에서는, 이전 두 포스팅과 동일한 Dataframe 반복 문제에서 가장 효율적인 실행속도를 보여줄 수 있는 방법을 탐색해보도록 한다.

라이브러리

import pandas as pd
import random
import time

실험 데이터셋

• df_a : user_id, some_data 두 컬럼으로 이루어져 있다.
• df_a의 some_data 는 약 20% 가량이 NaN 값을 가진다.
• df_b : user_id, alt_data 두 컬럼으로 이루어져 있다.
• df_a와 df_b의 user_id 집합은 동일하다.
• df_b 의 alt_data 에는 결측치가 없다.

qnt = 10000 # 데이터 수
df_a_origin = pd.DataFrame({
    "user_id" : [str(x) for x in range(1, qnt+1)],
    "some_data" : [random.randint(0, qnt) if random.randint(0, qnt) < qnt*4/5 else None
                   for _ in range(qnt)]
})
df_b = pd.DataFrame({
    "user_id" : [str(x) for x in range(1, qnt+1)],
    "alt_data" : [random.randint(0, qnt) for _ in range(qnt)]
})

실험의 목표

• df_a 의 NaN 인 some_data 값을 찾아, df_b 의 동일 user_id 의 alt_data 로 대체한다.

대조군

• 작동 방식 : df_a 의 각 row 를 순회하며 NaN값 여부를 확인하고, alt_data로 대체한다.

순서	작동	시간복잡도
1	df_a의 각 row를 순회하며, some_data가 NaN인지 확인한다.	O(N_a)
2	NaN값인 경우, df_b에서 동일한 user_id 에 해당하는 alt_data를 찾는다.	O(N_b)
3	row의 some_data 를 찾은 alt_data로 대체한다.	O(1)

전체 시간복잡도 : O(N_a * N_b)
또한 매 반복마다 boolean mask 를 생성하므로 메모리 비용이 발생

df_a = df_a_origin.copy()
start = time.time()
for i, row in df_a.iterrows(): #-------- (1)
    if pd.isna(row["some_data"]): #----- (1)
        df_a.at[i, "some_data"] = df_b.loc[df_b["user_id"] == row["user_id"], "alt_data"].iloc[0] #----(2)(3)
print(f"time check 1 ::: {time.time() - start}")

time check 1 ::: 0.7818460464477539

문제 포착

• python-level의 반복과 df_b에서 user_id 에 해당되는 row를 찾는 lookup 연산은 큰 연산비용을 가진다.

실험군

• 작동 방식 :

순서	작동	시간복잡도
1	df_a 와 df_b를 user_id 키를 기준으로 merge한다.	O(N_a + N_b)
2	fillna() 메서드를 통해 some_data 가 NaN 인 경우, alt_data로 대체한다.	O(N_a * 1)

전체 시간복잡도 : O(N_a + N_b) + O(N_ * 1)
= O(N_a + N_b)

df_a = df_a_origin.copy()
start = time.time()
df_merge = df_a.merge(df_b, on="user_id", how="left") # O(N_a) + O(N_b)
df_merge["some_data"] = df_merge["some_data"].fillna(df_merge["alt_data"]) # fillna : 벡터화된 연산. O(N_a)
df_merge
print(f"time check 2 ::: {time.time() - start}")

time check 2 ::: 0.00737309455871582

결과 리뷰

• 이전 두 포스팅보다도 훨썬 더 큰 폭의 성능 향상이 이루어졌다.
• 시간복잡도는 딕셔너리 캐싱과 동일하지만, 성능 향상 폭이 다른 이유에 대해서는 아래 원리 섹션에서 살펴본다.

원리

Python 레벨의 반복문을 C/CPython 레벨 반복문으로 대체

• “연산 + 관리 비용”이 함께 있는 파이썬의 반복문을, “순수 연산 비용”에 가까운 C/CPython 레벨로 컴파일된 반복문으로 대체함으로써, 실행 비용을 크게 줄인다.
• 파이썬 반복 1회의 실제 비용은 아래와 같다.

for x in iterable:
    do_something(x)

# 1. Python bytecode 해석
# 2. iterator 객체 호출 (`__next__`)
# 3. Python object 생성 / 참조
# 4. 타입 동적 확인
# 5. reference count 증가/감소
# 6. GIL 유지

• 반면 C/CPython 레벨의 1회 반복 비용은 아래와 같다.

for (i = 0; i < n; i++) {
    if (isnan(a[i])) a[i] = b[i];
}

// 정적 타입임(타입 해석 필요 없음)
// 직접 메모리 접근 (iterator 필요 없음)
// 함수 호출 없음
// reference count 없음

merge의 내부 동작

• pandas의 merge 는 내부적으로 hash 기반의 join을 사용한다.
• C/CPython 레벨로 동작하여 빠르다.
• merge 메서드는 아래와 같은 내부 동작을 가진다.

순서	작동	시간복잡도
1	df_a 또는 df_b를 해시테이블로 구성한다.	O(N)
2	다른쪽 테이블을 순회하며	O(N)
3	각 row의 key로 해시테이블에서 매칭되는 key를 lookup 한다.	O(1)

시간복잡도 : O(N_a) + O(N_b * 1)
= O(N_a + N_b)

참고 : 1번 순서에서 어떤 df를 해시테이블로 만들지는 데이터에 따라 다르다. pandas가 두 데이터프레임 중 해시테이블로 만드는 게 유리한(=성능이 좋은) 쪽을 택해 해시테이블로 만든다. 여기서 고려되는 사항은 데이터의 크기, 데이터 타입, 중복도 등이 있다.

fillna의 내부 동작

• pandas의 fillna 메서드는 C/CPython 레벨의 벡터화된 연산을 수행한다.(빠름)
• fillna 메서드는 아래와 같은 내부 동작을 가진다.

순서	작동	시간복잡도
1	데이터프레임을 순회하면서	O(N)
2	각 순회마다 특정 값이 NaN인지 검사한다.	O(1)
3	NaN인 경우, 지정된 값으로 대체한다.	O(1)

시간복잡도 : O(N) + O(1) + O(1)
= O(N)

추후 작업

• 더욱 성능을 향상시킬 방법을 탐색한다.
• 후보 : SIMD, branch 제거, 내부 알고리즘 선택 (hash join vs sort merge)