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 >:

[legend]

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 )
    {}

◆ 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.

◆ 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.

◆ ~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 DGtal::Trace::info(), DGtal::TimeStampMemoizer< TKey, TValue >::myHits, DGtal::TimeStampMemoizer< TKey, TValue >::myMap, DGtal::TimeStampMemoizer< TKey, TValue >::myMaxSize, DGtal::TimeStampMemoizer< TKey, TValue >::myRatio, DGtal::TimeStampMemoizer< TKey, TValue >::myTimeStamp, DGtal::TimeStampMemoizer< TKey, TValue >::myVerbose, DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay(), and DGtal::trace.

Referenced by DGtal::TimeStampMemoizer< TKey, TValue >::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 DGtal::TimeStampMemoizer< TKey, TValue >::myHits, DGtal::TimeStampMemoizer< TKey, TValue >::myMap, and DGtal::TimeStampMemoizer< TKey, TValue >::myTimeStamp.

Referenced by DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isComplementaryFullyConvex(), and DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isFullyConvex().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::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 DGtal::TimeStampMemoizer< TKey, TValue >::myMaxSize.

Referenced by DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isComplementaryFullyConvex(), and DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isFullyConvex().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::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 DGtal::TimeStampMemoizer< TKey, TValue >::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.

◆ 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.

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::myHits, DGtal::TimeStampMemoizer< TKey, TValue >::myMap, DGtal::TimeStampMemoizer< TKey, TValue >::myMaxSize, DGtal::TimeStampMemoizer< TKey, TValue >::myRatio, and DGtal::TimeStampMemoizer< TKey, TValue >::myTimeStamp.

Referenced by DGtal::TimeStampMemoizer< TKey, TValue >::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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp(), DGtal::TimeStampMemoizer< TKey, TValue >::myMap, DGtal::TimeStampMemoizer< TKey, TValue >::myMaxSize, and DGtal::TimeStampMemoizer< TKey, TValue >::myTimeStamp.

Referenced by DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isComplementaryFullyConvex(), and DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isFullyConvex().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::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 DGtal::TimeStampMemoizer< TKey, TValue >::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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp(), DGtal::TimeStampMemoizer< TKey, TValue >::get(), DGtal::TimeStampMemoizer< TKey, TValue >::hits(), and DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp(), DGtal::TimeStampMemoizer< TKey, TValue >::get(), DGtal::TimeStampMemoizer< TKey, TValue >::map(), DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay(), DGtal::TimeStampMemoizer< TKey, TValue >::set(), and DGtal::TimeStampMemoizer< TKey, TValue >::size().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp(), DGtal::TimeStampMemoizer< TKey, TValue >::isValid(), DGtal::TimeStampMemoizer< TKey, TValue >::maxSize(), DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay(), and DGtal::TimeStampMemoizer< TKey, TValue >::set().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp(), and DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp(), DGtal::TimeStampMemoizer< TKey, TValue >::get(), DGtal::TimeStampMemoizer< TKey, TValue >::selfDisplay(), DGtal::TimeStampMemoizer< TKey, TValue >::set(), and DGtal::TimeStampMemoizer< TKey, TValue >::timeStamp().

◆ 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 DGtal::TimeStampMemoizer< TKey, TValue >::cleanUp().

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

TimeStampMemoizer.h

Public Types

Public Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Key

◆ Self

◆ Size

◆ StoredValue

◆ TimeStamp

◆ Value

Constructor & Destructor Documentation

◆ TimeStampMemoizer() [1/3]

◆ TimeStampMemoizer() [2/3]

◆ TimeStampMemoizer() [3/3]

◆ ~TimeStampMemoizer()

Member Function Documentation

◆ cleanUp()

◆ get()

◆ hits()

◆ isValid()

◆ map()

◆ maxSize()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ selfDisplay()

◆ set()

◆ size()

◆ timeStamp()

Field Documentation

◆ myHits

◆ myMap

◆ myMaxSize

◆ myRatio

◆ myTimeStamp

◆ myVerbose