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?
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:12RecursiveArray
already knowsDerived
, there is no reason to pass to it any other template parameters than can be found inDerived
. I sayunsigned int
intypes_t
and if I want to change it, I only have to change it in one place. But note that I failed since I wroteunsigned int
intMemoizedFibonacci
while I should have writtentypes_t<MemoizedFibonacci>::value_type
, which is quite dumb since I createdtypes_t
so that I would have to writeunsigned int
in only one place. \$\endgroup\$ – Morwenn Mar 9 '14 at 12:09types_t
is useful for DRY. \$\endgroup\$ – Morwenn Mar 21 '14 at 23:06