lru_cache() & cache decorator

python study

파이썬의 문제

파이썬이 가진 가장 큰 장점이 범용성(다른 여러 언어들로 할 수 있는 일을 파이썬 하나로 할 수 있는 것)이라면, 가장 큰 약점은 아무래도 속도가 아닐까 싶다.

특히 간단한 전처리부터 이러한 처리 문제는 속을 썩이는 경우가 종종 있는데, 이럴 때면 분산처리 방식 등을 고민하게 된다. 오늘 리뷰할 것은 굳이 복잡한 분산처리 방식 등을 쓰지 않고도 가장 쉽게 성능을 개선시킬 수 있는 방법인데, 바로 functools 라이브러리에 있는 lru_cache를 사용하는 것이다.

lru_cache란?

해당 기능은 이름에서도 알 수 있듯 cache를 활용하는 기능이며, 구체적으로 여러 단계의 계산이 반복적으로 일어나는 것을 기억해두었다가 그 뒤의 연산을 보다 빠르게 하는 것이라 보면된다.

이러한 기능을 쓸 때 가장 중요한 것이 바로 주의사항을 먼저 확인하는 것인데, lru_cache를 통해 일반적인 전처리나 분석 코드 정도를 쓸때라면 몰라도 ML에 적용할 경우엔 메모리 문제를 반드시 고려해야 한다.

때문에 memory 제한을 두지 않는 cache보다는 lru_cache를 통해 어느정도의 cache memory를 허용할 것이지 정해두는 것이 필수적이다.

직접 해보기

실험 #1. Programmers 피보나치 수열 관련 문제

여러 단계의 계산이 순차적으로 일어나는 대표적인 연산 방식이 바로 피보나치 수열이다. 일반적으로 알고리즘 문제를 풀 때에는 이를 고려해 초기화된 값으로 적당히 긴 배열을 만들어 참고하는 식으로 사용하는데, 이러한 방식의 문제는 lru_cache를 통해 쉽게 해결할 수 있다.

만약 직접 풀어보고 싶다면 programmers 회원가입 및 로그인을 한 뒤, 피보나치 문제를 검색하거나 여기를 클릭해서 들어가면 된다.

쉽게 접근하기 위해 programmers의 피보나치 문제를 아주 기본적인 피보나치 수식을 통해 풀어보면 아래와 같은 결과를 얻게 된다.

기본적인 피보나치 수열을 사용했을 때의 결과

총 14개의 문제 중 6개만 맞췄고, 8개가 틀렸다.

틀린 8개 중 4개가 런타임 에러인데, 위 코드의 경우 특별히 이상한 라이브러리를 임포트했거나, 제한된 환경이 아니고, 위 함수의 특성을 고려했을 때, python에서 기본적으로 제한한 재귀횟수를 초과했을 것으로 예상된다.

이를 해결하기 위해 sys 라이브러리를 이용해 제한울 조금 늘려주면 아래와 같이 된다.

재귀제한을 늘려줬을 경우의 결과

의도한대로 이제 모든 틀린 문제가 '시간초과'로 뜬 것을 확인할 수 있다.

즉, 기본적인 피보나치 함수로는 문제를 적절한 시간 내에 해결할 수 없다는 것을 의미한다.

여기에 lru_cache를 이용해 문제를 해결할 수 있는지 확인해볼 수 있다.

lru_cache를 이용한 문제 해결

lru_cache를 decorator로 사용한 것만으로 문제가 해결됐다!

비록 아주 큰 숫자(즉, 반복)이 이뤄졌을 경우 보다 긴 시간과 메모리가 사용됐지만 그럼에도 사용하지 않았을때 대비 아주 큰 성능 차이를 보인다.

실험 #2. Jupyter Notebook에서 실행시간 직접 비교

이를 jupyter notebook 상에서 다시 확인해보면 아래와 같다. 우선 함수 정의 부분이다.

피보나치 수열 정의

programmers에서는 2 이상의 n이 들어올 경우, 1234567로 나눈 나머지를 출력하라고 했지만 여기선 편의를 위해 그냥 피보나치 수열만 출력한다. 위 함수의 성능을 확인해보면 아래와 같다.

두 함수의 성능차이

%%timeit을 통해 여러 번 반복해 평균적인 실행시간을 구했고, 그 결과는 2.51초 vs 55.5나노초로 lru_cache를 썼을 경우 약 45백만 배 빠르다!! (나노초는 10억분의 1초)

번외. Programmers 다른 방법 풀이

알고리즘 문제를 푸는 방법은 다양하다. 특히 이번 포스팅을 올리며 가장 거슬렸던 부분이 lru_cache를 사용했더니 매우 빠르게 문제를 해결할 수 있었지만, 거기에 들어가는 추가적인 메모리였다. (머신러닝 엔지니어라는 직군이 메모리 문제에 집착을 보이게 되는 것은 어쩔 수 없는 직업병 같은 게 아닐까)

그래서 좀 더 시간을 들여 메모리를 최적화하되, 문제를 빠르게 해결할 수 있는 다른 방법으로 코딩을 해봤다.

다른 방법의 문제 풀이

이 방법을 생각하기 위해 가장 어려웠던 건 피보나치라는 이름을 잊는 것이었는데, 포스팅의 목적이나 해당 문제의 이름에 대놓고 '피보나치'가 적혀있었기에 오히려 이를 고의적으로 배제하려고 하니 오히려 문제가 더 쉬워졌다. 

최종 코드

하지만 그 방식만큼은 기존의 lru_cache와도 비슷한 방법인데, 제시된 n만큼 for문을 반복하며 이후의 수를 기억(a)하는 방식이다. 특정 값을 1234567로 나눈 나머지와 다른 값을 더한 후 다시 구한 나머지의 합은 같으니 매계산마다 1234567을 해서 b가 너무 커지지 않도록 했다.

(실험결과 최종적으로 1234567을 나눠주는 것보다 더 적은 메모리와 더 빠른 실행시간이 소요됐다)

전체 코드는 github에 저장해두었다.

바로 이동하고 싶다면 클릭!