Chức năng thừa nhận, đệ quy?

Question

Tôi biết cách thực hiện ghi nhớ bằng Python dễ dàng nhưng tôi cần cách nhanh hơn để tính toán chúng, vì vậy tôi đang sử dụng C++. Tuy nhiên, tôi không có đầu mối làm thế nào để ghi nhớ. Tôi hiểu rằng đó là về lưu trữ các giá trị vào một mảng hoặc vector và sau đó quét cho giá trị của nó khi lấy, nhưng nó sẽ thực sự hữu ích để xem cách thực hiện điều này để tôi có thể thử tốc độ của nó.

Answer 1

Cách gọn gàng nhất mà tôi có thể nghĩ đến để làm điều này trong C++ có lẽ là sử dụng đối tượng hàm để lưu trữ các giá trị đã ghi nhớ. Tôi đoán đây có lẽ là hơi tương tự như trang trí python của bạn, mặc dù tôi chưa bao giờ thực sự thực hiện bất kỳ python. Mã sẽ trông giống như sau:

template <typename T, T (*calc)(T)> 
class mem { 
    std::map<T,T> mem_map; 

public: 
    T operator()(T input) { 
    typename std::map<T,T>::iterator it; 

    it = mem_map.find(input); 
    if (it != mem_map.end()) { 
     return it->second; 
    } else { 
     T output = calc(input); 
     mem_map[input] = output; 
     return output; 
    } 
    } 
}; 

Mã xác định lớp mẫu có tên và con trỏ hàm, sau đó được định nghĩa trên lớp cho phép nó được gọi. Toán tử hàm nhận giá trị đầu vào sẽ kiểm tra nếu giá trị nói trên bản đồ, sau đó đơn giản trả về từ bản đồ hoặc tính toán nó (sử dụng con trỏ hàm), thêm nó vào bản đồ và sau đó trả về nó.

Vì vậy, giả sử bạn xác định một số chức năng xử lý như nói:

int unity(int in) { return in; } 

Bạn sẽ sử dụng mã như thế này:

mem<int, unity> mem_unity; 
int y; 
y = mem_unity(10); 

Vì vậy, chúng ta định nghĩa một thể hiện của lớp mem trong đó có kiểu giá trị của chúng tôi và chức năng xử lý như các tham số mẫu, sau đó chỉ cần gọi lớp này là một hàm.

Answer 2

Không ai ngoại trừ việc học đệ quy sẽ tính toán giai thừa theo cách đó.

Ghi nhớ là một ý tưởng rất hay, đặc biệt nếu bạn định gọi lại phương thức này nhiều lần. Tại sao vứt bỏ công việc tốt?

Một xem xét khác là cách tốt hơn để tính giai thừa: sử dụng nhật ký tự nhiên của hàm gamma. Nó sẽ giữ chống lại tràn lâu hơn, bởi vì bạn trả về một giá trị gấp đôi. Nhật ký tự nhiên sẽ tăng chậm hơn giá trị. Nếu bạn đang tính toán kết hợp, nhật ký tự nhiên sẽ thay đổi phép nhân và phép chia thành phép cộng và phép trừ.

Nhưng, bằng mọi cách, hãy ghi nhớ cho bất kỳ triển khai nào bạn sử dụng. Nếu bạn đang viết nó trong C++, tôi khuyên bạn nên sử dụng một số std:map với đối số x làm khóa và ln(gamma(x)) làm giá trị.

Rất tiếc, đã quá lâu kể từ khi tôi viết C++ và STL. Tôi muốn sử dụng bản đồ băm có thời gian truy cập đọc là O(1) để phải lặp qua các phím trong O(n).

Answer 3

Chỉ để cho vui, đây là một bản ghi nhớ chung chung tôi đã viết một số thời gian trước đây. Nó đòi hỏi các mẫu variadic, một cách tự nhiên:

template <template <typename...> class Container, typename...> struct Memo; 

template <typename R, typename... Args, template <typename...> class Container> 
struct Memo<Container, R, std::tuple<Args...>> 
{ 
    Memo(std::function<R(Args...)> f) : func(f) { } 

    R operator()(Args && ...args) 
    { 
    const auto arg = std::make_tuple(args...); 
    typename CacheContainer::const_iterator it = cache.find(arg); 

    if (it == cache.cend()) 
    { 
     it = cache.insert(typename CacheContainer::value_type(arg, func(std::forward<Args>(args)...))).first; 
     std::cout << "New call, memoizing..." << std::endl; 
    } 
    else 
    { 
     std::cout << "Found it in the cache!" << std::endl; 
    } 

    return it->second; 
    } 

private: 

    typedef Container<typename std::tuple<Args...>, R> CacheContainer; 

    std::function<R(Args...)> func; 
    CacheContainer cache; 
}; 


template <typename R, typename... Args> 
Memo<std::map, R, std::tuple<Args...>> OMapMemoize(R(&f)(Args...)) 
{ 
    return Memo<std::map, R, std::tuple<Args...>>(f); 
} 
template <typename R, typename... Args> 
Memo<std::unordered_map, R, std::tuple<Args...>> UMapMemoize(R(&f)(Args...)) 
{ 
    return Memo<std::unordered_map, R, std::tuple<Args...>>(f); 
} 

Tôi không hoàn toàn chắc chắn nếu tôi nhận được quyền chuyển nhượng rvalue, vì đã lâu rồi tôi viết nó. Dù sao, đây là một trường hợp thử nghiệm:

int foo(double, char) { return 5; } 

int main() 
{ 
    auto f = OMapMemoize(foo); 
    auto g = UMapMemoize(foo); 

    int a, b; 

    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 

    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 

    return a; 
} 

Answer 4

Tôi thích dựa vào chụp lambda như trong (sử dụng std=c++14)

template<typename R, typename... Args> 
auto memoize(std::function<R(Args...)>&& f) 
{ 
    using F = std::function<R(Args...)>; 
    std::map<std::tuple<Args...>,R> cache; 
    return ([cache = std::map<std::tuple<Args...>,R>{}, 
      f = std::forward<F>(f)](Args&&... args) mutable 
    { 
     std::tuple<Args...> t(args...); 
     if (cache.find(t) == cache.end()) 
     { 
      R r = f(std::forward<Args...>(args)...); 
      cache[t] = r; 
     } 
     return cache[t]; 
    }); 
}