WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"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を使って作成できる：

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

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

Wolfram Language code: ds["Length"]

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

Wolfram Language code: ds["Capacity"]

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

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

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

Wolfram Language code: ds["Length"]

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

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

値を調べる：

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

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

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

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

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

値を調べる：

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

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

Wolfram Language code: Normal[ds]

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

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

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

Wolfram Language code: Normal[ds]

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

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

スコープ  (2)

情報  (1)

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

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

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

Wolfram Language code: Information[ds]

エビクション  (1)

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

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

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

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

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

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

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

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

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

Wolfram Language code: Normal[ds]

エビクションの数：

Wolfram Language code: evictions

削除された要素：

Wolfram Language code: evicted