Kitap 01 · Programlamanın TemelleriSayfa 37 / 56

Memoization

Okunuşu: memoizeyşın

Güncellendi 30 Eylül 20262 dk okuma

Kısaca

Memoization, fonksiyon çağrılarının sonuçlarını saklayıp aynı girdiler tekrar geldiğinde kaydedilen sonucu döndüren bir optimizasyon tekniğidir.

Memoization nedir?

Memoization, bir fonksiyonu yanıtlarını hatırlatarak hızlandırma yöntemidir. Fonksiyon belirli bir argüman kümesiyle ilk kez çalıştığında sonucu hesaplar ve genellikle bu argümanlarla anahtarlanmış bir karma tablo (hash map) gibi bir arama tablosuna kaydeder. Aynı argümanlarla bir sonraki çağrıda işi yeniden yapmak yerine kaydedilen sonucu hemen döndürür.

Yalnızca saf fonksiyonlarda, yani aynı girdi için her zaman aynı çıktıyı veren ve bir veritabanına yazmak gibi yan etkileri olmayan fonksiyonlarda doğru çalışır. Klasik örnek özyinelemeli Fibonacci fonksiyonudur: memoization olmadan aynı değerleri defalarca yeniden hesaplayarak üstel sayıda çağrı yapar; memoization ile her değer bir kez hesaplanır ve çalışma süresi doğrusal, yani O(n) düzeyine düşer. Memoization, dinamik programlamanın yukarıdan aşağıya (top-down) biçimidir.

Zor bir matematik probleminin yanıtını bir yapışkan nota yazmak gibidir; bir dahaki sefere biri sorduğunda notu okumanız yeter. Memoization, Python'un functools.cache dekoratörü ile React'in useMemo hook'u ve memo fonksiyonu gibi birçok araca yerleşiktir; bunlar, girdileri değişmediğinde değerleri yeniden hesaplamayı ya da bileşenleri yeniden oluşturmayı atlar.

Memoization, önbelleklemenin belirli bir türüdür. Önbellekleme, pahalı herhangi bir sonucu yeniden kullanmak üzere saklamanın geniş fikridir; çoğunlukla sunucular arasında paylaşılır ve zamanla geçerliliğini yitirir. Memoization ise bir fonksiyonun dönüş değerlerini genellikle tek bir işlemin içinde bellekte önbelleğe alır. Ödün bellektir: her sonucu saklamak sınırsız büyüyebilir, bu yüzden birçok memoize edilmiş fonksiyon yalnızca en son girdileri tutar.

Önemli noktalar

Memoization, bir fonksiyonun sonuçlarını saklar ve tekrarlanan girdiler için yeniden kullanır.
Yalnızca yan etkisi olmayan saf fonksiyonlar için güvenlidir.
Naif Fibonacci gibi üstel özyinelemeli algoritmaları doğrusal hâle getirebilir.
Daha az hesaplama karşılığında ek bellek harcar.
Memoization, fonksiyon çağrılarına uygulanan dar bir önbellekleme biçimidir.

Örnek

JavaScript'te elle yazılmış bir memoize yardımcısıjavascript

function memoize(fn) {
  const cache = new Map();
  return (n) => {
    if (cache.has(n)) return cache.get(n); // reuse a saved result
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
}

const fib = memoize((n) => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
console.log(fib(50)); // 12586269025, with each fib(n) computed only once
// Without memoization, fib(50) would take about 40 billion calls

Sık sorulan sorular

Memoization ile önbellekleme (caching) arasındaki fark nedir?

Memoization, bir fonksiyonun dönüş değerlerini argümanlarıyla anahtarlayarak genellikle bellekte saklayan özel bir önbellekleme türüdür. Önbellekleme ise daha geniş bir fikirdir ve HTTP yanıtlarını, veritabanı sorgularını ve dosyaları da kapsar; çoğunlukla geçerlilik süreleri ve paylaşılan depolama içerir.

Memoization ile dinamik programlama arasındaki fark nedir?

Dinamik programlama, örtüşen alt sorunların çözümlerini birleştirerek bir sorunu çözer. Memoization, bunu özyinelemeli bir fonksiyona önbellek ekleyerek yapmanın yukarıdan aşağıya yoludur; tablolama (tabulation) ise bir tabloyu adım adım dolduran aşağıdan yukarıya yoldur.

Memoization ne zaman kullanılmamalıdır?

Yan etkileri olan ya da geçerli saat gibi değişen verilere bağlı sonuçlar üreten fonksiyonlar için ve ucuz olan ya da aynı girdilerle nadiren çağrılan fonksiyonlar için kaçının. Bu durumlarda ek bellek ve aramalar, kazandırdığından fazlasına mal olur.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin