News for hackers. Stuff that matters.
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].

  [0]
  > list(heapq.merge([3, 2, 1], [3], [2, 3], [4, 5], [0, 1, 2]))
  [0, 1, 2, 2, 3, 2, 1, 3, 3, 4, 5]
  > sorted(itertools.chain([3, 2, 1], [3], [2, 3], [4, 5], [0, 1, 2]))
  [0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5]

  [1]
  > sorted(heapq.merge([3, 2, 1], [3], [2, 3], [4, 5], [0, 1, 2]))
  [0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5]

  [2]
  > list(itertools.chain([3, 2, 1], [3], [2, 3], [4, 5], [0, 1, 2]))
  [3, 2, 1, 3, 2, 3, 4, 5, 0, 1, 2]
  > list(heapq.merge([3, 2, 1], [3], [2, 3], [4, 5], [0, 1, 2]))
  [0, 1, 2, 2, 3, 2, 1, 3, 3, 4, 5]
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 appreciate your comment

Re:K-way merge - Python way by tantalor on Thursday December 27, 2012 @03:25PM (#4974888)
> if you don't have sorted arrays

In this case certainly you should sort the multiple smaller arrays (in parallel), not the merged one.