Help us understand the problem. What is going on with this article?

出力を保存する関数

More than 5 years have passed since last update.

ちょっと漸化式をいっぱい使う式を解く要件があったのですが、
そこで入力と出力をキャッシュするクラスを作りました。

漸化式というとフィボナッチ数が有名ですが、
普通に再帰を使って計算してしまうと結構時間かかります。
しかし、入力に対して出力が同じ値になるので、それをキャッシュするわけです。

ソースはこちら
f(n,2)が普通のフィボナッチ数、f(n,m)はm個足した版です。

fib.cpp
#include <boost/function.hpp>
#include <boost/unordered_map.hpp>

template<typename R, typename T1, typename T2>
class CacheFunction{
    typedef boost::function<R (T1, T2)> CalculateFunction;
    CalculateFunction cfunc;
    typedef boost::unordered_map<std::pair<T1, T2>, R> CacheMap;
    CacheMap cmap;

public:
    CacheFunction() :cfunc(){}
    CacheFunction(CalculateFunction cfunc) :cfunc(cfunc){}

    int operator()(T1 a, T2 b){
        auto key = std::pair<T1, T2>(a, b);
        auto it = cmap.find(key);
        if (it != cmap.end()) return it->second;
        auto result = cfunc(a, b);
        cmap[key] = result;
        return result;
    }

    void set(CalculateFunction func){
        cfunc = func;
    }
};

int main(){
    CacheFunction<int, int, int> f_ch;

    auto f = [&](int n, int m)->int{
        if (n <= m) return 1;
        Number x = 0;
        for (int i = 0; i < m; i++){
            x += f_ch(n - 1 - i, m);
        }
        return x;
    };
    f_ch.set(f);

    std::cout << f_ch(30, 5) << std::endl;
    return 0;
}

キャッシュするために関数をラップするんですが、
再帰で呼び出す関数もラップした関数にしないといけません。

なので、一度ラップするクラスを作り、ラムダ式でキャプチャして
最後にラップクラスにセットというややこしい方法に…。
なんとかならないですかね~。
こういうことをするにあたって何も考えずに出来る言語ないかなぁ…。

おまけ
引数3つ版も作ってみました。
たらいまわし関数も一瞬です。

tarai.cpp
#include <boost/function.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <boost/unordered_map.hpp>

template<typename R, typename T1, typename T2, typename T3>
class CacheFunction3{
    typedef boost::function<R (T1, T2, T3)> CalculateFunction;
    CalculateFunction cfunc;
    typedef boost::tuple<T1, T2, T3> Key;


    struct ihash
        : std::unary_function < Key, std::size_t >
    {
        std::size_t operator()(Key const& e) const
        {
            std::size_t seed = 0;
            boost::hash_combine(seed, e.get<0>());
            boost::hash_combine(seed, e.get<1>());
            boost::hash_combine(seed, e.get<2>());
            return seed;
        }
    };

    struct iequal_to
        : std::binary_function < Key, Key, bool >
    {
        bool operator()(Key const& x, Key const& y) const
        {
            return (x.get<0>() == y.get<0>() &&
                x.get<1>() == y.get<1>() &&
                x.get<2>() == y.get<2>());
        }
    };

    typedef boost::unordered_map<Key, R, ihash, iequal_to> CacheMap;
    CacheMap cmap;

public:
    CacheFunction3() :cfunc(){}
    CacheFunction3(CalculateFunction cfunc) :cfunc(cfunc){}

    int operator()(T1 a, T2 b, T3 c){
        auto key = Key(a, b, c);
        auto it = cmap.find(key);
        if (it != cmap.end()) return it->second;
        auto result = cfunc(a, b, c);
        cmap[key] = result;
        return result;
    }

    void reset(CalculateFunction func){
        cfunc = func;
    }
};

int main()
{
    CacheFunction3<int, int, int, int> ctarai;
    auto tarai = [&](int x, int y, int z)->int{
        return x <= y ? y : ctarai(ctarai(x - 1, y, z), ctarai(y - 1, z, x), ctarai(z - 1, x, y));

    };
    ctarai.reset(tarai);

    std::cout << ctarai(13, 6, 0) << std::endl;

    boost::function<int(int, int, int)> org_tarai = [&](int x, int y, int z)->int{
        return x <= y ? y : org_tarai(org_tarai(x - 1, y, z), org_tarai(y - 1, z, x), org_tarai(z - 1, x, y));
    };

    std::cout << org_tarai(13, 6, 0) << std::endl;

    return 0;
}
izmktr
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away