字典中的复合键

Question

我正在维护一个字典，用来记录一对对象之间的相似度。
比如，这个字典可能长这样：

similarities = {
 p1: {p2: v12, p3:v13, p4:v14},
 p2: {p1: v21, p3:v23, p4:v24},
 p3: {p1: v31, p2:v32, p4:v34},
 p4: {p1: v41, p2:v42, p4:v43}
}

需要注意的是，相似度的测量是对称的。因此，similarities[p1][p2] 和 similarities[p2][p1] 是一样的，也就是说 v12 == v21。

有时候，我需要从 similarities[p1] 中删除 p2；在这个过程中，我还需要从 similarities 中所有的内部字典里删除 p1 和 p2。
这真是麻烦而且效率低下。

所以，除了维护一个对称的字典，还有没有办法用一个复合键来维护字典，这样我就可以查找 similarities[p1,p2] 呢？

我不能使用 tuple，因为 (p1, p2) != (p2, p1)，而且我也不知道怎么给这个元组排序。

我能想到的唯一其他容器是 frozenset，但这也不行，因为在 similarities 中可能还有其他键包含 p1 或 p2。那么我该用什么容器来解决这个问题呢？

技术信息：

• python 2.7
• 这个“复合键”中总是会有两个元素

谢谢

Answer 1

如果这些 p_ 对象的类型支持排序的话，你能不能用一个包含两个元素的元组，并且这两个元素总是按从小到大的顺序排列呢？

Answer 2

我可能会直接使用一个 frozenset，前提是这些对象是可以被哈希的。

另外，如果这些对象有明确且一致的顺序，你可以把它们放在一个按照这个顺序排序的元组里。如果你想的话，可以写一个小的 dict 子类，让它自动帮你处理这些事情。

或者，你可以像这样做：

class SymmetricDict(dict):
    def __getitem__(self, key):
        if key in self:
            return dict.__getitem__(self, key)
        a, b = key
        return dict.__getitem__(self, (b, a))

对于 __setitem__ 也是类似的。

Answer 3

我觉得使用 frozenset 是唯一合乎逻辑的解决方案。你可以通过一个简单的方式，找到只匹配其中一个值的键，这里用到了集合交集的测试：

def remove_ab(ab, similarities):
    return {k:v for k, v in similarities.items() if not ab & k}

similarities = {frozenset({1, 2}): "v12",
                frozenset({1, 3}): "v13",
                frozenset({2, 3}): "v23",
                frozenset({3, 4}): "v34"}

similarities = remove_ab(frozenset({1, 2}), similarities
print(similarities) # output is {frozenset({3, 4}): 'v34'}