Inverse dictionary lookup in Python

Question

Is there any straightforward way of finding a key by knowing the value within a dictionary   All I can think of is this   key    key for key  value in dict obj items   if value     value   0

User · Answer

Since this is still very relevant  the first Google hit and I just spend some time figuring this out  I ll post my  working in Python 3  solution   testdict     one       1                two       2                three     3                four      4                 value    2    key for key in testdict items   if key 1     value  0  0   Out 1    two    It will give you the first value that matches

User · Answer

This version is 26  shorter than yours but functions identically  even for redundant ambiguous values  returns the first match  as yours does   However  it is probably twice as slow as yours  because it creates a list from the dict twice   key   dict obj keys   dict obj values   index value     Or if you prefer brevity over readability you can save one more character with  key   list dict obj  dict obj values   index value     And if you prefer efficiency   PaulMcGuire s approach is better  If there are lots of keys that share the same value it s more efficient not to instantiate that list of keys with a list comprehension and instead use use a generator   key    key for key  value in dict obj items   if value     value   next

User · Answer

There is none  Don t forget that the value may be found on any number of keys  including 0 or more than 1

User · Answer

oneline solution using zip  gt  gt  x     a  100   b  999   gt  gt  y   dict zip x values    x keys        gt  gt  y  100   a   999   b

User · Answer

I m using dictionaries as a sort of  database   so I need to find a key that I can reuse  For my case  if a key s value is None  then I can take it and reuse it without having to  allocate  another id  Just figured I d share it   db    0     1          5 None  11 None  19           keys to reallocate    None  allocate extend i for i in db iterkeys   if db i  is None  free id   keys to reallocate -1    I like this one because I don t have to try and catch any errors such as StopIteration or IndexError  If there s a key available  then free id will contain one  If there isn t  then it will simply be None  Probably not pythonic  but I really didn t want to use a try here

User · Answer

Maybe a dictionary-like class such as DoubleDict down below is what you want  You can use any one of the provided metaclasses in conjuction with DoubleDict or may avoid using any metaclass at all   import functools import threading                                                                                    class  DDChecker type        def   new   cls  name  bases  classdict           for key  value in classdict items                if key not in     new        slots       DoubleDict  dict view                    classdict key    cls  wrap value          return super     new   cls  name  bases  classdict        staticmethod     def  wrap function            functools wraps function          def check self   args    kwargs               value   function self   args    kwargs              if self  DoubleDict  forward                     dict map reversed  self  DoubleDict  reverse items                      raise RuntimeError  Forward  amp  Reverse are not equivalent                return value         return check                                                                                    class  DDAtomic  DDChecker        def   new   cls  name  bases  classdict           if not bases              classdict    slots           DDAtomic  mutex                classdict    new       cls  atomic new         return super     new   cls  name  bases  classdict        staticmethod     def  atomic new cls  iterable       pairs           instance   object   new   cls  iterable    pairs          instance   mutex   threading RLock           instance clear           return instance       staticmethod     def  wrap function            functools wraps function          def atomic self   args    kwargs               with self   mutex                  return function self   args    kwargs          return atomic                                                                                    class  DDAtomicChecker  DDAtomic         staticmethod     def  wrap function           return  DDAtomic  wrap  DDChecker  wrap function                                                                                      class DoubleDict metaclass  DDAtomicChecker          slots        forward      reverse       def   new   cls  iterable       pairs           instance   super     new   cls  iterable    pairs          instance clear           return instance      def   init   self  iterable       pairs           self update iterable    pairs                                                                                     def   repr   self           return repr self   forward       def   lt   self  other           return self   forward  lt  other      def   le   self  other           return self   forward  lt   other      def   eq   self  other           return self   forward    other      def   ne   self  other           return self   forward    other      def   gt   self  other           return self   forward  gt  other      def   ge   self  other           return self   forward  gt   other      def   len   self           return len self   forward       def   getitem   self  key           if key in self              return self   forward key          return self   missing key key       def   setitem   self  key  value           if self in values value               del self self get key value           self   set key value key  value          return value      def   delitem   self  key           self pop key       def   iter   self           return iter self   forward       def   contains   self  key           return key in self   forward                                                                                    def clear self           self   forward              self   reverse           def copy self           return self   class   self items         def del value self  value           self pop key value       def get self  key  default None           return self key  if key in self else default      def get key self  value           if self in values value               return self   reverse value          return self   missing value value       def get key default self  value  default None           return self get key value  if self in values value  else default      def in values self  value           return value in self   reverse      def items self           return self   dict view  items     key  self key   for key in self        def iter values self           return iter self   reverse       def keys self           return self   dict view  keys   self   forward       def pop self  key   default           if len default   gt  1              raise TypeError  too many arguments           if key in self              value   self key              self   del key value key  value              return value         if default              return default 0          raise KeyError key       def pop key self  value   default           if len default   gt  1              raise TypeError  too many arguments           if self in values value               key   self get key value              self   del key value key  value              return key         if default              return default 0          raise KeyError value       def popitem self           try              key   next iter self           except StopIteration              raise KeyError  popitem    dictionary is empty           return key  self pop key       def set key self  value  key           if key in self              self del value self key           self   set key value key  value          return key      def setdefault self  key  default None           if key not in self              self key    default         return self key       def setdefault key self  value  default None           if not self in values value               self set key value  default          return self get key value       def update self  iterable       pairs           for key  value in    key  iterable key   for key in iterable keys                               if hasattr iterable   keys   else iterable               self key    value         for key  value in pairs items                self key    value      def values self           return self   dict view  values   self   reverse                                                                                     def   missing key self  key           if hasattr self   class       missing                  return self   missing   key          if not hasattr self   default factory                or self default factory is None              raise KeyError key          return self   setitem   key  self default factory         def   missing value self  value           if hasattr self   class       missing value                  return self   missing value   value          if not hasattr self   default key factory                or self default key factory is None              raise KeyError value          return self set key value  self default key factory         def   set key value self  key  value           self   forward key    value         self   reverse value    key      def   del key value self  key  value           del self   forward key          del self   reverse value                                                                                     class   dict view frozenset              slots        name           def   new   cls  name  iterable                  instance   super     new   cls  iterable              instance   name   name             return instance          def   repr   self               return  dict         format self   name  list self

