[python] 파이썬 re 모듈 동작 방식

문제 상황

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

문제 조건에서 접두사가 매칭되는 경우를 찾으면 false을 반환하라고 한다. 맨 처음 작성한 코드에서는 "접두사"라는 표현에 집중하여 re 모듈을 이용하여 정규표현식 비교 코드를 작성했다.

import re

def solution(phone_book):
    phone_book.sort()
    for i in range(0, len(phone_book) - 1):
        if re.search(f'^{phone_book[i]}', phone_book[i+1]):
            return False
    return True

이 경우 테스트는 문제없이 동작하지만, 효율성 테스트에서 실패하는 문제가 있었다.

시간 초과가 나온 모습

문제 발생 원인 예상

 나는 문제가 될 수 있을 것 같은 지점을 크게 2개 부분으로 생각했다.

1. f string을 이용할 때마다 새로운 문자열이 생성되기 때문에
2. re 모듈 내부의 re.search 구현 상에 효율성을 떨어뜨리는 특징이 존재

 1번의 경우 f-string의 문자열 결합 방식이 파이썬이 제공하는 문자열 결합 방식 중 가장 효율적인 것으로 알려져 있으므로 시간복잡도 측면에서는 문제가 되지 않을 것이다. 이에 대해 쓴 글이 있으니 참고하자. 공간 복잡도 측면으로 생각한다고 해도 어차피 for문을 순회할 때마다 할당된 문자열은 파이썬의 가비지콜렉터가 적절한 시기에 해제할 것이므로 메모리 상으로도 문제가 발생할 일은 없다.

 따라서 위 코드가 문제가 되는 이유는 re 모듈 자체에 있다고 판단되었다. 따라서 re 모듈의 구성을 살펴보기 위해 inspect 모듈을 이용하여 해당 모듈의 소스코드를 살펴봤다.

re 모듈 동작 방식 살펴보기

 파이썬은 오픈소스 기반 언어이므로 github에서 내부 구현을 살펴볼 수 있다. 아래 링크를 참고하자.

re 모듈의 __init__.py 파일: https://github.com/python/cpython/blob/main/Lib/re/__init__. py

import inspect

print(inspect.getsource(re))

_compiler 모듈의 모든 함수를 import 하고 있는 모습

search 모듈의 정의

re 모듈의 search 함수는 내부적으로 _compiler.py에 정의된 _compile 함수를 사용하며, 반환된 객체의 search 함수를 실행, 결과 값을 반환한다.  _compiler.py 파일부터는 모듈 밖으로 공개되지 않으므로 github 상의 소스코드를 참고했다.

_compile 함수 정의: https://github.com/python/cpython/blob/main/Lib/re/__init__.py#L280

_compile 함수의 대부분 동작은 캐시와 관련되어 있다. 실질적인 컴파일 동작은 re 모듈 내 다른 파일인 _compiler.py에서 수행되며, _compile 함수는 _compiler.compile 함수가 반환한 객체를 캐싱하는 작업 정도만 수행한다. 코드에 따르면 _compile 함수는 _cache, _cache2라는 이름을 가진 2개의 딕셔너리를 캐시로 사용하며, 크기는 각각 512, 256이다.

_compile 함수 내부에서 캐싱을 하는 모습

_compiler.compile 함수: https://github.com/python/cpython/blob/main/Lib/re/_compiler.py#L738

_compiler.compile 함수의 경우 정확한 동작 방식을 파악하기는 어렵지만 전달된 패턴을 파싱, 플래그 값 등을 이용하여 플래그 값을 컴파일하여 얻은 객체를 반환한다. 파이썬 공식문서에서는 해당 객체를 정규식 객체(Pattern)로 묘사하며, 해당 객체에 대한 타입은 __init__.py 내에 type 함수를 이용하여 나타내고 있다.

해당 함수는 내부적으로 _sre라는 모듈을 사용하고 있으나, 이는 파이썬 모듈이 아니라 C언어로 작성되어 있으며, re 모듈의 대부분 기능을 수행하는 것으로 알려져 있다. 자세한 구현이 궁금하다면 Modules 폴더의 _src 모듈을 보자. 

https://github.com/python/cpython/tree/main/Modules/_sre

---

 결론

위 정보들을 통해 알 수 있듯이 re 모듈은 1. 일련의 과정을 통해 정규식 객체(Pattern)를 만들고, 2. 해당 객체를 __init__. py 파일 내에서 2개의 딕셔너리 자료형을 통해 캐싱한다. 캐싱은 몇 개의 동일한 정규식을 자주 사용하는 프로그램에서는 유용할 수 있으나 현재 문제처럼 데이터에 중복이 없는 상황에서는 해당 정규식 객체를 다시 사용할 일이 없음에도 캐싱하여 쓸모없는 메모리를 차지하게 되며, cache conflict가 발생하여 연산 면에서 오히려 손해를 보게 된다. 일반적으로 캐싱은 전체적인 비용을 줄이기 위해 수행한다는 것을 생각해 보면 정규식 객체의 생성은 캐싱보다 큰 비용을 요구할 텐데, 이런 작업을 계속 진행하므로 당연히 시간 및 공간 복잡도 측면에서 손해를 볼 수밖에 없다.

 따라서 이 문제를 풀기 위해서는 re 모듈 대신 단순한 문자열 비교를 수행해야 한다. 코드는 다음과 같다.

def solution(phone_book):
    phone_book.sort()
    for i in range(0, len(phone_book) - 1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
    return True
    
# 또는

def solution(phone_book):
    phone_book.sort()
    for i in range(0, len(phone_book) - 1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

효율성 테스트 결과 (순서대로)

---

 사실 re 모듈이 캐싱을 수행한다는 파이썬 re 모듈 공식 문서에 언급되어 있으나, 나 포함 대부분의 사람들은 단순한 모듈의 경우 구글링으로 사용법 정도만 익히는 게 대부분이다. re 모듈이 Pattern 객체를 다루는 모든 함수들이 내부적으로 _compile 함수를 호출하여 캐싱의 대상이 된다는 말은 없으므로 당황스러울 수는 있지만 공식 문서를 읽은 상태였다면 이에 대한 유추는 가능했을 것이다. 그렇게 생각해 보니 역시 공식문서 정독보다 모듈을 이해하기 좋은 방법은 없는 것 같다. 

https://docs.python.org/ko/3/library/re.html#re.compile