K-way merge - Python way • Hacker News Board

K-way merge - Python way

#1

Post by mmihaljevic » Thu, Dec 27, 2012, 5:55 PM UTC

K-way merge - Python way
melitamihaljevic.blogspot.com

Re: K-way merge - Python way

#2

Post by cypherpunks01 » Thu, Dec 27, 2012, 7:23 PM UTC

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

#3

Post by mmihaljevic » Thu, Dec 27, 2012, 7:53 PM UTC

cypherpunks01 wrote: post #2

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.

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

#4

Post by thezilch » Thu, Dec 27, 2012, 8:18 PM UTC

cypherpunks01 wrote: post #2

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.

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

#5

Post by tantalor » Thu, Dec 27, 2012, 8:25 PM UTC

mmihaljevic wrote: post #3

cypherpunks01 wrote: post #2

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.

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

> if you don't have sorted arrays

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

Re: K-way merge - Python way

#6

Post by andrewcooke » Thu, Dec 27, 2012, 9:17 PM UTC

    >>> from heapq import merge
    >>> def kmerge(*lists):
    ...   return merge(*map(sorted, lists))
    ... 
    >>> list(kmerge([1,2,3],[6,5,4],[2,2]))
    [1, 2, 2, 2, 3, 4, 5, 6]