[SW 정글 29일차] @lru_cache

오늘은 이번 주에 같은 조가 된 동료가 알고리즘 문제를 풀면서 사용했다는 @lru_cache라는 것을 알아보려고 한다.

외장 라이브러리를 불러와서 쓰는 것이여서 코테에서 막힐 수도 있지만 알아두면 좋은 것같다.

 

 

 

1. functools 모듈

@lru_cache는 functools 모듈에 속해있는 데코레이터이다.

그러면 @lru_cache를 알아보기 전에 functools 모듈에 대해 알아보자.

 

functools 모듈은 python 표준 라이브러리 중 하나로 고차함수(함수를 반환하거나 다른 함수를 인수로 사용하는 함수)로 작업하기 쉽게 해주는 기능을 제공한다.

공식문서 상에는 functools 모듈에 12개의 데코레이터가 정의되어 있고 오늘 알아볼 lru_cache를 제외하고 다른 것들도 알아보고 싶다면 공식문서를 보면 좋을 것같다.

데코레이터란 어떠한 함수를 받아 미리 정의된 명령을 추가한 뒤에 다시 함수의 형태로 반환하는 함수이다.
원래 함수의 내부를 수정하지 않고 기능에 변화를 주고 싶을 때 사용하고 일반적으로 함수의 전처리나 후처리에 대한 필요가 있을때 사용을 한다. 또한 데코레이터를 이용하여 반복을 줄이고 메소드나 함수의 책임을 확장한다.

https://docs.python.org/3/library/functools.html

functools — Higher-order functions and operations on callable objects — Python 3.9.6 documentation

 

 

 

2. @lru_cache 알아보기

@lru_cache 데코레이터는 가장 최근의 maxsize 호출까지 memoizing하는 callable 함수를 감싸는 역할을 한다.

간단히 말해서 어떠한 함수의 리턴결과를 캐시해주는 데코레이터이다.

최초 요청 이후에 똑같은 요청이 들어오면 캐시된 결과를 리턴한다.

맨 처음에 말하는 maxsize는 @lru_cache(maxsize=128, typed=False)에서 매개값으로 받는 것으로 기본값은 128이고 None으로 설정하면 LRU 기능이 비활성화되고 캐시가 제한없이 커질 수 있다.

maxsize로 정한 최대크기를 초과할 경우에는 호출빈도가 가장 작은 것부터 캐시에서 자동으로 사라진다.

여기서 호출빈도가 낮다는 것을 판단하는 기준은 가장 최근에 참조되지 않은 데이터를 말한다.

lru_cache를 사용하게 되면 같은 인자를 갖는 함수가 주기적으로 호출될 경우에 시간을 절약할 수 있다.

 

maxsize말고 typed라는 매개변수를 받는데 기본값은 False이고 True로 설정해주면 다른 형의 함수 인자를 별도의 캐시로 저장한다는 것이다.

예를 들어, f(3)과 f(3.0)이 요청되면 둘은 다른 자료형이므로 각각 캐시된다는 것이다.

 

lru_cache 데코레이터에서 제공하는 함수는 아래와 같다.

- cache_parameters()

cache_parameters()는 @lru_cache 데코레이터로 wrapping된 함수에 적용된 maxsize와 typed의 값을 딕셔너리형태로 반환해주는 역할을 한다.

 

- cache_info()

 wrapping된 함수에 대한 hits, misses, maxsize , currsize의 값을 표시하는 네임드 튜플을 반환해주는 역할을 한다.

hits는 캐시에 저장된 함수의 결과를 사용한 횟수, misses는 캐시에 일치하는 경우가 없어서 함수가 실행된 횟수, maxsize는 설정한 maxsize값, currsize는 현재의 캐시저장용량을 말해준다.

 

두 함수는 아래의 @lru_cache를 사용한 예제에서 어떻게 값이 반환되는지 알아보면 이해가 더 잘 될것이다.

 

 

 

3. @lru_cache 사용해보기

@lru_cache는 같은 매개값을 가지는 함수가 주기적으로 호출될 때 시간을 절약할 수 있으므로 재귀함수에서 유용할 수 있고 재귀함수를 사용하는 알고리즘은 많지만 그 중에서 DP로 접근하는 문제에 적용해보려고 한다.

DP의 대표적인 문제인 피보나치 수열을 예제로 사용해보자.

 

dp_table = [1, 1, 1] + [0] * n

def fibonacci(x):
    if dp_table[x] != 0:
        return dp_table[x]
    
    dp_table[x] = fibonacci(x - 1) + fibonacci(x - 2)
    return dp_table[x]

top-down방식으로 접근하여 중복되어 나오는 계산에는 dp에 memoization한 값을 리턴해주는 형식이다.

 

