DGtal  1.4.beta
Public Types | Public Member Functions | Protected Attributes
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 >:
[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, TimeStampStoredValue
 

Public Member Functions

 TimeStampMemoizer (Size max_size=0, double ratio=0.5, bool verbose=false)
 
 TimeStampMemoizer (const TimeStampMemoizer &other)=default
 
 TimeStampMemoizer (TimeStampMemoizer &&other)=default
 
TimeStampMemoizeroperator= (const TimeStampMemoizer &other)=default
 
TimeStampMemoizeroperator= (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. More...
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 

Protected Attributes

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

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
TKeythe type used for keys, must be hashable.
TValuethe 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_sizethe maximum number of items that the memoizer will store.
ratiois 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.
verboseif 'true', traces some informations.

Definition at line 98 of file TimeStampMemoizer.h.

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

◆ TimeStampMemoizer() [2/3]

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

Copy constructor.

Parameters
otherthe object to clone.

◆ TimeStampMemoizer() [3/3]

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

Move constructor.

Parameters
otherthe 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.

200  {
201  if ( myVerbose ) selfDisplay( trace.info() );
202  Size nb = 0;
203  TimeStamp threshold = (TimeStamp) std::max( (Size) myTimeStamp
204  - (Size) round( (myMaxSize + 0.5 * myHits) * myRatio ),
205  (Size) 0 );
206  for ( auto it = myMap.begin(), itE = myMap.end(); it != itE; )
207  if ( it->second.second <= threshold )
208  {
209  it = myMap.erase( it );
210  ++nb;
211  }
212  else
213  ++it;
214  if ( myVerbose) trace.info() << " " << nb << " erased." << std::endl;
215  myHits = 0;
216  }
void selfDisplay(std::ostream &out) const
std::ostream & info()
Trace trace
Definition: Common.h:153
int max(int a, int b)
HalfEdgeDataStructure::Size Size

References DGtal::Trace::info(), max(), 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
keyany 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.

176  {
177  auto it = myMap.find( key );
178  if ( it == myMap.end() )
179  return std::make_pair( Value(), false );
180  it->second.second = myTimeStamp++;
181  ++myHits;
182  return std::make_pair( it->second.first, false );
183  }

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.

152  {
153  return myHits;
154  }

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.

238  {
239  return ( myMaxSize > 0 );
240  }

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.

164  {
165  return myMap;
166  }

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.

144  {
145  return myMaxSize;
146  }

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
otherthe 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
otherthe 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
outthe output stream where the object is written.

Definition at line 225 of file TimeStampMemoizer.h.

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

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
keyany key.
valueany 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.

193  {
194  if ( myMap.size() >= myMaxSize ) cleanUp();
195  myMap[ key ] = std::make_pair( value, myTimeStamp++ );
196  }
void cleanUp()
Clean-up the memoizer by removing a fraction of its oldest elements.

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.

138  {
139  return myMap.size();
140  }

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.

158  {
159  return myTimeStamp;
160  }

References DGtal::TimeStampMemoizer< TKey, TValue >::myTimeStamp.

Field Documentation

◆ myHits

template<typename TKey , typename TValue >
Size DGtal::TimeStampMemoizer< TKey, TValue >::myHits
protected

◆ myMap

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

◆ myMaxSize

template<typename TKey , typename TValue >
Size DGtal::TimeStampMemoizer< TKey, TValue >::myMaxSize
protected

◆ 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

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