"LeastRecentlyUsedCache" (Data Structure)

"LeastRecentlyUsedCache"

represents a fixed-size cache where the keys and values are general expressions.

Details

A fixed-size cache table stores individual values that can be retrieved by the use of a key:

	CreateDataStructure["LeastRecentlyUsedCache",capacity]	create a new empty "LeastRecentlyUsedCache" for a total of capacity values
	CreateDataStructure["LeastRecentlyUsedCache",elems]	create a new "LeastRecentlyUsedCache" containing elems
	Typed[x,"LeastRecentlyUsedCache"]	give x the type "LeastRecentlyUsedCache"

For a data structure of type "LeastRecentlyUsedCache", the following operations can be used:

ds["Capacity"]	the maximum number of key-value pairs that can be stored in ds	time: O(1)
ds["Copy"]	return a copy of ds	time: O(n)
ds["EmptyQ"]	return True if ds contains no key-value pairs	time: O(1)
ds["Insert",keyvalue]	add key to ds with the associated value and return True if something was evicted from the cache	time: O(1)
ds["KeyDrop",key]	drop key and its value from ds	time: O(1)
ds["KeyDropAll"]	drop all the keys and their values from ds	time: O(n)
ds["KeyExistsQ",key]	True, if the key exists in ds	time: O(1)
ds["Keys"]	return the keys in ds as a list	time: O(n)
ds["Length"]	the number of key-value pairs stored in ds	time: O(1)
ds["Lookup",key]	return the value stored with key in ds and make this key the most recently used element; if the key is not found, return a Missing object	time: O(1)
ds["Lookup",key,defFun]	return the value stored with key in ds and make this key the most recently used element; if the key is not found, return defFun[key]	time: O(1)
ds["Peek"]	return the most recent value stored in ds	time: O(1)
ds["Peek",key]	return the value stored with key in ds; do not make this key the most recently used element	time: O(1)
ds["RemoveOldest"]	remove the oldest key-value pair in ds	time: O(1)
ds["Values"]	return the values in ds as a list	time: O(n)
ds["Visualization"]	return a visualization of ds	time: O(n)

	ds_i===ds_j	True, if ds_i equals ds_j
	FullForm[ds]	full form of ds
	Information[ds]	information about ds
	InputForm[ds]	input form of ds
	Normal[ds]	convert ds to a normal expression

When the "LeastRecentlyUsedCache" stores the maximum number of key-value pairs, any new insertions will cause the least recently used pairs to be evicted.

open allclose all

A new "LeastRecentlyUsedCache" can be created with CreateDataStructure:

The number of key-value pairs that are stored:

The maximum number of key-value pairs that can be stored:

Insert a key with a value:

There is one key stored:

Test if a key is present:

Look up a value:

When a key is not found, a Missing object is returned:

Store more elements in the cache and show them:

Look up a value:

The expression version shows the most recently used:

Insert another key with a value:

The expression version shows that a key-value pair was evicted from the cache:

A visualization of the "LeastRecentlyUsedCache" shows which is the most recently used key-value:

A new "LeastRecentlyUsedCache" can be created with CreateDataStructure:

Information about the data structure ds:

Top