메모화는 무엇이며 Python에서는 어떻게 사용할 수 있습니까?

메모화는 무엇이며 Python에서는 어떻게 사용할 수 있습니까?

Python을 시작한 지 얼마 되지 않았는데 메모화가 무엇인지, 어떻게 사용하는지 전혀 모르겠습니다.또, 간단한 예를 들어 주시겠습니까?

메모화는 메서드 입력에 따라 메서드 호출의 결과를 기억("각서"→기억해야 할 것)한 후 다시 계산하지 않고 기억된 결과를 반환하는 것을 말한다.메서드 결과의 캐시라고 생각할 수 있습니다.자세한 내용은 알고리즘 소개(3e), Cormen 등에서의 정의에 대해서는 387페이지를 참조해 주십시오.

Python의 메모화를 사용한 계산 요소의 간단한 예는 다음과 같습니다.

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

메모화 프로세스를 클래스로 캡슐화할 수 있습니다.

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

그 후, 다음과 같이 입력합니다.

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

factorial = Memoize(factorial)

Python 2.4에는 "디코레이터"라고 하는 기능이 추가되어 있습니다.이 기능을 사용하면, 다음의 내용을 간단하게 작성할 수 있습니다.

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

Python Decorator Library는 Python Decorator Library보다 약간 더 견고한 데코레이터를 가지고 있습니다.Memoize를 참조해 주세요.

functools.cache데코레이터:

Python 3.9는 새로운 기능을 출시했습니다.특정 인수 세트(메모화)를 사용하여 호출된 함수의 결과를 메모리에 캐시합니다.사용하기 쉽다:

import functools
import time

@functools.cache
def calculate_double(num):
    time.sleep(1) # sleep for 1 second to simulate a slow calculation
    return num * 2

처음 전화했을 때caculate_double(5)1초 정도 걸리고 10초 정도 걸립니다.같은 인수로 함수를 두 번째로 호출할 때calculate_double(5), 즉시 10이 반환됩니다.

추가cache데코레이터는 함수가 특정 값에 대해 최근에 호출된 경우 해당 값을 재계산하지 않고 캐시된 이전 결과를 사용합니다.이 경우 속도가 크게 향상되고 코드가 캐싱 세부 사항으로 복잡해지지 않습니다.

(편집: 앞의 예에서는 재귀를 사용하여 fibonacci 수를 계산했는데, 혼란을 방지하기 위해 예제를 변경했기 때문에 오래된 코멘트가 있습니다).

functools.lru_cache데코레이터:

이전 버전의 Python을 지원해야 하는 경우 Python 3.2+에서 작동합니다.디폴트로는 가장 최근에 사용한 128개의 콜만 캐시되지만maxsize로.None캐시가 만료되지 않음을 나타냅니다.

@functools.lru_cache(maxsize=None)
def calculate_double(num):
    # etc

---

다른 답변들은 그것이 무엇인지 꽤 잘 다루고 있다.난 그걸 반복하지 않을게요.도움이 될 만한 몇 가지 사항만 말씀드리겠습니다.

일반적으로 메모화는 무언가를 계산하고 값을 반환하는 함수에 적용할 수 있는 작업입니다.이 때문에 데코레이터로 구현되는 경우가 많습니다.구현은 간단하며 다음과 같습니다.

memoised_function = memoise(actual_function)

데코레이터로서 표현된 것.

@memoise
def actual_function(arg1, arg2):
   #body

나는 이것이 매우 유용하다는 것을 알았다.

from functools import wraps


def memoize(function):    
    memo = {}
        
    @wraps(function)
    def wrapper(*args):

        # add the new key to dict if it doesn't exist already  
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper
    
    
@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
fibonacci(25)

메모화는 고가의 계산 결과를 보관하고 캐시된 결과를 지속적으로 재계산하는 것이 아니라 반환하는 것입니다.

다음은 예를 제시하겠습니다.

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

보다 자세한 설명은 위키피디아 메모 항목에서 찾을 수 있습니다.

기본 제공 기능을 잊지 마십시오.hasattr수공예품을 원하는 분들을 위한 기능.이렇게 하면 (글로벌과는 달리) 함수 정의 내에 mem 캐시를 유지할 수 있습니다.

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]

