Dual look-up on keys?
castironpi at gmail.com
castironpi at gmail.com
Thu Mar 6 05:29:55 EST 2008
On Mar 6, 2:37 am, Bryan Olson <fakeaddr... at nowhere.org> 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.
>
> --
> --Bryan
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]
More information about the Python-list
mailing list