Dual look-up on keys?

[Steven D'Aprano]

On Thu, 06 Mar 2008 08:37:07 +0000, Bryan Olson wrote:

> Grant Edwards wrote:
>> It may be  obvious that he has a question.  It's not the least bit
>> obvious what that question is.
> 
> How can we efficiently implement an abstract data type, call it
> 'DoubleDict', where the state of a DoubleDict is a binary relation, that
> is, a set of pairs (x, y); and the operations on a DoubleDict are those
> on a Python set, plus:
> 
>      find_by_first(self, x):  return [y where (x, y) in DoubleDict]
> 
>      find_by_second(self, y):  return [x where (x, y) in DoubleDict]
> 
> 
> Python can implement this ADT directly as specified, but the find_by_
> operations would run in time len(self).  We want an implementation where
> the find_by's run in O(1 + k) where k is the length of the returned
> sequence.

If I've understood you correctly, what you want is a reverse lookup dict. 
Here's a Quick & Dirty partial implementation to get you started. It's 
VERY simple-minded, and barely tested at all. But both lookup and reverse-
lookup should be almost as efficient as Python dicts, and it only uses 
roughly twice as many pointers as a regular dict.


class RLdict(object):
    def __init__(self, **items):
        self.D = {}
        self.R = {}
        for key, value in items.iteritems():
            self[key] = value
    def __getitem__(self, key):
        return self.D[key]
    def getkey(self, value):
        return self.R[value]
    def __setitem__(self, key, value):
        self.D[key] = value
        self.R[value] = key
    def __repr__(self):
        return "RLdict(%s)" % self.D


And in action:

>>> d = RLdict(a=1, b=2, c=3, d=4)
>>> d
RLdict({'a': 1, 'c': 3, 'b': 2, 'd': 4})
>>> d['b']
2
>>> d.getkey(2)
'b'


Naturally both the keys and values must be hashable. The version above 
makes keys/values a one-to-one mapping; if you want many-to-many, you'll 
need something more clever.

It's also possible that inheriting from dict instead of object would give 
you a whole lot of extra functionality for free, but I haven't explored 
that avenue.


-- 
Steven