DGtal::TimeStampMemoizer< TKey, TValue > Class Template Reference

Aim: A generic class to store a given maximum number of pairs (key, value). The class tends to memorize pairs which are accessed more frequently than others. It is thus a memoizer, which is used to memorize the result of costly computations. The memoization principle is simple: a timestamp is attached to a pair (key,value). Each time a query is made, if the item was memoized, the result is returned while the timestamp of the item is updated. User can also add or update a value in the memoizer, which updates also its timestamp. After adding a pair (key,value), if the maximal number of items is reached, at least the oldest half (or a fraction) of the items are deleted, leaving space for storing new pairs (key,value). More...

#include <DGtal/base/TimeStampMemoizer.h>

Inheritance diagram for DGtal::TimeStampMemoizer< TKey, TValue >:

Public Types
typedef TKey	Key
typedef TValue	Value
typedef TimeStampMemoizer< TKey, TValue >	Self
typedef std::size_t	Size
typedef DGtal::uint32_t	TimeStamp
typedef std::pair< Value, TimeStamp >	StoredValue

Public Member Functions
	TimeStampMemoizer (Size max_size=0, double ratio=0.5, bool verbose=false)
	TimeStampMemoizer (const TimeStampMemoizer &other)=default
	TimeStampMemoizer (TimeStampMemoizer &&other)=default
TimeStampMemoizer &	operator= (const TimeStampMemoizer &other)=default
TimeStampMemoizer &	operator= (TimeStampMemoizer &&other)=default
	~TimeStampMemoizer ()=default
Size	size () const
Size	maxSize () const
Size	hits () const
Size	timeStamp () const
const std::unordered_map< Key, StoredValue > &	map () const
std::pair< Value, bool >	get (const Key &key)
void	set (const Key &key, const Value &value)
void	cleanUp ()
	Clean-up the memoizer by removing a fraction of its oldest elements.
void	selfDisplay (std::ostream &out) const
bool	isValid () const

Protected Attributes
Size	myMaxSize
	The maximal number of memoized items.
double	myRatio
	The minimal ratio to remove if the maximal number of items is reached.
TimeStamp	myTimeStamp
	Current time.
std::unordered_map< Key, StoredValue >	myMap
	The map memoizing computations.
Size	myHits
	The number of hits since the last clean-up.
bool	myVerbose
	when 'true', traces some information.

Detailed Description

template<typename TKey, typename TValue>
class DGtal::TimeStampMemoizer< TKey, TValue >

Aim: A generic class to store a given maximum number of pairs (key, value). The class tends to memorize pairs which are accessed more frequently than others. It is thus a memoizer, which is used to memorize the result of costly computations. The memoization principle is simple: a timestamp is attached to a pair (key,value). Each time a query is made, if the item was memoized, the result is returned while the timestamp of the item is updated. User can also add or update a value in the memoizer, which updates also its timestamp. After adding a pair (key,value), if the maximal number of items is reached, at least the oldest half (or a fraction) of the items are deleted, leaving space for storing new pairs (key,value).

Description of template class 'TimeStampMemoizer'

Template Parameters

TKey	the type used for keys, must be hashable.
TValue	the type used for values, must be DefaultConstructible, CopyConstructible, Assignable.

Definition at line 74 of file TimeStampMemoizer.h.

Member Typedef Documentation

Key

template<typename TKey, typename TValue>

typedef TKey DGtal::TimeStampMemoizer< TKey, TValue >::Key

Definition at line 77 of file TimeStampMemoizer.h.

Self

template<typename TKey, typename TValue>

typedef TimeStampMemoizer< TKey, TValue > DGtal::TimeStampMemoizer< TKey, TValue >::Self

Definition at line 79 of file TimeStampMemoizer.h.

Size

template<typename TKey, typename TValue>

typedef std::size_t DGtal::TimeStampMemoizer< TKey, TValue >::Size

Definition at line 80 of file TimeStampMemoizer.h.

StoredValue

template<typename TKey, typename TValue>

typedef std::pair< Value, TimeStamp > DGtal::TimeStampMemoizer< TKey, TValue >::StoredValue

Definition at line 82 of file TimeStampMemoizer.h.

TimeStamp

template<typename TKey, typename TValue>

typedef DGtal::uint32_t DGtal::TimeStampMemoizer< TKey, TValue >::TimeStamp

Definition at line 81 of file TimeStampMemoizer.h.

Value

template<typename TKey, typename TValue>

typedef TValue DGtal::TimeStampMemoizer< TKey, TValue >::Value

Definition at line 78 of file TimeStampMemoizer.h.

Constructor & Destructor Documentation

TimeStampMemoizer() [1/3]

