4

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,

Amir
  • 5,996
  • 13
  • 48
  • 61
  • are the values guaranteed to be unique across the whole dict? – tzelleke Jan 04 '13 at 23:10
  • 1
    I don't know what else are you doing with the dict, so one way could be to use use values as keys and vice-verse? – ajmartin Jan 04 '13 at 23:12
  • yeah that is part of my question... if there is no efficient way to do that, I need another dict whose keys are the values – Amir Jan 04 '13 at 23:14
  • 1
    @Amir Reza: you can't get better than `O(n)` using the current technique, where `n` is the size of the dict. So, I guess the best way to get `O(1)` is to do the opposite. – ajmartin Jan 04 '13 at 23:21
  • I'm assuming this is guaranteed to be exactly 2 levels deep—you're not going to sometimes have `x4: 7` or `x5: {y4: {z1: 3, z2: 5}}`, right? – abarnert Jan 04 '13 at 23:26
  • Yes for this case... but it will be interesting to have a solution for arbitrary depth! – Amir Jan 04 '13 at 23:28
  • @AmirReza I have updated my answer to include arbitrary depth and 'ragged' dicts – tzelleke Jan 05 '13 at 00:05
  • 1
    related: [Efficient bidirectional hash table in Python?](http://stackoverflow.com/questions/3318625/efficient-bidirectional-hash-table-in-python) – Phil Frost Jan 05 '13 at 00:23

2 Answers2

5

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).

abarnert
  • 354,177
  • 51
  • 601
  • 671
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']}
tzelleke
  • 15,023
  • 5
  • 33
  • 49