Lua Academy · Lekcja

Memoizacja za pomocą domknięć

Proszę buforować wyniki kosztownych funkcji w tabeli przechowywanej przez domknięcie.

Memoizacja za pomocą domknięć to bezpłatna lekcja Lua Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Lua Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Lua Academy zawiera 4 lekcji w sumie.

Czym jest memoizacja?

Memoizacja buforuje wyniki kosztownych wywołań funkcji, dzięki czemu kolejne wywołania z tymi samymi argumentami natychmiast zwracają zapisany wynik.

Podstawowy wrapper memoizujący

Domknięcie przechowuje tabelę cache. Przy pierwszym wywołaniu oblicza i zapisuje wynik. Przy kolejnych zwraca zapisaną wartość.

local function memoize(fn)
  local cache = {}
  return function(x)
    if cache[x] == nil then
      cache[x] = fn(x)
    end
    return cache[x]
  end
end

Memoizowany algorytm Fibonacciego

Memoizacja rekurencyjnej funkcji Fibonacciego zmniejsza jej złożoność czasową z wykładniczej do liniowej.

local fib
fib = memoize(function(n)
  if n <= 1 then return n end
  return fib(n-1) + fib(n-2)
end)
print(fib(30))  -- 832040 (fast!)

Memoizacja wielu argumentów

W przypadku funkcji z wieloma argumentami należy utworzyć tekstowy klucz pamięci podręcznej ze wszystkich argumentów.

local function memoize2(fn)
  local cache = {}
  return function(a, b)
    local key = a .. "," .. b
    if cache[key] == nil then cache[key] = fn(a, b) end
    return cache[key]
  end
end

Zagnieżdżone tabele pamięci podręcznej

W przypadku różnych typów argumentów należy użyć zagnieżdżonych tabel, których kluczami są poszczególne argumenty, aby uzyskać wyszukiwanie O(1) bez serializacji do tekstu.

local function nestedMemo(fn)
  local cache = {}
  return function(a, b)
    cache[a] = cache[a] or {}
    if cache[a][b] == nil then cache[a][b] = fn(a, b) end
    return cache[a][b]
  end
end

Unieważnianie pamięci podręcznej

Memoizacja zakłada używanie funkcji czystych (bez efektów ubocznych i z takim samym wynikiem dla tych samych danych wejściowych). Funkcji z efektami ubocznymi nie należy memoizować bez starannego unieważniania pamięci podręcznej.

Memoizacja oparta na TTL

Należy dodać logikę czasu życia, używając os.time(), aby wygaszać wpisy w pamięci podręcznej.

local function memoizeTTL(fn, ttl)
  local cache = {}
  return function(x)
    local entry = cache[x]
    if entry and os.time() - entry.time < ttl then
      return entry.value
    end
    cache[x] = {value = fn(x), time = os.time()}
    return cache[x].value
  end
end

Pamięć podręczna ze słabymi wartościami

Należy użyć słabych wartości, aby wyniki zapisane w pamięci podręcznej mogły zostać usunięte przez garbage collector, gdy zaczyna brakować pamięci.

local function memoizeWeak(fn)
  local cache = setmetatable({}, {__mode = "v"})
  return function(x)
    if cache[x] == nil then cache[x] = fn(x) end
    return cache[x]
  end
end

Wzorzec memoizacji rekurencyjnej

W przypadku wzajemnie rekurencyjnych funkcji należy przypisać memoizujący wrapper przed użyciem go przez ciało rekurencyjne, aby rekurencja korzystała z pamięci podręcznej.

Ograniczona pamięć podręczna (szkic LRU)

Aby kontrolować zużycie pamięci, należy zaimplementować pamięć podręczną LRU, która usuwa najdawniej używany wpis po przekroczeniu maksymalnego rozmiaru.

Memoizacja w praktyce

Typowe zastosowania: kosztowne obliczenia matematyczne, buforowanie wyników zapytań do bazy danych, kompilowanie wzorców Lua oraz analizowanie plików konfiguracyjnych.

Pytanie o memoizację

Dlaczego memoizację należy stosować wyłącznie do funkcji czystych?

Podsumowanie: memoizacja

Memoizacja wykorzystuje przechowywaną w domknięciu pamięć podręczną do zapisywania wyników według klucza argumentów, eliminując zbędne obliczenia. Dla bezpieczeństwa pamięci należy używać słabych tabel, a dla pamięci podręcznych zależnych od czasu — dodawać TTL.

Często zadawane pytania

Czy lekcja „Memoizacja za pomocą domknięć” jest bezpłatna?

Tak — pełny tekst „Memoizacja za pomocą domknięć” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Lua Academy, przejdź na CoddyKit PRO. Kurs Lua Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Memoizacja za pomocą domknięć”?

Proszę buforować wyniki kosztownych funkcji w tabeli przechowywanej przez domknięcie. Ćwiczysz Lua Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Lua Academy?

Nie wymagamy żadnego doświadczenia. Lua Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Memoizacja za pomocą domknięć”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Lua Academy?

Tak. Każda lekcja Lua Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

Czym są upvalues?
Współdzielone upvalues między domknięciami
Funkcje fabrykujące i generatory
Memoizacja za pomocą domknięć

← Powrót do Lua Academy