python query keys in a dictionary based on values

Question

Lets have a following dict:

 table = {x1: {y1: 1, y2:2},
         x2: {y1: 3, y2:4},
         x3: {y3: 5, y2:6}
         } 

Considering the values are unique, is there any way to query the key path based on the value efficiently or it is better to reconstruct the dict using the value as the key?

Example:

   result = magic_function(table, 3)
   result --> [x2, y1]

Thanks,

Answer 1

The idiomatic way to "invert" a dictionary is like this:

i = {v: k for (k, v) in d.items()}

If you're in Python 2 rather than 3, and d might be big, use iteritems instead.

In your case, you've got a dict of dicts, and you want to sort of double-invert it into a dict of paths, if I understand correctly. But you don't know how to write that. So, let's start by writing it explicitly, the long way:

i = {}
for k, v in d.items():
    for k2, v2 in v.items():
        i[v2] = (k, k2)

You can convert this into a dictionary comprehension, but you want it to be something you actually understand, rather than some magic invocation you copy and paste without thinking, so I'll leave that part up to you (but I'll be glad to help if you have any questions).

Answer 2

Inverting is probably the better way to go:

In [17]: d = {table[k1][k2]: (k1,k2) for k1 in table for k2 in table[k1]}

Here's a solution handling arbitrary depth and "ragged" dicts:

def invert_arbitrary(d, ldict, p=[]):
    for k, v in ldict.items():
        if isinstance(v, dict):
            invert_arbitrary(d, v, p + [k])
        else:
            d[v] = p + [k]

Example:

table = {'x1': {'y1': 1, 'y2': 2}, 
         'x2': {'y1': 3,
                'y2': {'z1': 4, 'z2': 5}},
         'x3': 6}

In [40]: d = dict()
In [41]: invert_arbitrary(d, table)

In [42]: d
Out[42]: 
{1: ['x1', 'y1'],
 2: ['x1', 'y2'],
 3: ['x2', 'y1'],
 4: ['x2', 'y2', 'z1'],
 5: ['x2', 'y2', 'z2'],
 6: ['x3']}