python中1:1映射的数据结构？

Question

我有一个问题,需要一个可逆的1:1键到值的映射.

这意味着有时我想找到一个给定键的值,但有时我想找到给定值的键.键和值都保证唯一.

x = D[y]
y == D.inverse[x]

显而易见的解决方案是每次我想要反向查找时简单地反转字典:反转字典非常容易,这里有一个配方但是对于大字典它可能非常慢.

另一种方法是创建一个新的类,它将两个字典统一起来,每个字典对应一种查找.这很可能很快,但会消耗两倍于单个字典的内存.

那么我可以使用更好的结构吗？

• 我的应用程序要求这应该非常快,并尽可能少地使用内存.
• 结构必须是可变的,并且强烈希望变异对象不应该导致它更慢(例如强制完整的重新索引)
• 我们可以保证键或值(或两者)都是整数
• 可能需要该结构来存储数千或数百万件物品.
• Keys&Valus保证是唯一的,即len(set(x))== len(x)代表[D.keys(),D.valuies()]中的x

Answer 1

另一种方法是创建一个新的类,它将两个字典统一起来,每个字典对应一种查找.这很可能很快,但会消耗两倍于单个字典的内存.

并不是的.你测量过了吗？由于两个字典都会使用与键和值相同的对象的引用,因此所花费的内存将只是字典结构.这不到两倍,并且无论您的数据大小如何都是固定的.

我的意思是不会复制实际数据.所以你要花掉额外的记忆.

例:

a = "some really really big text spending a lot of memory"

number_to_text = {1: a}
text_to_number = {a: 1}

只存在"真正大"字符串的单个副本,因此您最终只需花费更多内存.这通常是负担得起的.

我无法想象一个解决方案,如果你没有花费至少足够的内存来存储反向查找哈希表,那么你在按值查看键时可以获得键查找速度(这正是你在"联合两个"中所做的事情.dicts"解决方案".

Answer 2

class TwoWay:
    def __init__(self):
       self.d = {}
    def add(self, k, v):
       self.d[k] = v
       self.d[v] = k
    def remove(self, k):
       self.d.pop(self.d.pop(k))
    def get(self, k):
       return self.d[k]

Answer 3

另一种方法是创建一个新的类,它将两个字典统一起来,每个字典对应一种查找.这很可能会占用单个字典的两倍内存.

不是真的,因为他们只会持有两个相同数据的引用.在我看来,这不是一个糟糕的解决方案.

您是否考虑过内存数据库查找？我不确定它在速度上的比较,但关系数据库中的查找速度非常快.