木系のアルゴリズムを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

となり、インスタンスが新しく作られていることが確認できます。