ví dụ đơn giản cho Erlang memoization

Question

Giả sử bạn có một chức năng đơn giản, có thể nhận được khá đắt đối với giá trị lớn:

fact(0) -> 1; 
fact(N) -> N * fact(N - 1). 

Tôi có thể tìm thấy một ví dụ đơn giản của bộ nhớ đệm (hoặc memoizing) giá trị chức năng bằng cách sử dụng dets ở đâu?

Bất kỳ cách nào khác để ghi nhớ dễ dàng sẽ được đánh giá cao.

Answer 1

Ý tưởng là mỗi lần bạn yêu cầu tính toán nặng của mình, bạn sẽ ngay lập tức kiểm tra bộ nhớ cache nếu bạn đã đánh giá nó. Nếu có, bạn chỉ cần trả về giá trị được lưu trữ. Nếu không, bạn phải đánh giá giá trị mới và lưu trữ nó trước khi trả lại cho người dùng cuối cùng.

A dict, chứ không phải là bảng cược, cũng có thể hoạt động.

(Các giải pháp sau đây là chưa được kiểm tra)

-module(cache_fact). 

-export([init/0, fact/1]). 

init() -> 
    {ok, _} = dets:open_file(values, []). 

fact(N) -> 
    case dets:lookup(values, N) of 
     [] -> 
     Result = do_fact(N), 
     dets:insert_new(values, {N, Result}), 
     Result; 
     [{N, Cached}] -> 
     Cached 
    end. 

do_fact(0) -> 
    1; 
do_fact(N) -> 
    N * do_fact(N-1). 

Bạn có thể muốn để đóng gói toàn bộ điều vào một Erlang generic server. Trong hàm init, bạn nên tạo bảng DETS, hàm thực tế/1 sẽ đại diện cho API của bạn và bạn nên thực hiện logic trong các hàm handle_call.

Một ví dụ đẹp hơn có thể là viết dịch vụ rút gọn cho URL, được lưu trong bộ nhớ cache.

Theo đề xuất của @Zed, sẽ có ý nghĩa để lưu trữ các kết quả một phần cũng như để tránh tính toán lại thêm. Nếu đây là trường hợp:

-module(cache_fact). 

-export([init/0, fact/1]). 

init() -> 
    {ok, _} = dets:open_file(values, []). 

fact(0) -> 
    1; 
fact(N) -> 
    case dets:lookup(values, N) of 
     [] -> 
     Result = N * fact(N-1), 
     dets:insert_new(values, {N, Result}), 
     Result; 
     [{N, Cached}] -> 
     Cached 
    end. 

Rõ ràng, ngay cả khi điều này giúp số lượng lớn, bạn phải xem xét chi phí bổ sung thêm mục nhập vào bảng tra cứu cho mỗi bước. Xem xét lý do tại sao bộ nhớ đệm đã được giới thiệu (chúng tôi giả định tính toán rất nặng, do đó thời gian chèn tra cứu không đáng kể), điều này sẽ hoàn toàn ổn.

Answer 2

Tùy thuộc vào trường hợp của bạn, bạn cũng có thể sử dụng process dictionary cho memoization:

fact(0) -> 1; 
fact(N) -> 
    case erlang:get({'fact', N}) of 
     F when is_integer(F) -> 
      F; 
     'undefined' -> 
      F = N * fact(N-1), 
      erlang:put({'fact', N}, F), 
      F 
    end.