9
\$\begingroup\$

I was inspired by this answer to make this.

ex[0] = 1;
ex[n_] := ex[n] = ex[n - 1] + 0.5^n/n!;

The double assignment in the second line is very important. This causes all function calls to be evaluated only once. Once it has been initially evaluated, it will be saved in ex[n].

After a little research, it looks like I just reinvented a memoizer.

#include <unordered_map>
#include <functional>

template < auto callback,
           typename data_t,
           typename key_t = std::size_t >
class static_memoizer_t
{
public:
    using map_t = std::unordered_map< key_t,
                                      data_t >;
    using callback_t = decltype( callback );

    static_memoizer_t( ) = default;
    static_memoizer_t( static_memoizer_t const & ) = default;
    static_memoizer_t( static_memoizer_t && ) = default;
    static_memoizer_t & operator =( static_memoizer_t const & ) = default;
    static_memoizer_t & operator =( static_memoizer_t && ) = default;
    ~static_memoizer_t( ) = default;

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }

    data_t operator[ ]( key_t const & key ) const
    {
        return map.at( key );
    }

private:
    map_t map;
};

template < typename data_t,
           typename key_t = std::size_t >
class dynamic_memoizer_t
{
public:
    using map_t = std::unordered_map< key_t,
                                      data_t >;
    using callback_t = std::function< data_t( key_t const & ) >;

    dynamic_memoizer_t( callback_t callback ):
        callback( std::move( callback ) )
    { }
    dynamic_memoizer_t( dynamic_memoizer_t const & ) = default;
    dynamic_memoizer_t( dynamic_memoizer_t && ) = default;
    dynamic_memoizer_t & operator =( dynamic_memoizer_t const & ) = default;
    dynamic_memoizer_t & operator =( dynamic_memoizer_t && ) = default;
    ~dynamic_memoizer_t( ) = default;

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }

    data_t operator[ ]( key_t const & key ) const
    {
        return map.at( key );
    }

private:
    map_t map;
    callback_t callback;
};

The basic gist is that it stores the results of expensive functions. I wanted to add support for expensive recursive functions for my initial inspiration, not sure how to approach that though.

Usage:

int square_of( int i ) noexcept
{
    return i * i;
}

// static usage
using memoizer_t = static_memoizer_t< square_of, int, int >;
memoizer_t memoizer;
memoizer[ 2 ]; // calculates 2*2, returns 4
memoizer[ 2 ]; // pulls 2*2 from map

// dynamic usage
using memoizer_t = dynamic_memoizer_t< int, int >;
memoizer_t memoizer( square_of );
memoizer[ 2 ]; // calculates 2*2, returns 4
memoizer[ 2 ]; // pulls 2*2 from map
\$\endgroup\$
2
  • \$\begingroup\$ can you provide some sample code of its usage? Also, where are your benchmarks, performance measurements? \$\endgroup\$ – Peter Aug 20 '20 at 15:13
  • \$\begingroup\$ @Peter I hoped the usage was straight-forward but I added some usage in the question. As for benchmarks, it's just a iso-standard map wrapper. I suppose I can benchmark using map vs unordered_map. \$\endgroup\$ – lajoh90686 Aug 21 '20 at 3:29
5
\$\begingroup\$

Unfortunately, a major weakness of your class is that it only allows functions with a single argument. Now, this can be alleviated by using std::tuple and std::apply, but it's an ugly solution because it forces the user of the class to specify the tuple type, and every invocation of the object requires a std::make_tuple.

Fortunately, this can be solved using variadic templates.

To start, here's a basic definition of our class.

#include<tuple>
template<typename ReturnType, typename ... Args>
class Memoizer
{
};

Now, we need a way to store variadic number and types of arguments. std::tuple is perfect for this.

using tuple_type = std::tuple<Args...>;
using return_type = ReturnType;
using callback_type = std::function<return_type(Args...)>;
using map_type = std::unordered_map<tuple_type, return_type>;

Now, std::tuple doesn't come with an overloaded std::hash. Fortunately, this SO answer provides a good implementation.

Your data members would then become

map_type map;
callback_type callback;

The meat of the implementation lies in operator().

return_type operator()(Args&& ... args)
{
    auto arguments_tuple = std::make_tuple<Args...>(std::forward<Args>(args)...);
    if(map.find(arguments_tuple) == map.end())
    {
       std::cout << "Invoking function\n"; // for debugging
       map.insert({arguments_tuple, std::apply(callback, arguments_tuple)});
    }
    return map[arguments_tuple]; 
}

The method takes the arguments, create a tuple of them and then checks if the map already contains the tuple. If it doesn't, it inserts an entry into the map, using std::apply (C++17 feature).

Usage might look like this:

int func(int x, int y)
{
    return x * y;
}

int main()
{
   Memoizer<int, int, int> mem{func};
   auto t1 = mem(2, 3);
   auto t2 = mem(2, 3);
   std::cout << t1 << '\n';
   std::cout << t2 << '\n';
}

The output is:

Invoking function
6
6

The full implementation is here:

https://godbolt.org/z/Eczq93

You can also use custom types as arguments, provided std::hash and operator== are overloaded for those types.

\$\endgroup\$
2
  • \$\begingroup\$ Very advanced answer and certainly an improvement over the current version. Smart change of operator and abstraction. Unfortunately, it cannot support taking the memoizer as an argument, which makes recursion impossible (unless I force all callbacks to support it). Will need to consider further \$\endgroup\$ – lajoh90686 Sep 2 '20 at 7:03
  • \$\begingroup\$ For operator(): Since it's not a template function, we shouldn't use std::forward; we should take args by value and then use std::move. Also, the current logic does an extra (unnecessary) map lookup in the return statement. \$\endgroup\$ – user673679 Oct 2 '20 at 7:10
3
\$\begingroup\$

Some nitpicks:

  • Rule of zero — don't explicitly default the special member functions unless necessary.

  • This method always traverses the map twice, and sometimes unnecessarily default-constructs a value:

      data_t operator[ ]( key_t const & key )
      {
          if( map.end( ) == map.find( key ) )
              return map[ key ] = callback( key );
          return map[ key ];
      }
    

    The following version avoids most of the problems above, but still traverses the map twice when there is no cached value:

      data_t operator[](const key_t& key) {
          if (auto it = map.find(key); it != map.end()) {
              return it->second;
          } else {
              return map.emplace(key, callback(key))->first->second;
          }
      }
    

    An optimal version might involve using try_emplace and a wrapper around the callback that converts to the value type.

\$\endgroup\$
3
  • \$\begingroup\$ Does insert traverse the list again like emplace? \$\endgroup\$ – lajoh90686 Sep 1 '20 at 4:45
  • \$\begingroup\$ @lajoh90686 Yes. \$\endgroup\$ – L. F. Sep 1 '20 at 5:00
  • \$\begingroup\$ Okay, I've change it to have a lazy-eval type and it now uses try_emplace. I've also removed all the defaulted functions. Thanks for the input. \$\endgroup\$ – lajoh90686 Sep 1 '20 at 5:04

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.