Seluk-beluk penerapan memoisasi di Ruby

Dalam upaya tanpa akhir untuk menulis kode yang berkinerja baik, kami memiliki banyak teknik yang dapat kami gunakan. Salah satu teknik tersebut adalah memoisasi,^{11 Itu adalah menghafal, bukan menghafal — tidak ada “r”! yang intinya adalah menyimpan hasil pemanggilan fungsi yang mahal, sehingga fungsi mahal tersebut tidak perlu dipanggil lebih dari yang diperlukan.}

Bertahun-tahun yang lalu, saya menulis permata Ruby untuk memoisasi, ddmemoize. Sejak itu telah digantikan oleh solusi yang lebih baik, tetapi untuk waktu yang lama, ini adalah salah satu perpustakaan memoisasi terbaik untuk Ruby yang ada.

Membuat perpustakaan ini mengajari saya banyak hal. Memoisasi ternyata sangat rumit, dan implementasi yang tepat ternyata jauh melampaui Ruby ||= operator memoisasi. Manajemen memori dan keamanan thread, misalnya, merupakan pertimbangan penting, meski sering diabaikan.

Dalam artikel ini, saya akan memandu Anda melalui semua pembelajaran yang saya peroleh dalam proses penerapan permata memoisasi ini.

1. Variabel lokal
2. Operator memoisasi
   1. Hati-hati dengan false dan nihil
3. Memoisasi yang sadar argumen
4. Memoisasi DSL
   1. Persyaratan memoisasi
5. Menghafal benda beku
6. Memoisasi hemat memori
   1. Referensi yang lemah
   2. Referensi lembut
   3. Membekukan, ditinjau kembali
7. Mendukung argumen kata kunci
8. Blok pendukung
9. Memoisasi yang aman untuk thread
10. Metrik
11. Kesimpulan

Variabel lokal

Alat paling sederhana yang kita miliki untuk mengingat nilai adalah konsep variabel lokal. Mungkin sepele – tetapi tetap layak untuk disebutkan.

Dalam contoh berikut, #calc_base_price fungsi dipanggil dua kali:

def total_price
  vat = calc_base_price * VAT_RATE
  calc_base_price + vat
end

Jika #calc_base_price fungsinya mahal, misalnya karena permintaan database, masuk akal untuk menyimpan hasilnya dalam variabel lokal. Dalam cuplikan berikut, harga dasar disimpan dalam variabel lokal yang disebut base_price:

def total_price
  base_price = calc_base_price
  vat = base_price * VAT_RATE
  base_price + vat
end

Namun tentu saja ada lebih dari sekadar menghafal contoh sepele ini!

Operator memoisasi

Ruby hadir dengan operator, ||=yang terkadang disebut operator memoisasi. Berikut ini contoh penggunaannya:

def base_price
  @base_price ||= calc_base_price
end

Saat menjalankan metode ini, Ruby akan memeriksa apakah @base_price variabel instan sudah ditentukan dan memiliki nilai jujurartinya tidak nil dan tidak false. Jika demikian, ini akan mengembalikan nilai @base_price.

Sebaliknya, jika @base_price tidak terdefinisi atau disetel ke nil atau falseitu akan memanggil #calc_base_price metode, simpan nilai kembaliannya di @base_price variabel instan, dan gunakan nilai tersebut sebagai nilai untuk seluruh ekspresi (dan dengan demikian sebagai nilai kembalian #base_price).

Itu #base_price metode dapat ditulis ulang tanpa menggunakan ||= operator seperti ini:

def base_price
  if defined?(@base_price) && @base_price
    @base_price
  else
    @base_price = calc_base_price
  end
end

Namun, salah satu kasus di mana Ruby ||= operator tidak berfungsi dengan baik adalah ketika metode memoized memiliki parameter. Itu adalah hal berikutnya dalam daftar yang harus diperbaiki.

def open?
  @is_open ||= calc_is_open
end

def open?
  if defined?(@is_open)
    @is_open
  else
    @is_open = calc_is_open
  end
end

Memoisasi yang sadar argumen

