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%.

编辑:正如在几个答案中提到的,两个dicts不会使内存使用量增加一倍,因为它只是字典,而不是内部的项目,即重复.

有没有改进的解决方案？

Answer 1

如果你的键和值不重叠,一个明显的方法是简单地将它们存储在同一个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 2

相关文章:

Python映射逆

Python 1:1映射

当然,如果所有的值和键都是唯一的,那么你不能只使用一个字典,并且最初插入key:value和value:key？