python - Is there a better way to store a twoway dictionary than storing its inverse separate?

Question

Given a one-to-one dictionary (=bijection) generated à la

for key, value in someGenerator:
     myDict[key] = value

an inverse lookup dictionary can be trivially created by adding

    invDict[value] = key

to the for loop. But is this a Pythonic way? Should I instead write a class Bijection(dict) which manages this inverted dictionary in addition and provides a second lookup function? Or does such a structure (or a similar one) already exist?

Answer 1

我过去所做的是创建一个reversedict函数，该函数将接受一个 dict 并返回相反的映射，如果我知道它是一对一的（两次看到相同的值时抛出异常），要么值到键，要么如果不是，则将值添加到键列表中。这样，每次我想要反向查找时都不必同时构建两个字典，我可以像平常一样创建我的字典并在reversedict最后调用泛型函数。

但是，似乎Jon 在评论中提到的bidict解决方案可能是更好的解决方案。（我的reversedict功能似乎是他的 bidict~操作员）。

Answer 2

如果您想要 O(log(n)) 时间来访问值，您将需要映射的表示和逆映射的表示。

否则你能做的最好的就是在一个方向上 O(log(n)) 和在另一个方向上 O(n)。

编辑：不是 O(log(n))，感谢 Claudiu，但您仍然需要两个数据结构来实现快速访问时间。这将或多或少与字典和逆字典相同的空间。