K-way merge - Python way | Dark Hacker News

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

25 points by mmihaljevic 13 years ago | 5 comments

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.

thezilch 13 years ago | |

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]

mmihaljevic 13 years ago | |

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

tantalor 13 years ago | | |

> if you don't have sorted arrays

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

andrewcooke 13 years ago |

    >>> 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]

[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]