template<typename TKey, typename TValue>

DGtal::TimeStampMemoizer< TKey, TValue >::TimeStampMemoizer ( Size max_size = 0, double ratio = 0.5, bool verbose = false )

inline

Constructor.

Parameters

max_size	the maximum number of items that the memoizer will store.
ratio	is the real number between 0 and 1: when the maximum number is reached, at least the oldest ratio fraction of items are deleted from the memoizer.
verbose	if 'true', traces some informations.

Definition at line 98 of file TimeStampMemoizer.h.

      : myMaxSize( max_size ), myRatio( ratio ), myTimeStamp( 0 ),
        myMap( max_size ), myHits( 0 ), myVerbose( verbose )
    {}

References myHits, myMap, myMaxSize, myRatio, myTimeStamp, and myVerbose.

Referenced by operator=(), operator=(), TimeStampMemoizer(), and TimeStampMemoizer().

TimeStampMemoizer() [2/3]

template<typename TKey, typename TValue>

DGtal::TimeStampMemoizer< TKey, TValue >::TimeStampMemoizer ( const TimeStampMemoizer< TKey, TValue > & other )

default

Copy constructor.

Parameters

other

the object to clone.

References TimeStampMemoizer().

TimeStampMemoizer() [3/3]

template<typename TKey, typename TValue>

DGtal::TimeStampMemoizer< TKey, TValue >::TimeStampMemoizer ( TimeStampMemoizer< TKey, TValue > && other )

default

Move constructor.

Parameters

other

the object to clone.

References TimeStampMemoizer().

~TimeStampMemoizer()

template<typename TKey, typename TValue>

DGtal::TimeStampMemoizer< TKey, TValue >::~TimeStampMemoizer ( )

default

Destructor.

Member Function Documentation

cleanUp()

template<typename TKey, typename TValue>

void DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp ( )

inline

Clean-up the memoizer by removing a fraction of its oldest elements.

Definition at line 199 of file TimeStampMemoizer.h.

    {
      if ( myVerbose ) selfDisplay( trace.info() );
      Size nb = 0;
      TimeStamp threshold = (TimeStamp) std::max( (Size) myTimeStamp
                  - (Size) round( (myMaxSize + 0.5 * myHits) * myRatio ),
                  (Size) 0 );
      for ( auto it = myMap.begin(), itE = myMap.end(); it != itE; )
        if ( it->second.second <= threshold )
          {
            it = myMap.erase( it );
            ++nb;
          }
        else
          ++it;
      if ( myVerbose) trace.info() << " " << nb << " erased." << std::endl;
      myHits   = 0;
    }

References myHits, myMap, myMaxSize, myRatio, myTimeStamp, myVerbose, selfDisplay(), and DGtal::trace.

Referenced by set().

get()

template<typename TKey, typename TValue>

std::pair< Value, bool > DGtal::TimeStampMemoizer< TKey, TValue >::get ( const Key & key )

inline

Given a key, return the associated pair <value, true> if it is found, or return <dummy, false> where dummy is an arbitrary value.

Parameters

key

any key.

Returns

the associated pair <value, true> if the key is found, or return <dummy, false> where dummy is an arbitrary value.

Definition at line 175 of file TimeStampMemoizer.h.

    {
      auto it = myMap.find( key );
      if ( it == myMap.end() )
        return std::make_pair( Value(), false );
      it->second.second = myTimeStamp++;
      ++myHits;
      return std::make_pair( it->second.first, false );
    }

References myHits, myMap, and myTimeStamp.

hits()

template<typename TKey, typename TValue>

Size DGtal::TimeStampMemoizer< TKey, TValue >::hits ( ) const

inline

Returns

the number of successful hits in the memoizer (i.e. the number of times where a get( key ) succeeded and returned a pair (value, true)).

Definition at line 151 of file TimeStampMemoizer.h.

    {
      return myHits;
    }

References myHits.

isValid()

template<typename TKey, typename TValue>

bool DGtal::TimeStampMemoizer< TKey, TValue >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns

'true' if the object is valid, 'false' otherwise.

Definition at line 237 of file TimeStampMemoizer.h.

    {
      return ( myMaxSize > 0 );
    }

References myMaxSize.

map()

template<typename TKey, typename TValue>

const std::unordered_map< Key, StoredValue > & DGtal::TimeStampMemoizer< TKey, TValue >::map ( ) const

inline

Returns

a const reference to the map memoizing items.

Definition at line 163 of file TimeStampMemoizer.h.

    {
      return myMap;
    }

References myMap.

maxSize()

template<typename TKey, typename TValue>

Size DGtal::TimeStampMemoizer< TKey, TValue >::maxSize ( ) const