Literatur apa pun tentang topik memoisasi pasti akan memunculkan deret Fibonacci sebagai contoh di mana memoisasi sangat berguna. Berikut adalah implementasi fungsi Ruby yang mengembalikan entri tertentu dalam deret Fibonacci:

def fib(n)
  case n
  when 0
    0
  when 1
    1
  else
    fib(n - 1) + fib(n - 2)
  end
end

Ini berfungsi sebagaimana mestinya: fib(6) mengevaluasi ke 8 dan fib(7) mengevaluasi ke 13.

Namun, untuk jumlah yang lebih besar, waktu eksekusi meningkat dengan cepat. Saya menulis beberapa kode untuk menghitung 50 angka Fibonacci pertama, dan mencetak durasinya^{22 Cuplikan kode ini menggunakan jam monoton untuk menghitung waktu yang telah berlalu. Ini adalah cara yang lebih akurat dibandingkan menggunakan Time.nowkarena jam monotonik tidak terpengaruh oleh pergeseran kecil yang terjadi misalnya saat sinkronisasi dengan server waktu jaringan. untuk menghitungnya:}

def now
  Process.clock_gettime(
    Process::CLOCK_MONOTONIC
  )
end

50.times do |i|
  print "#{i}: "

  before = now
  val = fib(i)
  after = now
  duration = after - before

  puts "#{val} (#{format '%.1f', duration}s)"
end

Inilah yang dicetaknya:

0: 0 (0.0s)
1: 1 (0.0s)
2: 1 (0.0s)
3: 2 (0.0s)
4: 3 (0.0s)
5: 5 (0.0s)
6: 8 (0.0s)
7: 13 (0.0s)
8: 21 (0.0s)
9: 34 (0.0s)
10: 55 (0.0s)
11: 89 (0.0s)
12: 144 (0.0s)
13: 233 (0.0s)
14: 377 (0.0s)
15: 610 (0.0s)
16: 987 (0.0s)
17: 1597 (0.0s)
18: 2584 (0.0s)
19: 4181 (0.0s)
20: 6765 (0.0s)
21: 10946 (0.0s)
22: 17711 (0.0s)
23: 28657 (0.0s)
24: 46368 (0.0s)
25: 75025 (0.0s)
26: 121393 (0.0s)
27: 196418 (0.0s)
28: 317811 (0.0s)
29: 514229 (0.0s)
30: 832040 (0.1s)
31: 1346269 (0.1s)
32: 2178309 (0.2s)
33: 3524578 (0.3s)
34: 5702887 (0.5s)
35: 9227465 (0.8s)
36: 14930352 (1.2s)
37: 24157817 (2.0s)
38: 39088169 (3.2s)
39: 63245986 (5.2s)
40: 102334155 (8.3s)
41: 165580141 (13.5s)
42: 267914296 (21.8s)

Menghitung angka 42 pada deret Fibonacci membutuhkan waktu 21 detik,^{33 Apakah Anda melihat bagaimana durasinya juga membentuk sesuatu yang cukup dekat dengan deret Fibonacci? Seberapa rapi itu?! setelah itu saya menyerah dan membatalkan skrip. Ekstrapolasi dari durasi di atas, saya memperkirakan penghitungan angka 50 pada deret Fibonacci akan memakan waktu 17 menit.44 Ini dengan asumsi bahwa pelambatan termal pada M2 MacBook Air saya tidak aktif. Jika ya, saya bayangkan akan memakan waktu lebih lama dari itu.}

Alasan mengapa penghitungan angka Fibonacci menjadi sangat lambat adalah karena ada a banyak terjadinya pekerjaan berlebihan. Misalnya menghitung fib(40) menghitung fib(39) Dan fib(38). Menghitung fib(39) Juga menghitung fib(38). Pekerjaan yang berlebihan ini akan semakin buruk jika jumlah pekerjanya sedikit. Misalnya, fib(40) menghitung angka ketiga (n=2) dalam deret Fibonacci 63.245.986 kali.

Ini hanya perlu dilakukan sekali saja. Tidak heran implementasi ini lambat.

Salah satu cara untuk menghindari masalah kecepatan eksekusi ini adalah dengan menulis ulang metode untuk menghindari rekursi dan menggunakan perulangan:

