Apa itu memoisasi dan bagaimana saya bisa menggunakannya dengan Python?

Saya baru saja memulai Python dan saya tidak tahu apa itu memoisasi dan bagaimana menggunakannya. Juga, bolehkah saya memiliki contoh sederhana?

Memoisasi secara efektif mengacu pada mengingat ("memoisasi" → "memorandum" → untuk diingat) hasil pemanggilan metode berdasarkan input metode dan kemudian mengembalikan hasil yang diingat daripada menghitung hasilnya lagi. Anda dapat menganggapnya sebagai cache untuk hasil metode. Untuk perincian lebih lanjut, lihat halaman 387 untuk definisi dalam Pengantar Algoritma (3e), Cormen et al.

Contoh sederhana untuk menghitung faktorial menggunakan memoisasi dengan Python akan menjadi seperti ini:

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]

Anda bisa menjadi lebih rumit dan merangkum proses memoisasi ke dalam kelas:

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]

Kemudian:

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

factorial = Memoize(factorial)

Fitur yang dikenal sebagai " dekorator " telah ditambahkan dalam Python 2.4 yang memungkinkan Anda untuk sekarang cukup menulis yang berikut untuk mencapai hal yang sama:

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

The Python dekorator Perpustakaan memiliki dekorator serupa yang disebut memoizedyang sedikit lebih kuat dari Memoizekelas yang ditampilkan di sini.

Baru untuk Python 3.2 adalah functools.lru_cache. Secara default, hanya cache panggilan 128 yang terakhir digunakan, tapi Anda dapat mengatur maxsizeuntuk Noneuntuk menunjukkan bahwa cache tidak harus berakhir:

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Fungsi ini dengan sendirinya sangat lambat, coba fib(36)dan Anda harus menunggu sekitar sepuluh detik.

Menambahkan lru_cacheanotasi memastikan bahwa jika fungsi baru-baru ini dipanggil untuk nilai tertentu, itu tidak akan menghitung ulang nilai itu, tetapi menggunakan hasil sebelumnya yang di-cache. Dalam hal ini, ini mengarah pada peningkatan kecepatan yang luar biasa, sementara kode tidak berantakan dengan detail caching.

Jawaban lainnya mencakup apa yang cukup baik. Saya tidak mengulanginya. Hanya beberapa poin yang mungkin bermanfaat bagi Anda.

Biasanya, memoisasi adalah operasi yang dapat Anda terapkan pada fungsi apa pun yang menghitung sesuatu (mahal) dan mengembalikan nilai. Karena itu, ini sering diterapkan sebagai dekorator . Implementasinya sangat mudah dan akan seperti ini

memoised_function = memoise(actual_function)

atau diekspresikan sebagai dekorator

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

Memoisasi adalah menjaga hasil perhitungan yang mahal dan mengembalikan hasil yang di-cache daripada terus-menerus menghitung ulang.

Ini sebuah contoh:

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

Deskripsi yang lebih lengkap dapat ditemukan di entri wikipedia tentang memoisasi .

Jangan lupa hasattrfungsi bawaan, untuk mereka yang ingin kerajinan tangan. Dengan begitu Anda dapat menyimpan cache mem di dalam definisi fungsi (sebagai lawan global).

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]

Saya menemukan ini sangat berguna

def memoize(function):
    from functools import wraps

    memo = {}

    @wraps(function)
    def wrapper(*args):
        if args in memo:
            return memo[args]
        else:
            rv = function(*args)
            memo[args] = rv
            return rv
    return wrapper


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

fibonacci(25)

Memoisasi pada dasarnya menyimpan hasil operasi masa lalu yang dilakukan dengan algoritma rekursif untuk mengurangi kebutuhan untuk melintasi pohon rekursi jika perhitungan yang sama diperlukan pada tahap selanjutnya.

lihat http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Contoh Memoisasi Fibonacci dengan Python:

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]

Memoisasi adalah konversi fungsi menjadi struktur data. Biasanya orang ingin konversi terjadi secara bertahap dan malas (berdasarkan permintaan elemen domain tertentu - atau "kunci"). Dalam bahasa fungsional malas, konversi malas ini dapat terjadi secara otomatis, dan dengan demikian memoisasi dapat diimplementasikan tanpa efek samping (eksplisit).

Baiklah saya harus jawab bagian pertama dulu: apa itu memoisasi?

Itu hanya metode untuk menukar memori untuk waktu. Pikirkan Tabel Multiplikasi .

Menggunakan objek yang dapat diubah sebagai nilai default dalam Python biasanya dianggap buruk. Tetapi jika menggunakannya dengan bijak, itu sebenarnya bisa berguna untuk mengimplementasikan memoization.

Berikut ini contoh yang diadaptasi dari http://docs.python.org/2/faq/design.html#why-are-default-values-share-between-objects

Menggunakan bisa berubah dictdalam definisi fungsi, hasil yang dihitung menengah dapat di-cache (misalnya ketika menghitung factorial(10)setelah menghitung factorial(9), kami dapat menggunakan kembali semua hasil menengah)

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

Berikut ini adalah solusi yang akan bekerja dengan daftar atau jenis argumen tanpa merengek:

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

Perhatikan bahwa pendekatan ini dapat diperluas secara alami ke objek apa pun dengan menerapkan fungsi hash Anda sendiri sebagai kasus khusus di handle_item. Misalnya, untuk membuat pendekatan ini berfungsi untuk fungsi yang mengambil set sebagai argumen input, Anda bisa menambahkan ke handle_item:

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

Solusi yang berfungsi dengan argumen posisi dan kata kunci secara terpisah dari urutan penetapan arg kata kunci (menggunakan 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

Pertanyaan serupa: Mengidentifikasi panggilan fungsi varargs setara untuk memoisasi dengan Python

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]

Hanya ingin menambah jawaban yang sudah disediakan, pustaka dekorator Python memiliki beberapa implementasi sederhana namun bermanfaat yang juga dapat memo "tipe yang tidak dapat dihancurkan", tidak seperti functools.lru_cache.