木系のアルゴリズムをpythonで実装しようとしていたら時間が無くなってしまったので小ネタ。
木系のアルゴリズムで、Nodeを共有したい場合ってありますよね。
下の図のオレンジ色のノードみたいに。
Nodeを拡張する場合に、拡張したいNodeと同じNodeが既に存在しているかどうかを調べるのも結構面倒なので、そこをうまくやれるといいですよね。
Nodeにkeyを指定しておいて、同じkeyがあったら既存のインスタンスを返す、といった実装をしようと思ったら、metaclassを使えばできる、という小ネタです。
# 同じkeyをもつノードは一つにしたい場合
class NodeType(type):
_instances = {}
def __call__(cls, *args, key, **kwargs):
# stateが同じものがあれば、すでに作られたインスタンスを返し、なければ新規作成
if key not in cls._instances:
instance = super(NodeType, cls).__call__(key=key, *args, **kwargs)
cls._instances[key] = instance
return cls._instances[key]
class Node(metaclass=NodeType):
def __init__(self, key, name):
self.key = key
self.name = name
self.id = id(self)
def __repr__(self):
return 'id: {}, name {}, key: {}'.format(self.id, self.name, self.key)
node1 = Node(key=1, name='1'); print(node1)
node2 = Node(key=2, name='2'); print(node2)
node1_2 = Node(key=1, name='1_2'); print(node1_2)
上記のようにtypeを継承したクラスを作り、metaclassを使うことで、実現可能です。
id: 1850359362728, name 1, key: 1
id: 1850359363008, name 2, key: 2
id: 1850359362728, name 1, key: 1
作られたインスタンスは、keyによって管理されています。
NodeType._instances
{1: id: 1850359362728, name 1, key: 1, 2: id: 1850359363008, name 2, key: 2}
時間がなさ過ぎたので以上。。。
この方法だと、NodeType._instancesにも参照が生じてしまうので、
今後は、弱参照をうまくつかって、ガベージコレクションがうまく働く方法を検討したいです。
(2017.12.19追記)
上記の方法だと、
del node2
node2_2 = Node(key=2, name='2_2'); print(node2_2)
このように一度消して再作成したつもりでも、
id: 1850359363008, name 2, key: 2
となり、nameやidの情報を見てわかる通り、最初に作成したインスタンスが生き続けています。
NodeType._instances で参照が残っているので、当たり前と言えば当たり前かもしれませんが。
そこで、弱参照を使ってこの問題に対応することを考えます。
pythonでは、weakrefライブラリを使うことで弱参照を扱えます。
下記にコードは書きますが、最初の4行しか変えていません。
from weakref import WeakValueDictionary
# 同じkeyをもつノードは一つにしたい場合
class NodeType(type):
_instances = WeakValueDictionary()
def __call__(cls, *args, key, **kwargs):
# stateが同じものがあれば、すでに作られたインスタンスを返し、なければ新規作成
if key not in cls._instances:
instance = super(NodeType, cls).__call__(key=key, *args, **kwargs)
cls._instances[key] = instance
return cls._instances[key]
class Node(metaclass=NodeType):
def __init__(self, key, name):
self.key = key
self.name = name
self.id = id(self)
def __repr__(self):
return 'id: {}, name {}, key: {}'.format(self.id, self.name, self.key)
node1 = Node(key=1, name='1'); print(node1)
node2 = Node(key=2, name='2'); print(node2)
node1_2 = Node(key=1, name='1_2'); print(node1_2)
NoteTypeクラスの中で、_instancesを辞書型の代わりに
WeakValueDictionaryを使っています。
id: 1945971777040, name 1, key: 1
id: 1945971777432, name 2, key: 2
id: 1945971777040, name 1, key: 1
今度は、一度消して再作成してみると、
del node2
node2_2 = Node(key=2, name='2_2'); print(node2_2)
id: 1945971719192, name 2_2, key: 2
となり、インスタンスが新しく作られていることが確認できます。