Efficient mapping of both paths in Python with flag values

Question

What is the best data structure for bidirectionally displaying an object with flag values ​​for each pair in Python? For example, imagine that I have two pools of men and women that I want to meet. I want the data structure to keep matches, so I can access the corresponding man of every woman, the corresponding woman of every man and, say, a number representing the value of this pair.

The key feature is that I want to access all this data with constant time (approximately at the moment of access to the keys in the dictionary), without wasting resources on building.

If there wasn’t a “flag value” bidict , the bidict from the library proposed in this post would be absolutely perfect. In fact, every time I add a pair to the data structure of all star-pairs, it is automatically updated to avoid polygamy:

 couples = bidict({ 'leonard' : 'penny', 'howard' : 'bernadette', 'sheldon' : 'amy' }) couples.forceput('stephen', 'amy') print couples >> bidict({'stephen': 'amy', 'leonard': 'penny', 'howard': 'bernadette'}) 

Now I ask for advice on the most efficient and pythonic way of implementing the quality function, which, for example:

 quality('stephen', 'amy') >> 0.4 couples.forceput('sheldon', 'amy', quality = 1.0) quality('sheldon', 'amy') >> 1.0 quality('stephen', 'amy') >> Raise KeyError 

Answer 1

Solution 1: Fast and Dirty

Here's a trivial implementation built on top of bidict , made by adrin and Austin :

 class couple ( bidict ) : self._flags = {} def add ( self, key, val, flag ) : try : del self._flags[ self._inv[ val ] ] except KeyError : pass self._put(key, val, overwrite_key=True, overwrite_val=True) self._flags[ key ] = flag def flag ( self, key, val ) : if ( self._fwd.get( key ) == val ) : return self._flags[ key ] else : raise KeyError( key, val ) 

Thus, you can get the following behavior:

 bbt = couple() bbt.add( 'stephen', 'amy', 0.4 ) bbt.flag( 'stephen', 'amy' ) >> 0.4 bbt.add( 'sheldon', 'amy', 1.0 ) bbt.flag( 'sheldon', 'amy' ) >> 1.0 bbt.flag( 'stephen', 'amy' ) >> KeyError: ('stephen', 'amy') 

Solution 2: Concrete and Autonomous

Since I finally finished coding my own structure. This is standalone, and can be c / c , if necessary, someone passing here:

 class FlaggedDoubleMapper : """Flagged Double Mapper""" def __init__ ( self, keys = [], vals = [], flags = [] ) : """Initializes a flagged double mapper with lists of keys, values and flags. """ self._flg = {} # Flags dictionary self._fwd = {} # Forward dictionary self._bwd = {} # Backward dictionary for key, val, flag in zip( keys, vals, flags ) : self.add( key, val, flag ) def __repr__ ( self ) : """Representation bidict-style.""" return 'fdm({})'.format( self._fwd ) def contains ( self, key, val ) : """Returns True if and only if self contains the key-val binding.""" try : return ( self._fwd[ key ] == val ) except KeyError : return False def add ( self, key, val, flag ) : """Adds a flagged binding, overwriting all corresponding bindings.""" try : _val = self._fwd[ key ] del self._bwd[ _val ] except KeyError : pass try : _key = self._bwd[ val ] del self._flg[ _key ] del self._fwd[ _key ] except KeyError : pass self._flg[ key ] = flag self._fwd[ key ] = val self._bwd[ val ] = key def remove ( self, key, *args ) : """Removes a binding. - remove( key ) will send a KeyError( key ) if no binding with key as a forward key is found. - remove( key, val ) will send a KeyError( key, val ) if no forward key-val binding is found. """ try : _val = args[0] if ( _val != self._fwd[ key ] ) : # Can raise a KeyError( key ) raise KeyError( key, _val ) except IndexError : _val = self._fwd[ key ] # Can raise a KeyError( key ) del self._flg[ key ] del self._fwd[ key ] del self._bwd[ _val ] def flag ( self, key, *args ) : """Returns the flag of a binding. - flag( key ) will send a KeyError( key ) if no binding with key as a forward key is found. - flag( key, val ) will send a KeyError( key, val ) if no forward key-val binding is found. """ try : _val = args[0] if ( _val != self._fwd[ key ] ) : # Can raise a KeyError( key ) raise KeyError( key, _val ) except IndexError : pass return self._flg[ key ] 

Answer 2

Note that tuples are hashed. You can create a dict that matches a pair with any data, including quality:

 quality = dict() quality[ ('stephen', 'amy') ] = 0.4 

Answer 3

Since you use keys that are hashed, the immediate solution should be to add a dictionary that uses frozenset {man, woman} as it has quality as its value.

However, you reach a point where defining all your needs and installing them in the right object architecture begins to make a difference. You have graph architecture here, in the sense that data is tied to nodes (names of people and sex) and links (relationships and quality). I would probably borrow or implement a graph structure to represent this, choose the best option depending on speed and memory considerations, and the structure would make future expansion an easy task.

Given that you have only one link to node maximum, and you want to access O (1) to people and their partners, here you would optimize by completing your schedule as follows:

 class People (): def __init__(self, name, sex): self.name = name self.sex = sex self.relationship = None def force_link(self, partner, quality = None): #You can implement a sex check here for example self.relationship = Relationship (quality) partner.relationship = self.relationship class Relationship (): def __init__(self, quality): #May grow over time self.quality = quality class Graph (): def __init__(self): # Indexing by name self.nodes = { name : People(name, sex) for name, sex in zip(namelist,sexlist) } # Linking example self.nodes['brandon'].force_link(self.nodes['amy'],0.2) # Get quality example print (self.nodes['amy'].relationship.quality)