Merging sorted lists/iterators/generators into one stream of values...

George Sakkis gsakkis at rutgers.edu
Fri Oct 7 16:16:16 CEST 2005


"Lasse Vågsæther Karlsen" <lassevk at gmail.com> wrote:

> Thanks, that looks like Mike's solution except that it uses the
> built-in heapq module.

This make a big difference for the algorithmic complexity; replacing an item in a heap is much more
efficient than sorting the whole list.

> While this one contains less code than Mike's solution it seems to lack
> the ability to control the comparison operation, which means it won't
> work in my case. I need to both be able to sort on an arbitrary field
> name (could be done using a list where I place the field first), and
> also to be able to sort in a different order than smallest-first.
>
> Perhaps by adjusting the data that is returned through each source
> would do that. I'll look into it.

Yes, it's a little inconvenient that the builtin heap doesn't take a comparison operation but you
can easily roll your own heap by transforming each item to a (key,item) tuple. Now that I'm thinking
about it, it might be a good addition to the cookbook.

George





More information about the Python-list mailing list