8
\$\begingroup\$

I created a class a while ago that I named a "Recursion Array". It is a way to create dynamically memoized sequences such as the Fibonacci sequence or the factorial numbers sequences. The concept is to create mathematic sequences defined by recursion by only providing the first values and the recursive formula; all the computed results are internally stored into a vector. That allows to create mathematic formula in a recursive way, without having to care about the access time; each result is only computed once. Here is the base class:

#include <initializer_list>
#include <vector>

template<typename T>
types_t;

template<typename Derived>
class RecursionArray
{
    public:

        using value_type = typename types_t<Derived>::value_type;

        // A RecursionArray is not copyable
        RecursionArray(const RecursionArray&) = delete;
        RecursionArray& operator=(const RecursionArray&) = delete;

        /**
         * @brief Calls "function" and applies memoization
         * @see value_type self(size_t n)
         */
        inline auto operator()(std::size_t n)
            -> value_type
        {
            return self(n);
        }

    protected:

        RecursionArray() = default;

        /**
         * @brief Initializer-list constructor
         *
         * This should be the one and only way to instance a
         * RecursionArray.
         *
         * @param vals Results of "function" for the first values
         */
        RecursionArray(std::initializer_list<value_type> vals):
            _values(vals.begin(), vals.end())
        {}

        /**
         * @brief Calls "function" and applies memoization
         *
         * @param n Index of the value to [compute, memoize and] return
         * @return Value of "function" for n
         */
        auto self(std::size_t n)
            -> value_type
        {
            while (size() <= n)
            {
                // Compute and add the values to the vector
                _values.emplace_back(function(size()));
            }
            return _values[n];
        }

        /**
         * @brief Returns the number of computed elements
         * @return Number of computed elements in the vector
         */
        constexpr auto size() const
            -> std::size_t
        {
            return _values.size();
        }

        /**
         * @brief User-defined function whose results are stored
         *
         * This is the core of the class. A RecursionArray is just
         * meant to store the results of "function" are reuse them
         * instead of computing them another time. That is why a
         * RecursionArray function can only accept unsigned integers
         * as parameters.
         *
         * @param n Index of the element
         * @return See user-defined function
         */
        auto function(std::size_t n)
            -> value_type
        {
            return static_cast<Derived&>(*this).function(n);
        }

    private:

        // Member data
        std::vector<value_type> _values;  /**< Computed results of "function" */
};

It is a base class that uses static polymorphism. Here is an example of a user-defined derived class:

class MemoizedFibonacci;
/*
 * We need to tell to the RecursionArray which
 * kind of data it has to store.
 */
template<>
struct types_t<MemoizedFibonacci>
{
    using value_type = unsigned int;
};

/**
 * @brief Fibonacci function class
 *
 * A way to implement the Fibonacci function and to force it
 * to store its results in order to gain some speed with the
 * following calls to the function.
 */
struct MemoizedFibonacci:
    RecursionArray<MemoizedFibonacci>
{
    using super = RecursionArray<MemoizedFibonacci>;
    using typename super::value_type;

    /**
     * @brief Default constructor
     *
     * To use a Fibonacci function, we need to know at least
     * its first two values (for 0 and 1) which are 0 and 1.
     * We pass those values to the RecursionArray constructor.
     */
    MemoizedFibonacci():
        super( { 0, 1 } )
    {}

    /**
     * @brief Fibonacci function
     *
     * Fibonacci function considering that the first values are
     * already known. Also, "self" will call "function" and
     * memoize its results.
     *
     * @param n Wanted Fibonacci number
     * @return nth Fibonacci number
     */
    auto function(std::size_t n)
        -> value_type
    {
        return self(n-1) + self(n-2);
    }
};

And finally, here is how we can use the user-defined class:

