Merging sorted lists/iterators/generators into one stream of values...
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.
More information about the Python-list