python可逆字典

Question

我想在Python中以类似于字典的形式存储一些数据：{1:'a', 2:'b'}。每个值都将是唯一的，不仅是在其他值之间，而且在键之间。

有没有一个简单的数据结构，我可以使用它来获取相应的对象，不管我是使用“key”还是“value”？例如：

>>> a = {1:'a', 2:'b'}
>>> a[1]
'a'
>>> a['b']
2
>>> a[3]
KeyError

“keys”是标准的python int，值是短字符串（<；256char）。

我当前的解决方案是创建一个反向字典，如果在原始字典中找不到结果，则搜索它：

pointsreversed = dict((v, k) for k, v in points.iteritems())
def lookup(key):
    return points.get(key) or pointsreversed.key()

它占用的空间是原来的两倍，这不太好（我的字典可以高达几百兆），而且平均速度要慢50%。

编辑：正如在一些答案中提到的，两个口述稿不会使内存使用翻倍，因为它只是字典，而不是其中的条目，即重复。

有没有一个解决方案可以改进这个问题？

Answer 1

在计算机编程的艺术中，Vokume 3 Knuth有一个关于辅助键查找的部分。就您的问题而言，可以将该值视为次要密钥。

第一个建议是做你已经做过的事情：按值为键建立一个有效的索引。

第二个建议是设置一个大型btree，它是聚集数据的复合索引，其中分支节点包含值，叶子包含键数据和指向较大记录（如果有）的指针

如果数据是几何的（就像你看起来的那样），就有所谓的邮局树。它可以回答一些问题，比如，到x点最近的对象是什么。这里有几个例子：http://simsearch.yury.name/russir/01nncourse-hand.pdf这种查询的另一个简单选项是四叉树和k-d树。http://en.wikipedia.org/wiki/Quadtree

另一个最后的选择是组合散列，将键和值组合成一种特殊的散列，这样即使没有这两个值，也可以对散列进行有效的查找。我在网上找不到一个好的组合散列解释，但它在TAoCP第3卷第573页第二版。

当然，对于其中的一些，您可能需要编写自己的代码。但如果内存或性能真的很关键，您可能需要花点时间。

Answer 2

如果键和值不重叠，一个明显的方法是将它们简单地存储在同一个dict中

class BidirectionalDict(dict):
    def __setitem__(self, key, val):
        dict.__setitem__(self, key, val)
        dict.__setitem__(self, val, key)

    def __delitem__(self, key):
        dict.__delitem__(self, self[key])
        dict.__delitem__(self, key)

d = BidirectionalDict()
d['foo'] = 4
print d[4]   # Prints 'foo'

（您可能还希望实现像__init__、update和iter*方法这样的方法，使其像真正的dict一样工作，这取决于您需要多少功能）。

这应该只涉及一个查找，虽然可能不会在内存中节省很多（毕竟dict条目的数量还是原来的两倍）。但是请注意，无论是这个还是原来的都不会占用两倍的空间：dict只占用引用（实际上是指针）的空间，外加一个过度分配的开销。由于指向相同的对象，数据本身占用的空间不会重复两次。

Answer 3

相关职位：

Python mapping inverse

Python 1:1 mappings

当然，如果所有的值和键都是唯一的，难道不能只使用一个字典，并在开始时同时插入key:value和value:key吗？