int main()
{
    MemoizedFibonacci fibonacci;

    // The Fibonacci numbers up to the nth are computed
    // and stored into the RecursionArray
    std::cout << fibonacci(12) << std::endl;    // 144
    std::cout << fibonacci(0) << std::endl;     // 0
    std::cout << fibonacci(1) << std::endl;     // 1
    std::cout << fibonacci(25) << std::endl;    // 75025
}

The problem is that I want to keep the user side simple, but also to avoid virtual (hence the static polymorphism). There are three main functions in the class: * function: the recursive formula. * operator(): so that the end user can use the final instances as functions. * self: helper function (same as operator()) so that the recursive formula is easier to write.

It would be great if the user did not have to specialize types_t and could just give MemoizedFibonacci, but I can't seem to find a way to do so. Do you whether there would be some way to ease the functor writer work?

\$\endgroup\$
  • \$\begingroup\$ I am not very experienced with C++, but wouldn't it be better to pass in the value_type as an argument to the template: RecursionArray<MemoizedFibonnacci, unsigned int>? It seems you really like templates, and have overused them a little bit ;-) \$\endgroup\$ – amon Mar 9 '14 at 9:12
  • \$\begingroup\$ @amon Haha, I know what you mean. At first, the reason was since RecursiveArray already knows Derived, there is no reason to pass to it any other template parameters than can be found in Derived. I say unsigned int in types_t and if I want to change it, I only have to change it in one place. But note that I failed since I wrote unsigned int int MemoizedFibonacci while I should have written types_t<MemoizedFibonacci>::value_type, which is quite dumb since I created types_t so that I would have to write unsigned int in only one place. \$\endgroup\$ – Morwenn Mar 9 '14 at 12:09
  • \$\begingroup\$ I don't like to do this, but I edited the code I posted to show how types_t is useful for DRY. \$\endgroup\$ – Morwenn Mar 21 '14 at 23:06
6
\$\begingroup\$

There's a (slight) typo in what you've posted - the forward declaration of types_t:

   template<typename T>
   types_t;
// ^^^^^^^^
// Should be struct types_t;

Similarly, you've forward defined class MemoizedFibonacci and then defined it as struct MemoizedFibonacci (this isn't really a problem, but clang will complain about it with warnings enabled).

It'd be nice to not have to specialise a struct with a value_type. Often, decltype can help you get around this, however, in this case, since you're using CRTP and static polymorphism, it's unfortunately not going to work. I actually agree that using another template parameter is potentially a better solution here than to force specialisation of a template.

To me, the largest shortcoming here is that this only works with functions that take a single std::size_t parameter. Perhaps this is fine for your uses (calculating mathematical sequences that depend only on 1 variable). Using variadic templates, you can lift this restriction (at the expense of imposing another). Something like the following (incomplete, but hopefully gives you the idea):

#include <tuple>
#include <unordered_map>

template<typename Derived, typename... Args>
class RecursionArray
{

public:
    using argument_type = std::tuple<Args...>;

    inline auto operator()(Args&&... args)
        -> value_type
    {
        return self(std::forward<Args>(args)...);
    }

    auto self(Args&&... args)
        -> value_type
    {
        auto tup = argument_type(args...);
        auto it = values_.find(tup);
        if(it != values_.end()) {
            return it->second;
        }
        auto p = values_.emplace(std::make_pair(std::move(tup), function(std::forward<Args>(args)...));
        return p.first->second;
    }

private:
    std::unordered_map<argument_type, value_type> values_;

};

This lifts the restriction that you need to have a single std::size_t parameter, at the expense of extra complexity, and the ability to easily enforce computation up to a given size. Whether the trade-off is worth it is up to you, but it is something to think about.

\$\endgroup\$
  • \$\begingroup\$ Well, for a more general memoizer, I already asked that question. This structure was dedicated to memoize recursive functions, hence some design choices. As I detailed in the comments under the question, the types_t specialization is to write the value_type only (which I failed to do...). Concerning the struct/class, I have to admit that I totally overlooked it. Thanks! \$\endgroup\$ – Morwenn Mar 12 '14 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.