Merging dictionaries
Bjorn Pettersen
bjorn at roguewave.com
Wed Dec 15 17:33:49 EST 1999
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
More information about the Python-list
mailing list