2

我怎样才能实现frozensets 的 Multiton 设计模式，无论它frozenset是如何创建的？

我正在寻找的是行为就像 的类frozenset，但它保证“完全实习”：对于任何两个实例，如果a == bthen a is b。

这个问题的答案似乎为传递给构造函数的每个参数 生成了一个实例（并且似乎还假设这些是可散列的）。但是一个给定的frozenset可以用许多不同的方式构造：构造函数可以得到具有不同元素顺序的元组，或者不可散列的列表；或者您可以使用诸如 a.union(b) 之类的运算符来创建冻结集等。

动机自然是 - 试图节省内存。我有一个图，其中许多顶点由（除其他外）recurring frozensets 标记。该图是通过从旧的顶点创建新的顶点来“增长”的，而新frozenset的 s 是通过从旧的顶点中添加或删除元素来获得的。

非常感谢！

4

2 回答 2

0

这是一种可能的解决方案。

class Uniquifier(object) :
    """
    This class accepts an immutable object and returns a "canonical" instance of it, if one exists, or keeps it in store as that canonical instance. This is used as a kind of clunky multiton implementation.

    Of course instances are not destroyed until this object is destroyed.
    """
    def __init__(self):
        self._universe = {}


    def uniquify(self, item):
        try :
            return self._universe[item]
        except KeyError :
            self._universe[item] = item
            return self._universe[item]

运行这个：

a = frozenset([3,5])
b = frozenset([5,3])
c = frozenset([3]).union([5])
print a==b, b==c
print a is b, b is c, a is c

结果是：

True True
False False False

但是这个：

universe = Uniquifier()
a = universe.uniquify(frozenset([3,5]))
b = universe.uniquify(frozenset([5,3]))
c = universe.uniquify(frozenset([3]).union([5]))
print a == b, b==c
print a is b, b is c, a is c

给

True True
True True True

如预期的。

我希望使用一些 pythonic 魔法可以将 Uniquifier 逻辑“隐藏在幕后”，但我想这具有简单透明的优点。

于 2019-09-15T06:44:18.750 回答
0

您可以使用该__new__方法在frozenset. 我引用文档：

new () 主要是为了允许不可变类型（如 int、str 或 tuple）的子类自定义实例创建。它也通常在自定义元类中被覆盖，以自定义类创建。

这个想法是缓存创建的每个包装器，并始终为相同的frozenset.

有一个小技巧：frozenset那些本身就是frozensets 的元素，它们也应该被包裹起来。

class FrozenSetWrapper:
    _cache = {}

    def __new__(cls, iterable=[]):
        fs = frozenset(FrozenSetWrapper(e) if isinstance(e, frozenset) else e
                        for e in iterable) # wrap recursively
        fsw = FrozenSetWrapper._cache.get(fs)
        if fsw is None: # was not in cache
            fsw = super(FrozenSetWrapper, cls).__new__(cls) # create an object
            fsw._fs = fs # init
            fsw.__doc__ = fs.__doc__
            FrozenSetWrapper._cache[fs] = fsw # cache
        return fsw # and return

例子：

f1 = FrozenSetWrapper([1,2,3])
f2 = FrozenSetWrapper([1,2,3])

print(f1, f2)
# <__main__.FrozenSetWrapper object at 0x7f7894f2fa90> <__main__.FrozenSetWrapper object at 0x7f7894f2fa90>

现在，我们必须重新实现frozenset获得完美匹配的方法。这对他们中的一些人来说很容易：只需将工作委托给被包装的frozenset：

def __repr__(self):
    return self._fs.__repr__()

def __iter__(self):
    return self._fs.__iter__()

...

但是对于某些方法，您必须处理frozensetand FrozenSetWrapper：

def __contains__(self, e):
    elif isinstance(e, frozenset):
        e = FrozenSetWrapper(e)

    return self._fs.contains(e)

def __eq__(self, other):
    if isinstance(other, FrozenSetWrapper):
        return self is other
    elif isinstance(other, frozenset)
        return self._fs == other
    else:
        return False

...

或返回类型：

def __and__(self, other):
    if isinstance(other, FrozenSetWrapper):
        return FrozenSetWrapper(self._fs.__and__(other._fs))
    elif isinstance(other, frozenset):
        return FrozenSetWrapper(self._fs.__and__(other))
    else:
        raise TypeError("unsupported operand type(s) ...")

实习的想法是有道理的，但由于边缘情况，实施可能会很棘手。

于 2019-09-15T11:39:53.173 回答