[Tutor] Return key from value

[Danny Yoo]

On Thu, 13 May 2004, firephreek wrote:

> I thought there was a method for it, but I can't seem to find it.
>
> Does anyone know how I can return the matching key from a dictionary if
> I know the value?  I'm working with some very large data structures, and
> I don't want to have to duplicate them.


Hi Stryder,


A simple dictionary is good for defining a mapping from a key to a value
--- but it's not so good for going the other way.  It's possible to just
do a linear scan across the items() of a dictionary:

###
>>> d = {1:'one', 2:'two', 3:'three'}
>>> d.items()
[(1, 'one'), (2, 'two'), (3, 'three')]
###

You mentioned that the data structure is large: the linear scan might a
bad idea, then.  If so, then the most straightforward thing I can think of
at the moment is to duplicate: have one dictionary map from keys to
values, and another dictionary to go the other way.  This approach trades
off space for fast lookup.


But what are your keys and values, by the way?  Depending on what the data
is, we might be able to use something like the "range" data structures
surveyed by Bentley and Friedman.  If you have an ACM account, then you
might like to read:

    http://portal.acm.org/citation.cfm?id=356797&dl=ACM&coll=portal

which is a nice introduction to these structures.  If the keys and values
can be treated as numbers, then a KD-tree can work:

    http://www.nist.gov/dads/HTML/kdtree.html

The BioPython project has an optimized KD tree implementation, so you
might be able to get away without having to write much.  *grin*


One other alternative is to cheat and use a relational database like
Sqlite:

    http://www.sqlite.org/

*grin*