Merging dictionaries

[Preston Landers]

 Hello all,

I've got a program that works with large data structures in the form of
nested dictionaries.

The task at hand is to 'merge' two dictionaries with a special
merge_function() called for items that exist in both dictionaries.

This is defined simply as putting 'missing' items from one into the
other.  If an item exists in both, then the merge_function() function is
called, and the result of that is used as the value.  In my case, the
merge_function() is simple addition lambda.

I've got a recursive implementation posted below that works fine.  Its
output is correct.  However, it is unbearably slow.  I have up to seven
levels of nesting, and lots and lots of items.

The reason I'm posting is to find out if there is an iterative
solution.  "Mastering Algorithms With Perl" said nothing about this
problem, unfortunately. ;-)  Any ideas?  If I can't come up with
anything I'm afraid I'm going to have to look for and alternate approach
to the overall problem and abandon these nested dictionaries.

BTW I am aware of the limitations of the function I present below
(mainly, the two parameters must be similar in structure, number of
nested levels, etc) but it does the job I need.

Sorry if the formatting is messed up, too.

thanks,

---Preston

import types

def merge_dicts(left_dict, right_dict, merge_function):
    """merge two dictionaries, returning the combination.  recursively
operates on dicts within dicts.
    You must supply a function that accepts two parameters and returns a
conceptually 'merged' value.
    All type checking must be done by the merge_function you supply."""

    return_dict = right_dict.copy()

    # check that we actually have a function
    if type(merge_function) != types.FunctionType:
        raise TypeError, "The merge_function supplied was not a valid
function."

    # cache the key lists
    right_dict_keys = right_dict.keys()

    for left_key in left_dict.keys():
        if left_key in right_dict_keys:

            # cache the values
            left_value = left_dict[left_key]
            right_value = right_dict[left_key]

            # recurse on dictionaries
            if type(left_value) == type({}):
                return_dict[left_key] = merge_dicts(left_value,
right_value, merge_function)
                continue

            # apply the merge function
            return_dict[left_key] = merge_function(left_value,
right_value)

        else:
            return_dict[left_key] = left_dict[left_key]

    return return_dict

d1 = {"foo" : {"x": 1, "y": {"apple": 912.2, "banana": 11.8}}, "bar" :
{"x": 1, "y": 2}}
d2 = {"foo" : {"x": 1, "y": {"apple": 87.8, "banana": 0.2, "pear": 12}},
"biff" : {"x": 1, "y": 2}}

print merge_dicts(d1,d2, lambda x,y:x+y)

# should print:
# {'foo': {'x': 2, 'y': {'banana': 12.0, 'pear': 12, 'apple': 1000.0}},
'bar': {'x': 1, 'y': 2}, 'biff': {'x': 1, 'y': 2}}


--
|| Preston Landers <prestonlanders at my-deja.com> ||


Sent via Deja.com http://www.deja.com/
Before you buy.