python中1：1映射的数据结构？ [英] A data-structure for 1:1 mappings in python?

问题描述

我有一个问题，需要可逆的1：1键映射到值。

这意味着有时我想找到给定一个键的值，但在其他时候，我想要找到给定值的键。钥匙和值均保证唯一。

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

明显的解决方案是在每次想要反向查找时简单地反转字典：反相字典很简单，这里有一个食谱，但是对于一个大字典来说可能非常慢。

另一个替代方法是创建一个新类，它将两个字典相结合，一个用于每种查找。这很可能是快速的，但会占用单个字幕的两倍的内存。

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

• 我的应用程序需要这应该非常快，并尽可能少地使用内存。


• 结构必须是可变的，并且非常希望突破该对象不应使其更慢（例如强制一个完整的重新索引）


• 我们可以保证键或值（或两者）都将是一个整数


• 很可能将需要结构来存储数以千计的项目。


• 键& Valus被保证是独一无二的，即len（set（x））== len（x）for for [Dkeys（），D.valuies（）]

解决方案

  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] 
  

I have a problem which requires a reversable 1:1 mapping of keys to values.

That means sometimes I want to find the value given a key, but at other times I want to find the key given the value. Both keys and values are guaranteed unique.

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

The obvious solution is to simply invert the dictionary every time I want a reverse-lookup: Inverting a dictionary is very easy, there's a recipe here but for a large dictionary it can be very slow.

The other alternative is to make a new class which unites two dictionaries, one for each kind of lookup. That would most likely be fast but would use up twice as much memory as a single dict.

So is there a better structure I can use?

• My application requires that this should be very fast and use as little as possible memory.
• The structure must be mutable, and it's strongly desirable that mutating the object should not cause it to be slower (e.g. to force a complete re-index)
• We can guarantee that either the key or the value (or both) will be an integer
• It's likely that the structure will be needed to store thousands or possibly millions of items.
• Keys & Valus are guaranteed to be unique, i.e. len(set(x)) == len(x) for for x in [D.keys(), D.valuies()]

解决方案

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]

这篇关于python中1：1映射的数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！