Dual look-up on keys?

Bryan Olson fakeaddress at nowhere.org
Thu Mar 6 12:16:11 CET 2008

castironpi at gmail.com wrote:
> Bryan Olson wrote:
>> 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]

> It gets hairier if you have an element that isn't a first or second
> necessarily.
>       find_by_other(self, x): return [y where (x, y) in DoubleDict or
> (y, x) in DoubleDict]

Do you need all three find_by's, or are the pairs actually
unordered, so you just need to find partners? Are the relations
many-to-many, and if so do you want duplicates removed?

As programming exercises, the variants are all reasonable and
possibly interesting. I was just trying to answer the call to
nail down the problem statement.


More information about the Python-list mailing list