How do you iterate over two dictionaries and grab the values at the same path?

Question

I have two dictionaries, that are of similar structure...meaning they(should) have the same key structure, even within nested keys. Also, these dicts could have almost any type of nested structure...list, dict, etc... I want to be able to traverse these dictionaries, and grab the two values and return them from a function.

Simple Example:

dict_a = {'a':1, 'b':2, 'c':{'d':3}}
dict_b = {'a':2, 'b':4, 'c':{'d':6}}
#Note the structure is the same for these dicts
#I want to be able to do something like:
>>get_values( dict_a, dict_b)
[(1,2),(2,4),(3,6)]

I came up with a solution to it myself by traversing one dictionary, and appending each key(or index if it encounters a list) into a list...as a sort of key-path:

key_map = []#A list of all key-paths for a dictionary
generate_key_paths(dict_a, [], key_map)
def generate_key_paths(value, key_list,key_map ):

    new_list = [item for item in key_list]
    if isinstance( value, dict):
        #Handle list
        for key, val in value.iteritems():
            new_list.append( key)
            self._generate_key_paths( val, new_list, key_map )
            new_list = [item for item in key_list]

    elif isinstance( value, list ):
        #Handle list
        for idx,item in enumerate(value):
            new_list.append( idx )  
            self._generate_key_paths( item, new_list, key_map )
            new_list = [item for item in key_list]
    else:
        #Handle data--reached farthest point you can go
        #So just append (key-path, value) to key_map
        key_map.append((new_list, value ) )

And then once you have a list of key-path,value tuples...take the path, and try to reach it on the second dictionary to get its value...

val_list = []
for item in key_map:
    value = get_value( item[0] )
    if value is not None:
        val_list.append( (item[1], value ) )
def get_value( key_list ):
    value = dict_b
    for item in key_list:
        try:
            value = value[item]
        except:
            value = None
            break
    return value

This works quite well for all structures a dictionary could have, but it seems like a lot of work. Is there a more pythonic way of achieving this? Is there a faster, more efficient way?

EDIT: I'm looking for a value that isn't a list or a dict, so when these values are reached, it should iterate inside them, until it finds a value. It is guaranteed that if it's a list, it will be a list of dicts, so there should always be some sort of key:value relationship to follow.

For example a possible dict could look like this:

dict_a = {'a':1, 'b':2, 'c':[{'d':5},{'e':6}]}

dict_b = {'a':2, 'b':4, 'c':[{'d':10},{'e':12}]}

Answer: [(1,2), (2,4), (5,10), (6,12)]

Answer 1

You are looking for an equivalent of flatten(zipTree(...)) (functions which don't exist but whose names should get my point across).

from collections import Mapping

def treezipFlat(t1,t2):
    if isinstance(t1,Mapping) and isinstance(t2,Mapping):
        assert set(t1)==set(t2)
        for k,v1 in t1.items():
            v2 = t2[k]
            for tuple in treezipFlat(v1,v2):
                yield tuple
    else:
        yield (t1,t2)

Demo:

>>> dict_a = {'a':1, 'b':2, 'c':{'d':3}}
>>> dict_b = {'a':2, 'b':4, 'c':{'d':6}}
>>> list( treezipFlat(dict_a, dict_b) )
[(1, 2), (3, 6), (2, 4)]

You can furthermore yield the tuple of paths by augmenting the function like so:

from collections import Mapping

def treezipItems(t1,t2, path=[]):
    if isinstance(t1,Mapping) and isinstance(t2,Mapping):
        assert set(t1)==set(t2)
        for k,v1 in t1.items():
            v2 = t2[k]
            for tuple in treezipItems(v1,v2, path=path+[k]):
                yield tuple
    else:
        yield (path, (t1,t2))

>>> list( treezipItems(dict_a, dict_b) )
[(['a'], (1, 2)), (['c', 'd'], (3, 6)), (['b'], (2, 4))]

Imho I feel the natural thing here is a function called treezip:

def treezip(t1,t2):
    if isinstance(t1,Mapping) and isinstance(t2,Mapping):
        assert set(t1)==set(t2)
        R = {}
        for k,v1 in t1.items():
            v2 = t2[k]
            R[k] = treezip(v1,v2)
        return R
    else:
        return (t1,t2)

>>> from pprint import pprint as pp
>>> treezip(dict_a, dict_b)
{'a': (1, 2), 'c': {'d': (3, 6)}, 'b': (2, 4)}

Then a function called flattenValues (or flattenItems if you want to preserve keys).