WOLFRAM

Wolfram Language & System Documentation Center

"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
    CreateDataStructure["LeastRecentlyUsedCache",cache, f]create a new "LeastRecentluUsedCache" with specified evict function f
    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 dstime: O(1)
    ds["Copy"]return a copy of dstime: O(n)
    ds["EmptyQ"]return True if ds contains no key-value pairstime: O(1)
    ds["Insert",keyvalue]add key to ds with the associated value and return True if something was evicted from the cachetime: 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 dstime: O(1)
    ds["Keys"]return the keys in ds as a listtime: O(n)
    ds["Length"]the number of key-value pairs stored in dstime: 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 objecttime: 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 dstime: O(1)
    ds["Peek",key]return the value stored with key in ds; do not make this key the most recently used elementtime: O(1)
    ds["RemoveOldest"]remove the oldest key-value pair in dstime: O(1)
    ds["Values"]return the values in ds as a listtime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    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.

Examples

open all close all

Basic Examples  (2)

A new "LeastRecentlyUsedCache" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["LeastRecentlyUsedCache", 3]

The number of key-value pairs that are stored:

Wolfram Language code: ds["Length"]

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

Wolfram Language code: ds["Capacity"]

Insert a key with a value:

Wolfram Language code: ds["Insert", f[1] -> 1]

There is one key stored:

Wolfram Language code: ds["Length"]

Test if a key is present:

Wolfram Language code: ds["KeyExistsQ", f[1]]

Look up a value:

Wolfram Language code: ds["Lookup", f[1]]

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

Wolfram Language code: ds["Lookup", f[2]]

Store more elements in the cache and show them:

Wolfram Language code: ds["Insert", f[2] -> 2]; ds["Insert", f[3] -> 3]; Normal[ds]

Look up a value:

Wolfram Language code: ds["Lookup", f[1]];

The expression version shows the most recently used:

Wolfram Language code: Normal[ds]

Insert another key with a value:

Wolfram Language code: ds["Insert", f[4] -> 4]

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

Wolfram Language code: Normal[ds]

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

Wolfram Language code: ds = CreateDataStructure["LeastRecentlyUsedCache", 3]; ds["Insert", f[1] -> 1]; ds["Insert", f[2] -> 2]; ds["Insert", f[3] -> 3]; ds["Visualization"]

Scope  (2)

Information  (1)

A new "LeastRecentlyUsedCache" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["LeastRecentlyUsedCache", 3]

Information about the data structure ds:

Wolfram Language code: Information[ds]

Eviction  (1)

Create a function to track evictions from a cache:

Wolfram Language code: evictions = 0; evicted = {}; trackEvictions = Function[{key, val}, evictions++; AppendTo[evicted, key -> val] ];

Create a new "LeastRecentlyUsedCache" with capacity two and a function to track evictions:

Wolfram Language code: ds = CreateDataStructure["LeastRecentlyUsedCache", 2, trackEvictions ]

Insert two key-value pairs in the cache:

Wolfram Language code: ds["Insert", 1 -> "one" ]; ds["Insert", 2 -> "two"];

Cache is now full. If a new element is inserted, it will evict the least recently used entry:

Wolfram Language code: ds["Insert", 3 -> "three"]

Verify that the eviction of the element:

Wolfram Language code: Normal[ds]

The number of evictions:

Wolfram Language code: evictions

The evicted element:

Wolfram Language code: evicted