"LeastRecentlyUsedCache" (データ構造)

"LeastRecentlyUsedCache"

キーと値が一般式である，固定サイズのキャッシュを表す．

詳細

  • 固定サイズのキャッシュテーブルは，キーを使って取り出すことができる個々の値を保存する．
  • CreateDataStructure["LeastRecentlyUsedCache",capacity]capacity 値全体のために新しい空の "LeastRecentlyUsedCache"を作成する
    CreateDataStructure["LeastRecentlyUsedCache",elems]elems を含む新しい"LeastRecentlyUsedCache"を作成する
    CreateDataStructure["LeastRecentlyUsedCache",cache, f]指定のエビクション関数 f を含む新しい"LeastRecentlyUsedCache"を作成する
    Typed[x,"LeastRecentlyUsedCache"]x に"LeastRecentlyUsedCache"型を与える
  • "LeastRecentlyUsedCache"型のデータ構造には，以下の演算が使える．
  • ds["Capacity"]ds に保存できるキーと値のペアの最大数time: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["EmptyQ"]ds にキーと値のペアが含まれない場合にはTrueを返すtime: O(1)
    ds["Insert",keyvalue]関連の value と一緒に key を ds に加え，何かがキャッシュから強制削除された場合にはTrueを返すtime: O(1)
    ds["KeyDrop",key]key とその値を ds から省くtime: O(1)
    ds["KeyDropAll"]すべてのキーとその値を ds から省くtime: O(n)
    ds["KeyExistsQ",key]key が ds 内に存在する場合にはTruetime: O(1)
    ds["Keys"]ds のキーをリストとして返すtime: O(n)
    ds["Length"]ds に保存されたキーと値のペアの数time: O(1)
    ds["Lookup",key]ds 内に key と一緒に保存される値を返し，このキーを一番最後に使われた値とする．キーが見付からない場合には，Missingオブジェクトを返すtime: O(1)
    ds["Lookup",key,defFun]ds 内に key と一緒に保存される値を返し，このキーを一番最後に使われた値とする．キーが見付からない場合には，defFun[key]を返すtime: O(1)
    ds["Peek"]ds に保存される最新の値を返すtime: O(1)
    ds["Peek",key]ds 内に key と一緒に保存される値を返す．このキーは一番最後に使われた要素とはしない．time: O(1)
    ds["RemoveOldest"]ds 内の最も古いキーと値のペアを削除するtime: O(1)
    ds["Values"]ds の値をリストとして返すtime: O(n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する
  • "LeastRecentlyUsedCache"が最大数のキーと値のペアを保存するとき，任意の新たな挿入によって，最近最も使われていないペアが強制削除される．

例題

すべて開くすべて閉じる

例  (2)

新しい"LeastRecentlyUsedCache"は，CreateDataStructureを使って作成できる：

保存されているキーと値のペアの数：

保存できるキーと値のペアの最大数：

キーを値と一緒に挿入する：

保存されているキーは1個である：

キーが存在するかどうかを検証する：

値を調べる：

キーが見付からない場合には，Missingオブジェクトが返される：

キャッシュにもっと要素を保存し，それらを表示する：

値を調べる：

式のバージョンは，一番最後に使われたものを表示する：

キーをもう1つ値と一緒に挿入する：

式のバージョンは，キーと値のペアがキャッシュから強制削除されたことを示す：

"LeastRecentlyUsedCache"の可視化は，どれが一番最後に使われたキーと値のペアであるかを示す：

スコープ  (2)

情報  (1)

新しい"LeastRecentlyUsedCache"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

エビクション  (1)

キャッシュからのエビクションを追跡する関数を作成する：

容量が2でエビクションを追跡する関数を含む新しい"LeastRecentlyUsedCache"を作成する：

キャッシュに2つのキーの値のペアを挿入する：

キャッシュが満杯になった．新しい要素が挿入されると，最長時間未使用の項目が削除される：

要素が削除されたことを確かめる：

エビクションの数：

削除された要素：