Việc sử dụng các ngôn ngữ chức năng có giúp chống lại các giá trị tính toán nhiều lần không?

Question

Xem xét một hàm f (x, y):

f(x,0) = x*x; 
f(0,y) = y*(y + 1); 
f(x,y) = f(x,y-1) + f(x-1,y); 

Nếu một cố gắng thực hiện điều đó một cách đệ quy trong một số ngôn ngữ như C++ ông sẽ gặp phải một vấn đề.

Giả sử hàm này được gọi đầu tiên với x = x0 và y = y0. Sau đó, đối với bất kỳ cặp nào (x, y) trong đó 0 <= x < x0 và 0 <= y < y0 giá trị trung gian sẽ được tính nhiều lần - các cuộc gọi đệ quy sẽ tạo thành một cây lớn trong đó nhiều lá thực tế sẽ chứa cùng một cặp (x, y). Đối với các cặp (x, y) trong đó x và y đều gần với 0 giá trị sẽ được tính nhiều lần.

Ví dụ, tôi đã thử nghiệm một chức năng tương tự được thực hiện trong C++ - cho x=20 và y=20 tính toán của nó mất khoảng 4 giờ (có, bốn giờ Trái đất!).

Rõ ràng việc triển khai có thể được viết lại theo cách tính toán lặp lại không xảy ra - hoặc lặp lại hoặc với bảng bộ nhớ cache.

Câu hỏi đặt ra là: liệu các ngôn ngữ chức năng có thực hiện tốt hơn và tránh tính toán lặp lại khi triển khai một hàm như trên đệ quy không?

Answer 1

Thuật ngữ mà bạn đang tìm kiếm ở đây là Memoization:

Trong máy tính, memoization là một kỹ thuật tối ưu hóa sử dụng chủ yếu để tăng tốc độ chương trình máy tính bằng cách có chức năng cuộc gọi tránh lặp lại tính kết quả cho các đầu vào được xử lý trước đó.

Không, ngôn ngữ chức năng không tự động thực hiện ghi nhớ. Bạn có thể thực hiện nó trong chúng, nhưng trong C++ là tốt. Tuy nhiên, đúng là khi bạn viết mã chức năng thuần túy (nghĩa là không có tác dụng phụ), thì việc ghi nhớ dễ dàng hơn. Ví dụ: một số ngôn ngữ động (ví dụ: Perl) có các mô-đun ghi nhớ tự động có thể dễ dàng ghi nhớ bất kỳ chức năng nào. Có một cuộc thảo luận về chủ đề này trong Automatic memoization section of the Wikipedia article.

Ví dụ đây là một ngây thơ C++ Fibonacci:

long fib_rec(long index) 
{ 
    if (index < 2) 
     return index; 
    else 
     return fib_rec(index - 1) + fib_rec(index - 2); 
} 

Và đây là một phiên bản memoized:

long fib_memoized_aux(vector<long>& cache, long index) 
{ 
    if (cache[index] >= 0) 
    return cache[index]; 

    cache[index] = fib_memoized_aux(cache, index - 1) + fib_memoized_aux(cache, index - 2); 
    return cache[index]; 
} 


long fib_memoized(long index) 
{ 
    vector<long> cache(index + 1, -1); 
    cache[0] = 0; 
    cache[1] = 1; 

    return fib_memoized_aux(cache, index); 
}