def fib(n)
  arr = (0, 1)
  while arr.size <= n
    arr << arr.last(2).sum
  end
  arr(n)
end

Alasan mengapa solusi ini jauh lebih cepat adalah karena solusi ini menghindari penghitungan ulang apa pun. Misalnya, fib(40) menghitung angka ketiga dalam deret Fibonacci hanya sekali — bukan 63 juta kali.

Versi yang menggunakan loop bukan rekursi adalah banyak lebih cepat, namun memiliki masalah karena tidak mudah dibaca seperti versi awal. Dalam versi rekursif yang lebih cepat ini, definisi matematis dari deret Fibonacci tidak mudah terlihat.

Itu #fib fungsi tidak dapat disimpan dengan menerapkan ||= operator seperti sebelumnya. Diperlukan sesuatu yang sedikit lebih canggih, membuat cache untuk setiap nilai argumen n:

def fib(n)
  @fib ||= {}
  @fib(n) ||=
    case n
    when 0
      0
    when 1
      1
    else
      fib(n - 1) + fib(n - 2)
    end
end

Dengan perubahan ini, penuh perhitungan fib(40) seketika. Faktanya, memang demikian fib(4000).^{55 Angka apa pun yang lebih besar dari 8000 atau lebih akan menghasilkan masalah yang berbeda: stack level too deep (SystemStackError). Hal ini sulit, namun bukan tidak mungkin, untuk dihindari dengan solusi rekursif. Versi yang menggunakan loop tidak akan mengalami masalah ini.}

Memoisasi DSL

Salah satu kekuatan besar Ruby adalah kemampuannya untuk metaprogramming. Kasus penggunaan yang baik untuk ini adalah mengotomatiskan memoisasi dengan menjawab panggilan memo­ize setelah definisi metode, seperti ini:

def fib(n)
  # (snip)
end
memo­ize :fib

Teknik yang akan saya perkenalkan di sini hanya berfungsi metodebukan untuk fungsi. Jadi, mari kita tetap bertahan #fib di kelas:

class Fib
  def fib(n)
    case n
    when 0
      0
    when 1
      1
    else
      fib(n - 1) + fib(n - 2)
    end
  end
end

Pemanggilannya sedikit berbeda, tetapi berfungsi seperti sebelumnya (dengan kelambatan yang sama):

p Fib.new.fib(10)

Kami akan membuat modul bernama Memoization dan tempelkan memo­ize metode di sana:

module Memoization
  def memo­ize(method_name)

Tujuannya adalah mengganti metode dengan nama yang diberikan (:fib dalam contoh kita) dengan yang baru yang melakukan memoisasi otomatis. Metode baru ini harus dapat memanggil metode asli, sehingga terlebih dahulu membuat salinan dari metode asli menggunakan #alias_method:

    orig_method_name="__orig_" + method_name.to_s
    alias_method(orig_method_name, method_name)

Dalam contoh kita dengan #fib Misalnya, ini akan membuat metode bernama #__orig_fib.