User · Answer

Make a reverse dictionary  reverse dictionary    v k for k v in dictionary items       If you have a lot of reverse lookups to do

User · Answer

There are cases where a dictionary is a one one mapping  Eg   d    1   one   2   two         Your approach is ok if you are only doing a single lookup  However if you need to do more than  one lookup it will be more efficient to create an inverse dictionary  ivd    v  k for k  v in d items      If there is a possibility of multiple keys with the same value  you will need to specify the desired behaviour in this case   If your Python is 2 6 or older  you can use  ivd   dict  v  k  for k  v in d items

User · Answer

There isn t one as far as I know of  one way however to do it is to create a dict for normal lookup by key and another dict for reverse lookup by value   There s an example of such an implementation here   http   code activestate com recipes 415903-two-dict-classes-which-can-lookup-keys-by-value-an   This does mean that looking up the keys for a value could result in multiple results which can be returned as a simple list

User · Answer

Through values in dictionary can be object of any kind they can t be hashed or indexed other way  So finding key by the value is unnatural for this collection type  Any query like that can be executed in O n  time only  So if this is frequent task you should take a look for some indexing of key like Jon sujjested or maybe even some spatial index  DB or http   pypi python org pypi Rtree

User · Answer

No  you can not do this efficiently without looking in all the keys and checking all their values  So you will need O n  time to do this  If you need to do a lot of such lookups you will need to do this efficiently by constructing a reversed dictionary  can be done also in O n   and then making a search inside of this reversed dictionary  each search will take on average O 1     Here is an example of how to construct a reversed dictionary  which will be able to do one to many mapping  from a normal dictionary   for i in h normal      for j in h normal i           if j not in h reversed              h reversed j    set  i           else              h reversed j  add i    For example if your   h normal       1  set  3       2  set  5  7       3  set         4  set  7       5  set  1  4       6  set  1  7       7  set  1       8  set  2  5  6       your h reversed will be      1  set  5  6  7      2  set  8       3  set  1       4  set  5       5  set  8  2       6  set  8       7  set  2  4  6

User · Answer

I know this might be considered  wasteful   but in this scenario I often store the key as an additional column in the value record   d     key1      key1   val  val       key2      key2   val  val         it s a tradeoff and feels wrong  but it s simple and works and of course depends on values being tuples rather than simple values

User · Answer

Your list comprehension goes through all the dict s items finding all the matches  then just returns the first key   This generator expression will only iterate as far as necessary to return the first value   key   next key for key  value in dd items   if value     value     where dd is the dict   Will raise StopIteration if no match is found  so you might want to catch that and return a more appropriate exception like ValueError or KeyError

[python] Inverse dictionary lookup in Python

Examples related to python

Examples related to dictionary