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
--
http://mail.python.org/mailman/listinfo/python-list