Metode asli (#fib dalam contoh kita) belum tersentuh. Langkah selanjutnya adalah mendefinisikan kembali metode asli tersebut #define_method berguna. Untuk saat ini, itu akan digunakan #send untuk memanggil metode asli; implementasi dengan memoisasi akan menyusul nanti:

    define_method(method_name) do |*args|
      send(orig_method_name, *args)
    end
  end
end

Untuk menggunakan fungsi baru ini di fungsi kami yang sudah ada Fib kelas, tambahkan dulu extend Memoization dekat bagian atas, lalu tambahkan memo­ize :fib setelah #fib definisi metode:

class Fib
  extend Memoization

  def fib(n)
    case n
    when 0
      0
    when 1
      1
    else
      fib(n - 1) + fib(n - 2)
    end
  end
  memo­ize :fib
end

Ini masih akan berfungsi, masih tanpa memoisasi (belum):

p Fib.new.fib(10)

Sekarang saatnya menerapkan memoisasi dalam metode yang baru ditentukan. Hal pertama yang dibutuhkannya adalah cache:

define_method(method_name) do |*args|
  @__cache ||= {}

Ini @__cache Variabel instance akan berisi hasil semua pemanggilan untuk semua metode pada instance khusus ini. Kunci dari @__cache hash akan menjadi nama metode.

Selanjutnya, implementasi perlu mendapatkan cache untuk metode khusus ini, yang diberikan oleh method_name variabel:

  method_cache = (@__cache(method_name) ||= {})

Dengan cache untuk metode khusus ini sekarang tersedia, metode ini dapat memeriksa apakah sudah ada nilai untuk argumen yang diberikan. Jika ada, itulah nilai yang dapat dikembalikan — inti dari memoisasi:

  if method_cache.key?(args)
    method_cache(args)

Jika belum ada nilai yang tersedia, panggil metode asli dan simpan nilai yang dikembalikan dalam cache untuk metode ini:

  else
    method_cache(args) =
      send(orig_method_name, *args)
  end
end

Di Ruby, penugasan dievaluasi berdasarkan nilai yang ditetapkan, jadi tidak diperlukan nilai eksplisit method_cache(args) setelah penugasan.

Dengan perubahan ini, berjalan fib(40) sekarang memang sangat cepat — praktis seketika:

p Fib.new.fib(40)

Ada satu lagi perubahan rapi yang mungkin dilakukan. Di Ruby, definisi metode mengembalikan nama mehod sebagai simbol memo­ize dapat terjebak di depan def kata kunci dan memo­ize :fib baris dihapus:

memo­ize def fib(n)
  # (snip)
end

Sekarang sepertinya kata kunci, yang menurut saya cukup rapi.

Persyaratan memoisasi

Sebelum melanjutkan, saya ingin menjawab pertanyaan berikut: dalam kondisi apa memoisasi dapat diterapkan dengan aman? Memoisasi bukanlah teknik yang bisa disemprotkan ke kode untuk membuatnya lebih cepat. Ada batasan yang perlu dipertimbangkan agar kode memo berfungsi dengan benar.

Metode memoisasi hanya boleh menggunakan variabel yang tidak pernah mengubah nilainya. Ini termasuk variabel instan, argumen, variabel global, konstanta, dan banyak lagi.

Untuk mengilustrasikannya, lihat contoh berikut LineItem kelas, dengan memo #total_price metode:^{66 Penggunaan memoisasi di sini tidak terlalu berguna: mengalikan dua angka, count Dan unit_pricesangat cepat — tetapi ini cocok sebagai contoh.}

class LineItem
  extend Memoization

  attr_accessor :unit_price
  attr_accessor :count

  def initialize(unit_price:, count:)
    @unit_price = unit_price
    @count = count
  end

  memo­ize def total_price
    count * unit_price
  end
end

Total harga dihitung dengan benar:

line_item = LineItem.new(unit_price: 49, count: 2)
p line_item.total_price
# => 98

Namun setelah diubah hitungannya, total harga tidak terupdate, karena terpampang di memo:

line_item.count = 3
p line_item.total_price
# => 98

Solusi untuk masalah ini adalah dengan membuat LineItem tidak dapat diubah, baik dengan membekukannya atau menggantinya attr_accessor dengan attr_reader. Hal ini akan mencegah penghitungan a LineItem dari perubahan; sebaliknya, sebuah contoh baru LineItem dapat dibuat dengan hitungan yang benar:

line_item = LineItem.new(
  unit_price: 49,
  count: 2)
p line_item.total_price
# => 98

line_item = LineItem.new(
  unit_price: line_item.unit_price,
  count: 3)
p line_item.total_price
# => 147

Pedoman umum yang baik adalah menggunakan memoisasi hanya pada objek yang tidak dapat diubah, dan juga hanya meneruskan argumen yang tidak dapat diubah juga.

Menghafal benda beku

Ada satu masalah khusus dalam penerapan ini. Mencoba menggunakan memoisasi pada objek yang dibekukan gagal. Ambil kode berikut sebagai contoh:

f = Fib.new
f.freeze
p f.fib(40)

Ini gagal dengan a FrozenError:

example3.rb:20:in `block in memo­ize': can't modify frozen Fib: #<0x000000011ffeb008/>

­

­

­

­

­

&blk

&blk­

&&

&&&&