3

I have a giant dict with a lot of nested dicts -- like a giant tree, and depth in unknown.

I need a function, something like find_value(), that takes dict, value (as string), and returns list of lists, each one of them is "path" (sequential chain of keys from first key to key (or key value) with found value). If nothing found, returns empty list.

I wrote this code:

def find_value(dict, sought_value, current_path, result):   
    for key,value in dict.items():
        current_path.pop()
        current_path.append(key)
        if sought_value in key:
            result.append(current_path)
        if type(value) == type(''):
            if sought_value in value:
                result.append(current_path+[value])
        else:
            current_path.append(key) 
            result = find_value(value, sought_value, current_path, result)
    current_path.pop()
    return result

I call this function to test:

result = find_value(self.dump, sought_value, ['START_KEY_FOR_DELETE'], [])
if not len(result):
    print "forgive me, mylord, i'm afraid we didn't find him.."
elif len(result) == 1:
    print "bless gods, for all that we have one match, mylord!"

For some inexplicable reasons, my implementation of this function fails some of my tests. I started to debug and find out, that even if current_path prints correct things (it always does, I checked!), the result is inexplicably corrupted. Maybe it is because of recursion magic?

Can anyone help me with this problem? Maybe there is a simple solution for my tasks?

Gabe
  • 84,912
  • 12
  • 139
  • 238
Bruno Gelb
  • 5,322
  • 8
  • 35
  • 50
  • 2
    Why do you prefer non-recursive? Do you expect the tree depth to be so deep that you're afraid of a stack overflow? – Gabe Apr 29 '13 at 20:41
  • @Gabe, I don't know. I'm just afraid of recursion in python. Max depth, i think, is 15-20, or even less. But it's unknown. Also I'm afraid that recursion magic is thing, that might intercept me from debug the real problem. – Bruno Gelb Apr 29 '13 at 20:44
  • 1
    Thing is that if your tree doesn't have some properties, you'll have to scan it all. IMHO your function is a bit overkill, because is recursive and it tries to emulate the recursivity with a stack. You should pick one :) See [here](http://stackoverflow.com/questions/9831666/how-can-you-emulate-recursion-with-a-stack) for emulation – Laur Ivan Apr 29 '13 at 20:45
  • @equinoxel, ok, thank you, but forgive me, what would you really suggest me for my task? I assume you read all of my post? Also I don't worry to scan all tree if it havn't value :) – Bruno Gelb Apr 29 '13 at 20:48
  • 1
    This should be recursive – piokuc Apr 29 '13 at 20:49
  • @piokuc, if you say that, it will be. :) But what about realization? Is it well or even is it correct? – Bruno Gelb Apr 29 '13 at 20:50
  • 1
    Do you want me to debug it for you or formally prove correctness? – piokuc Apr 29 '13 at 20:52
  • A recursive solution to a recursive problem is always neater than a non-recursive one. After all, with the stack you're just emulating recursion ;) – piokuc Apr 29 '13 at 20:53
  • @piokuc, debug for me would be my sweet dream, but I assume you have no time for that. Yes, I ask as junior for formally proving by experienced pythoner. – Bruno Gelb Apr 29 '13 at 20:54
  • 1
    I don't know why but I don't feel like doing neither of these two things now. I can only give you one advice - open your eyes! recursion is cool! ;) – piokuc Apr 29 '13 at 20:59

2 Answers2

2

When you write result.append(current_path), you're not copying current_path, which continues to mutate. Change it to result.append(current_path[:]).

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • 1
    I'll be damned. You find the bug!!!! Now it passes all the tests! You are just.. beautiful creation of God. – Bruno Gelb Apr 29 '13 at 21:06
2

I doubt you can do much to optimize a recursive search like that. Assuming there are many lookups on the same dictionary, and the dictionary doesn't change once loaded, then you can index it to get O(1) lookups...

def build_index(src, dest, path=[]):
    for k, v in src.iteritems():
        fk = path+[k]
        if isinstance(v, dict):
            build_index(v, dest, fk)
        else:
            try:
                dest[v].append(fk)
            except KeyError:
                dest[v] = [fk]

>>> data = {'foo': {'sub1': 'blah'}, 'bar': {'sub2': 'whatever'}, 'baz': 'blah'}
>>> index = {}
>>> build_index(data, index)
>>> index
{'blah': [['baz'], ['foo', 'sub1']], 'whatever': [['bar', 'sub2']]}
>>> index['blah']
[['baz'], ['foo', 'sub1']]
Aya
  • 39,884
  • 6
  • 55
  • 55