inline

Returns

the maximum number of items that can be memoized.

Definition at line 143 of file TimeStampMemoizer.h.

    {
      return myMaxSize;
    }

References myMaxSize.

operator=() [1/2]

template<typename TKey, typename TValue>

TimeStampMemoizer & DGtal::TimeStampMemoizer< TKey, TValue >::operator= ( const TimeStampMemoizer< TKey, TValue > & other )

default

Assignment.

Parameters

other

the object to copy.

References TimeStampMemoizer().

operator=() [2/2]

template<typename TKey, typename TValue>

TimeStampMemoizer & DGtal::TimeStampMemoizer< TKey, TValue >::operator= ( TimeStampMemoizer< TKey, TValue > && other )

default

Move assignment.

Parameters

other

the object to copy.

References TimeStampMemoizer().

selfDisplay()

template<typename TKey, typename TValue>

void DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

Definition at line 225 of file TimeStampMemoizer.h.

    {
      out << "[TimeStampMemoizer " << myMap.size() << "/" << myMaxSize << " items"
          << " time=" << myTimeStamp << " ratio=" << myRatio
          << " hits=" << myHits 
          << "]";
    }

References myHits, myMap, myMaxSize, myRatio, and myTimeStamp.

Referenced by cleanUp().

set()

template<typename TKey, typename TValue>

void DGtal::TimeStampMemoizer< TKey, TValue >::set ( const Key & key, const Value & value )

inline

Memoizes (or update) a pair key and value.

Parameters

key	any key.
value	any value.

Note

if the maximum number of memoized items is reached, forces a clean-up of a the memoizer.

Definition at line 192 of file TimeStampMemoizer.h.

    {
      if ( myMap.size() >= myMaxSize ) cleanUp();
      myMap[ key ] = std::make_pair( value, myTimeStamp++ );
    }

References cleanUp(), myMap, myMaxSize, and myTimeStamp.

size()

template<typename TKey, typename TValue>

Size DGtal::TimeStampMemoizer< TKey, TValue >::size ( ) const

inline

Returns

the current number of memoized items.

Definition at line 137 of file TimeStampMemoizer.h.

    {
      return myMap.size();
    }

References myMap.

timeStamp()

template<typename TKey, typename TValue>

Size DGtal::TimeStampMemoizer< TKey, TValue >::timeStamp ( ) const

inline

Returns

the current time stamp.

Definition at line 157 of file TimeStampMemoizer.h.

    {
      return myTimeStamp;
    }

References myTimeStamp.

Field Documentation

myHits

template<typename TKey, typename TValue>

Size DGtal::TimeStampMemoizer< TKey, TValue >::myHits

protected

The number of hits since the last clean-up.

Definition at line 253 of file TimeStampMemoizer.h.

Referenced by cleanUp(), get(), hits(), selfDisplay(), and TimeStampMemoizer().

myMap

template<typename TKey, typename TValue>

std::unordered_map< Key, StoredValue > DGtal::TimeStampMemoizer< TKey, TValue >::myMap

protected

The map memoizing computations.

Definition at line 251 of file TimeStampMemoizer.h.

Referenced by cleanUp(), get(), map(), selfDisplay(), set(), size(), and TimeStampMemoizer().

myMaxSize

template<typename TKey, typename TValue>

Size DGtal::TimeStampMemoizer< TKey, TValue >::myMaxSize

protected

The maximal number of memoized items.

Definition at line 245 of file TimeStampMemoizer.h.

Referenced by cleanUp(), isValid(), maxSize(), selfDisplay(), set(), and TimeStampMemoizer().

myRatio

template<typename TKey, typename TValue>

double DGtal::TimeStampMemoizer< TKey, TValue >::myRatio

protected

The minimal ratio to remove if the maximal number of items is reached.

Definition at line 247 of file TimeStampMemoizer.h.

Referenced by cleanUp(), selfDisplay(), and TimeStampMemoizer().

myTimeStamp

template<typename TKey, typename TValue>

TimeStamp DGtal::TimeStampMemoizer< TKey, TValue >::myTimeStamp

protected

Current time.

Definition at line 249 of file TimeStampMemoizer.h.

Referenced by cleanUp(), get(), selfDisplay(), set(), timeStamp(), and TimeStampMemoizer().

myVerbose

template<typename TKey, typename TValue>

bool DGtal::TimeStampMemoizer< TKey, TValue >::myVerbose

protected

when 'true', traces some information.

Definition at line 255 of file TimeStampMemoizer.h.

Referenced by cleanUp(), and TimeStampMemoizer().

---

The documentation for this class was generated from the following file:

• TimeStampMemoizer.h