메모화는 기본적으로 재귀 알고리즘으로 수행된 과거 작업의 결과를 저장하여 나중에 동일한 계산이 필요할 때 재귀 트리를 통과할 필요성을 줄이는 것입니다.

http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/ 를 참조해 주세요.

Python에서의 Fibonacci 메모화의 예:

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]

메모화는 함수를 데이터 구조로 변환하는 것입니다.일반적으로 변환은 (특정 도메인 요소 또는 "키"의 요구에 따라) 서서히 진행되기를 원합니다.느린 기능 언어에서는 이 느린 변환이 자동으로 이루어지기 때문에 (명시적인) 부작용 없이 메모화가 구현될 수 있습니다.

첫 번째 부분은 메모화란 무엇인가?

그것은 단지 시간과 기억을 교환하는 방법일 뿐이다.구구단을 생각해 보세요.

Python에서 변경 가능한 개체를 기본값으로 사용하는 것은 일반적으로 좋지 않은 것으로 간주됩니다.하지만 현명하게 사용한다면, 실제로 이 기능을 구현하는 것이 유용할 수 있습니다.memoization.

다음은 http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects에서 개작한 예입니다.

가변 사용dict함수 정의에서 중간 계산 결과를 캐시할 수 있습니다(예: 계산 시).factorial(10)계산 후factorial(9)모든 중간 결과를 재사용할 수 있습니다.)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]

다음은 list 인수 또는 dict type 인수와 연동되는 솔루션입니다.

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

이 접근방식은 handle_item의 특수한 경우로서 독자적인 해시함수를 구현함으로써 자연스럽게 임의의 오브젝트로 확장할 수 있습니다.예를 들어, 입력 인수로 집합을 사용하는 함수에 대해 이 방법을 사용하려면 handle_item에 추가할 수 있습니다.

if is_instance(x, set):
    return make_tuple(sorted(list(x)))

키워드 arg가 전달된 순서와는 독립적으로 positional 인수와 키워드 인수 모두에서 동작하는 솔루션(inspect.getargspec 사용):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

유사한 질문:Python에서 메모화를 요구하는 동등한 varargs 함수를 식별하는 것

Python 데코레이터 라이브러리는 이미 제공된 답변에 추가하고 싶었을 뿐인데, 다음과 같이 "해시 불가능한 유형"을 메모할 수 있는 단순하지만 유용한 구현이 있습니다.functools.lru_cache.

cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]

속도를 고려하는 경우:

• @functools.cache그리고.@functools.lru_cache(maxsize=None)마찬가지로 고속으로 시스템에서 백만 번 루프하는 데 0.15초(15회 실행 중 베스트)가 소요됩니다.
• 글로벌 캐시 변수가 상당히 느려서 시스템에서 100만 번 루프하는 데 0.180초(15회 실행 중 베스트)가 소요됩니다.
• a self.cacheclass 변수는 아직 조금 느립니다.시스템에서 루프를 백만 번 반복하는 데 0.214초(15회 실행 중 베스트)가 소요됩니다.

후자의 두 가지는 현재 가장 많이 인용된 답변에서 설명된 방법과 유사하게 구현됩니다.

이는 메모리 소모를 방지하는 기능이 없습니다.에 코드를 추가하지 않았습니다.class또는global캐시의 크기를 제한하는 방법, 이것이 바로 베어본 구현입니다.그lru_cachemethod에는 무료로 제공됩니다.

저에게 한가지 미해결 질문은 어떻게 하면 이 시스템이 어떤 기능을 가지고 있는지functools데코레이터어떻게 해서든 캐시를 비울 수 있을까요?단위 테스트는 클래스 메서드(각 테스트의 새 클래스를 인스턴스화할 수 있음) 또는 두 번째로 글로벌 변수 메서드(다음 작업을 수행할 수 있음)를 사용하여 가장 깨끗한 것으로 보입니다.yourimportedmodule.cachevariable = {}★★★★★★★★★★★★★★★★★」

언급URL : https://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python