Merging dictionaries

[Bjorn Pettersen]

I think your problem is here:

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

which turns out to be O(n**2).  If you change the if statement to:

    if right_dict.has_key(left_key):

you should get back to O(n)'ish behavior.

-- bjorn

Preston Landers wrote:

>  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.
> --
> http://www.python.org/mailman/listinfo/python-list