对称字典，满足 d[a][b] == d[b][a]

Question

我有一个用Python写的算法，它可以为一对值创建度量，其中 m(v1, v2) == m(v2, v1)，也就是说这个度量是对称的。我想到可以用一个字典的字典来存储这些值，这样可以节省内存，并且可以用任意顺序轻松地检索这些值。我喜欢继承一些东西，理想情况下，我想写一个 symmetric_dict，让 s_d[v1][v2] 总是等于 s_d[v2][v1]。这可以通过检查两个值哪个大来实现，然后把它们调换位置，这样较小的值总是排在前面。比如，当我调用 s_d[5][2] = 4 时，字典会自动把它们调换成 s_d[2][5] = 4，取数据时也是这样。

我也很乐意接受更好的数据结构，但我更希望能实现一个“是一个”的关系，而不是单纯使用字典并预处理一些函数参数。

Answer 1

用嵌套索引来处理这个问题会非常困难。更好的方法是用元组作为键。这样，元组可以被排序，然后可以访问一个封装好的 dict 来获取值。

d[2, 5] = 4
print d[5, 2]

Answer 2

你可以使用一个frozenset作为字典的键：

>>> s_d = {}
>>> s_d[frozenset([5,2])] = 4
>>> s_d[frozenset([2,5])]
4

写一个字典的子类其实很简单，这个子类可以接受可迭代的对象作为键，然后在存储值的时候把它们转换成frozenset：

class SymDict(dict):
    def __getitem__(self, key):
        return dict.__getitem__(self, frozenset(key))

    def __setitem__(self, key, value):
        dict.__setitem__(self, frozenset(key), value)

这样你就可以得到：

>>> s_d = SymDict()
>>> s_d[5,2] = 4
>>> s_d[2,5]
4

Answer 3

这里有一个稍微不同的做法，看起来很有前景。虽然这个 SymDict 类不是 dict 的子类，但它的表现大部分和 dict 很像，而且只涉及一个私有的字典。我觉得一个有趣的特点是，它保留了你想要的自然 [][] 查找语法。

class SymDict(object):
    def __init__(self, *args, **kwrds):
        self._mapping = _SubSymDict(*args, **kwrds)
    def __getitem__(self, key1):
        self._mapping.set_key1(key1)
        return self._mapping
    def __setitem__(self, key1, value):
        raise NotImplementedError
    def __str__(self):
        return '_mapping: ' + self._mapping.__str__()
    def __getattr__(self, name):
        return getattr(self._mapping, name)

class _SubSymDict(dict):
    def __init__(self, *args, **kwrds):
        dict.__init__(self, *args, **kwrds)
    def set_key1(self, key1):
        self.key1 = key1
    def __getitem__(self, key2):
        return dict.__getitem__(self, frozenset((self.key1, key2)))
    def __setitem__(self, key2, value):
        dict.__setitem__(self, frozenset((self.key1, key2)), value)

symdict = SymDict()
symdict[2][4] = 24
symdict[4][2] = 42

print 'symdict[2][4]:', symdict[2][4]
# symdict[2][4]: 42
print 'symdict[4][2]:', symdict[4][2]
# symdict[4][2]: 42
print 'symdict:', symdict
# symdict: _mapping: {frozenset([2, 4]): 42}

print symdict.keys()
# [frozenset([2, 4])]