コンテンツにスキップ

0753: 弱参照キャッシュ

問題

ガベージコレクションの原則では、ルートから到達可能なオブジェクトは回収されません。 CPython はこれを参照カウントで実現しており、オブジェクトへの参照の個数が 0 になった時点で即座に回収します。 通常の辞書でオブジェクトをキャッシュすると、辞書自体が参照（強参照）を持つためオブジェクトは常に到達可能となり、使われなくなってもエントリが残り続けます。 一方、弱参照は参照カウントを増やさない参照です。 キャッシュを弱参照で構成すれば、「他から使われている間だけキャッシュされる」動作を実現できます。

次の 2 つのクラスを実装してください。

  • Node(name):name 属性を持つクラス。repr() は Node('a') の形式とする。
  • NodeCache():名前からノードへのキャッシュ。
    • get(name):名前 name のノードが生存していればそれを返す。なければ新しく生成し、登録して返す。
    • len(cache):生存しているエントリの個数を返す。
    • name in cache:名前 name のノードが生存しているかを返す。
    • キャッシュはノードへの強参照を持ってはならない。weakref.WeakValueDictionary（または weakref.ref）を使う。

制約

  • CPython を前提とし、最後の強参照が消えた時点で即座に回収されることを利用してかまいません（トレース方式の GC を使う処理系では、以下の例は決定的に動きません）。
  • 名前は文字列とします。
  • スレッド安全性は考えなくてかまいません。

例

>>> cache = NodeCache()
>>> a = cache.get("a")
>>> a
Node('a')
>>> b = cache.get("b")
>>> cache.get("a") is a  # 生存している間は同一のノードが返る
True
>>> len(cache)
2
>>> del a                # 最後の強参照を消す
>>> len(cache)
1
>>> "a" in cache
False
>>> "b" in cache
True
>>> c = cache.get("a")   # 回収済みなので新しく生成される
>>> len(cache)
2

発展

  1. weakref.WeakValueDictionary を使わずに、weakref.ref と削除時コールバックだけで同じ動作を実装してください。
  2. Node に __slots__ = ("name",) を追加すると get() が失敗します。原因を確かめ、弱参照と両立するように直してください。

参考