Apa perbedaan antara Caching dan Memoization?

114

Saya ingin tahu apa perbedaan sebenarnya antara cachingdan memoization.
Seperti yang saya lihat, keduanya melibatkan menghindari panggilan fungsi berulang untuk mendapatkan data dengan menyimpannya .

Apa perbedaan inti antara keduanya?

caching terminology memoization John
sumber
Saya ingin tahu apakah Anda bisa mengatakan "memoization is to caching" sebagai "array is to sparse array". Dengan kata lain, Anda hanya menyimpan barang "sesuai permintaan" daripada menghitung setiap kombinasi masukan yang mungkin.
Sridhar Sarnobat

Jawaban:

110

Memoization adalah bentuk khusus dari caching yang melibatkan caching nilai kembalian suatu fungsi berdasarkan parameternya .

Caching adalah istilah yang lebih umum; misalnya, cache HTTP adalah cache tetapi bukan memoisasi.

Wikipedia mengatakan :

Meskipun terkait dengan caching, memoization mengacu pada kasus spesifik dari pengoptimalan ini, membedakannya dari bentuk caching seperti buffering atau penggantian halaman.

SLaks
sumber
2
tetapi Anda selalu dapat melewati bagian di mana cache digunakan dengan suatu fungsi dan menamakannya 'memoization'. meskipun perbedaannya adalah Anda mengendalikan kebijakan caching di fungsi Anda, sedangkan memoization adalah urutan yang lebih tinggi dan terjadi di luar fungsi.
nicolas
Mengapa Caching HTTP bukan hafalan? yang juga didasarkan pada parameter (URL sumber daya yang diminta).
topo Kembalikan Monica
@topomorto: Karena fitur suka If-Matchdan kedaluwarsa. Memoisasi hanya masuk akal untuk fungsi murni, yang jarang dimiliki HTTP.
SLaks
@ Nicolas, kurasa kurang tepat. Saya pikir dalam memoization istilah "fungsi" digunakan dalam arti murni / matematis. Mengunduh halaman web dari alamat tertentu tidak dapat dianggap sebagai fungsi, karena mungkin saja halaman tersebut berubah.
Alexey
@Alexey bukankah pernyataan yang sama berlaku untuk cache? semua strategi tersebut bergantung pada pemanggilan fungsi yang sama yang memberikan hasil yang sama, alias tidak ada efek samping upstream .
nicolas
47

Seperti yang telah saya lihat digunakan, "memoization" adalah "menyimpan hasil dari fungsi deterministik" yang dapat direproduksi kapan saja dengan fungsi dan masukan yang sama.

"Caching" pada dasarnya mencakup strategi buffering keluaran, baik nilai sumber dapat direproduksi atau tidak pada waktu tertentu. Faktanya, caching juga digunakan untuk merujuk pada strategi buffering input , seperti cache-tulis pada disk atau memori. Jadi ini adalah istilah yang jauh lebih umum.

harpo
sumber
Apakah Anda yakin bahwa fungsinya harus deterministik?
Gherman
4
@Jerman, ya, memoization tergantung determinisme. Contoh klasiknya adalah algoritma rekursif, seperti deret Fibonacci atau faktorial. Alih-alih menghitung ulang sampai ke kasus dasar, fungsi memo akan mengalami korsleting dengan menggunakan kembali hasil sebelumnya untuk nilai yang sudah dihitung. Ini jelas tergantung pada input yang sama yang selalu menghasilkan output yang sama, yang merupakan definisi determinisme. Caching, di sisi lain, sering digunakan untuk proses non-deterministik (misalnya acak atau timestamped), dengan pemahaman bahwa hasil mungkin tidak cocok dengan nilai yang "diperbarui".
harpo
6

Saya pikir istilah caching biasanya digunakan ketika Anda menyimpan hasil operasi IO, atau pada dasarnya data apa pun yang datang kepada Anda dari luar (file, jaringan, kueri db). Memo istilah biasanya berlaku untuk menyimpan hasil perhitungan Anda sendiri, misalnya dalam konteks pemrograman dinamis.

MK.
sumber
1

Memoization adalah bentuk khusus dari caching hasil dari fungsi deterministik. Artinya, hasil caching di luar fungsi bukanlah memoization karena fungsi tersebut harus mengubah cache saat menghitung hasil baru (belum ada di cache) sehingga tidak akan menjadi fungsi (murni) lagi. Memoization umumnya menyiratkan penerusan cache sebagai argumen tambahan (dalam fungsi helper). Memoisasi akan mengoptimalkan fungsi yang perlu menghitung nilai beberapa kali untuk satu akses. Caching akan mengoptimalkan fungsi yang dipanggil beberapa kali dengan parameter yang sama. Dengan kata lain, Memoisasi akan mengoptimalkan akses pertama apakah caching hanya akan mengoptimalkan akses berulang.

Pierre-Yves Saumont
sumber
0

Saya ingin menambahkan jawaban bagus lainnya bahwa memoization juga dikenal sebagai tabling . Saya rasa penting juga untuk mengetahui istilah itu bagi mereka yang mempelajari apa itu memoization dan caching.

VS
sumber