Merging ordered lists

Raymond Hettinger python at rcn.com
Sun Jun 1 09:34:36 CEST 2008


On May 31, 10:00 pm, etal <eric.talev... at gmail.com> wrote:
> Here's an algorithm question: How should I efficiently merge a
> collection of mostly similar lists, with different lengths and
> arbitrary contents, while eliminating duplicates and preserving order
> as much as possible?

I would do it two steps.  There's a number of ways to merge depending
on whether everything is pulled into memory or not:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/491285
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/305269

After merging, the groupby itertool is good for removing duplicates:

   result = [k for k, g in groupby(imerge(*sources))]


Raymond



More information about the Python-list mailing list