Re:K-way merge - Python way
by cypherpunks01 on Thursday December 27, 2012 @02:23PM
(#4974669)
Re-sorting with sorted() in #2 defeats the purpose of the k-way merge, you may as well just materialize all the lists and sort them.
I didn't know about heapq.merge before, that seems like an efficient way to go. Usually when I do k-way merges it's over a data stream, so I almost always want an iterator.
Re:K-way merge - Python way
by thezilch on Thursday December 27, 2012 @03:18PM
(#4974853)
heapq.merge assumes the passed iterators are already sorted and will sort the iterators as is, so you can expect to get different results from some inputs to the examples in #1 and #2 [0]. Of course, if you simply call sorted on the the heapq results (#1), you will get the same result as #2 [1]. As well, without a final sort of either merge-example, you will get different results [2].
Re:K-way merge - Python way
by mmihaljevic on Thursday December 27, 2012 @02:53PM
(#4974729)
you are right about sorted() but I was thinking it could be useful if you don't have sorted arrays but need similar functionality and arrays are not too big so you don't need an iterator but I was really amazed with heapq.merge()
I didn't know about heapq.merge before, that seems like an efficient way to go. Usually when I do k-way merges it's over a data stream, so I almost always want an iterator.
I appreciate your comment
In this case certainly you should sort the multiple smaller arrays (in parallel), not the merged one.