efficient list merging

Eric Brunel eric.brunel at pragmadev.com
Wed Sep 4 17:56:38 CEST 2002


Mark McEahern wrote:
[snip]
> Anyway, here's yet another approach:
> 
> #! /usr/bin/env python
> 
> lol1 = [['a'], ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i', 'j']]
> lol2 = [['d', 'e', 'f'], ['k', 'l', 'm'], ['d'], ['f', 'g'], ['a']]
> 
> def mergelists(*lists):
>     d = {}
>     for each_list in lists:
>         for item in each_list:
>             key = str(item)
>             if key not in d:
>                 d[key] = item
>     ret = d.values()
>     ret.sort()
>     return ret
> 
> mergelol = mergelists(lol1, lol2)
> 
> expected = [['a'], ['a', 'b', 'c'], ['d'], ['d', 'e', 'f'], ['f', 'g'],
>             ['g', 'h', 'i', 'j'], ['k', 'l', 'm']]
> 
> assert mergelol == expected
> 
> // m

To avoid explicit for loops, you may write:

l = lol1 + lol2
mergelol = dict(zip(map(str, l), l)).values()
mergelol.sort()         # if needed...


Maybe doing:

mergelol = dict(zip(map(tuple, l), l)).values()

can be a little faster: converting a list to a tuple *seems* easier than 
converting it to a string. But I may be wrong...

Anyway, any method involving a dictionary will require to convert your 
lists to something else: list are mutable, and cannot be used as dictionary 
keys...
-- 
- Eric Brunel <eric.brunel at pragmadev.com> -
PragmaDev : Real Time Software Development Tools - http://www.pragmadev.com



More information about the Python-list mailing list