간단히 메모이제이션

메모이제이션은 어떤 문제를 해결합니까?
한마디로 비효율을 방지합니다.

왜

코드는 당신이 생각하는 것만큼 훌륭하지 않습니다. 때로는 작업을 수행하기 위해 계속해서 작업을 반복해야 합니다.

메모이제이션의 좋은 아이디어는 불필요한 계산을 피하는 것입니다. 프로그램이 이미 작업을 완료했으므로 결과를 저장해 보겠습니다. 동일한 것을 메모리에 반복적으로 계산하는 대신 나중에 사용하기 위해 저장합니다.

이것이 바로 캐싱의 개념입니다. 스크립트에 이전 작업이 필요한 경우 다음 작업이 발생하는 경우 메모이제이션에 적합한 후보입니다.

순수 기능 및 면책 조항

메모이제이션 기법을 적용하려면 순수 함수가 필요합니다. 이러한 함수는 상태를 조작하지 않으며 부작용이 없습니다. 그들은 항상 같은 입력에 대해 같은 결과를 반환합니다. 그 이상은 아닙니다.

모든 함수가 순수해야 하는 것은 아니라는 점에 유의하는 것이 중요합니다. 메모이제이션이 비생산적인 경우도 있습니다.

심플한 패턴

다음은 JavaScript의 매우 간단한 예입니다.

const myFunction = function(param) {
   if (!myFunction.memo[ param ]) {
       let outcome = {};// here is your operation instead
       myFunction.memo[ param ] = outcome;
   }
   return myFunction.memo[ param ];
};

myfunction.memo = {};

결과가 이미 사용 가능한 경우 코드는 계산을 건너뜁니다.

재귀

재귀는 조금 더 복잡하지만 메모이제이션 기술의 이점을 활용할 수 있습니다.

이미 알고 계시겠지만 재귀 함수는 스스로를 호출합니다. 일반적으로 특정 경우에 재귀를 종료하는 조건이 있습니다. 재귀 부분은 다른 모든 경우에 발생합니다.

다음은 Python의 예입니다.

def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

계산이 비쌉니다. 여러 작업을 여러 번 수행하기 때문에 발생합니다.

왜 이렇게이다?
fibo(2) 실행 fibo(1) . fibo(3)는 fibo(2) 및 fibo(1)를 실행하지만 fibo(2)는 fibo(1)도 실행합니다.
그런 조건에서 fibo(2000) 영원히 걸릴 것입니다 ...

캐시하자:

fiboCache = {}

def fibo(n):
    if n in fiboCache:
        return fiboCache[ n ]
    if n < 2:
        value = 1
    else:
       value =  fibo(n - 1) + fibo(n - 2)
       fiboCache[ n ] = value
    return value

우리는 값을 저장하기 위해 사전을 사용합니다. 이 최적화는 방대합니다. 스크립트가 없으면 스크립트를 실행하는 데 많은 시간과 메모리가 소요됩니다. 작은 숫자를 입력으로 사용하지 않는 한 메모리를 죽일 수 있지만 이 경우 함수를 사용하는 것은 거의 관심이 없습니다.

미친 범위로 부스트fibo를 테스트할 수 있습니다.

for i in range(1, 2000):
     print(fibo(i))

포장하다

메모이제이션에 대한 이 짧은 소개를 즐기시기 바랍니다. 대부분의 언어로 사용할 수 있으므로 주저하지 말고 적절하게 사용하십시오.