그러면 memozation한 dp_table을 제거하고 @lru_cache로 wrapping을 해보자.

 

import functools

@functools.lru_cache()
def fibo(n):
    if n < 2:
        return n
    
    return fibo(n - 1) + fibo(n - 2)

 

 

실행시간을 측정하여 얼마나 시간이 절약되는지 알아보자.

 

import time
import functools
import sys

sys.setrecursionlimit(10**8)
n = 1500

start = time.time()
dp_table = [1, 1, 1] + [0] * n

def fibonacci(x):
    if dp_table[x] != 0:
        return dp_table[x]
    
    dp_table[x] = fibonacci(x - 1) + fibonacci(x - 2)
    return dp_table[x]

fibonacci(n)
print('dp memoization time: ', '%.8f' %(time.time() - start))


start = time.time()
@functools.lru_cache(maxsize = 1000)
def fibo(n):
    if n < 2:
        return n
    
    return fibo(n - 1) + fibo(n - 2)

fibo(n)
print('lru_cache time: ', '%.8f' %(time.time() - start))

# 결과
# dp memoization time:  0.00598812
# lru_cache time:  0.00201440

그래도 0.003초면 컴퓨터에서는 큰 차이지 않을까?

 

 

마지막으로 위에서 말한 lru_cache에서 제공하는 2가지 함수의 결과를 알아보고 마치려고 한다.

- cache_parameters()

cache_parameters()는 @lru_cache 데코레이터로 wrapping된 함수에 적용된 maxsize와 typed의 값을 딕셔너리형태로 반환해주는 역할을 한다.

 

- cache_info()

 wrapping된 함수에 대한 hits, misses, maxsize , currsize의 값을 표시하는 네임드 튜플을 반환해주는 역할을 한다.

hits는 캐시에 저장된 함수의 결과를 사용한 횟수, misses는 캐시에 일치하는 경우가 없어서 함수가 실행된 횟수, maxsize는 설정한 maxsize값, currsize는 현재의 캐시저장용량을 말해준다.

import functools

@functools.lru_cache(maxsize = 1000)
def fibo(n):
    if n < 2:
        return n
    
    return fibo(n - 1) + fibo(n - 2)


print(fibo.cache_info())
# 결과 CacheInfo(hits=33, misses=36, maxsize=1000, currsize=36)
                
print(fibo.cache_parameters())
# 결과 {'maxsize': 1000, 'typed': False}

---

[오늘의 나는 어땠을까?]

오늘은 아침부터 저녁먹기 전까지는 계획한대로 공부를 했지만 저녁을 먹고 난 후에는 집중을 잘 못했다.

왜 그랬을까...

그래도 알고리즘 코드 리뷰도 하고 동료의 질문을 답변해주면서 이미 경험한 문제들을 더 내 것으로 만드는 좋은 시간을 가졌지만 계획적이지 못했다.

 

그리고 요즘 너무 심란해진 것같다.

들어오기 전에 개발자가 되기 위해서는 비전공자로서 준비해야할 것이 너무 많다는 큰 걱정이 있었고 여기와서도 초반에는 그러한 걱정이 있었지만 일주일만에 사라지고 주어진 과제에만 열중했다.

하지만, 3주차부터 조금 여유를 느끼면서 타이트하지 않아 해이해져 낭비되는 시간이 있다는 것을 느꼈고 자료구조나 알고리즘을 딥하게 공부하고 남은시간과 아침 시간의 활용도를 높이고자 다른 공부를 몇 일전부터 시작했다.

다른 공부에 어느정도 시간을 투자하니 또 다시 정글에 들어오기 전에 했던 걱정, 알아야할 것과 공부할 것이 너무 많다는 생각이 들었다.

 

계속해서 나는 아직 부족하고 빨리 개발자가 되어 커리어를 시작하고 싶고 시간을 부족하다고 느끼고..

이러한 걱정이 계속되던 중에 오후에 코치님과의 티타임과 저녁 10시쯤 1기 수료생과 메일을 주고받으면서 다시 정신을 잡을 수 있었다.

내가 지금 집중해야 할 것은 그냥 지금 당장 내 눈앞에 주어진 것이고 시간이 남는다면 더 깊게, 궁금증이 모두 해결될 때까지 투자하는 것이다.

1기 교육생들은 주어진 것이외에 스터디를 진행했다는 소식을 들은 후에 나도 뭔가 다른 것을 해야한다는 압박감?이 느껴져서 잠시 다른 곳에 한 눈 팔았지만 이 시간 이후로 다시 돌아오고자 한다.

 

집중, 계획, 목표지향, 꾸준함

---

<참고 자료>

https://ichi.pro/ko/python-ui-functools-modyul-sogae-3044253398862

https://thrillfighter.tistory.com/399