generic xmerge ?

[Alex Martelli]

bonono at gmail.com <bonono at gmail.com> wrote:

> oops, sorry. I meant
> 
> l1=[(date,v1,v2,v3), ...]
> l2=[ another set of tuples ]
> 
> Thanks. so I have to concat the multiple lists first(all of them are
> sorted already) ?

You can do it either way -- simplest, and pretty fast, is to concatenate
them all and sort the result (the sort method is very good at taking
advantage of any sorting that may already be present in some parts of
the list it's sorting), but you can also try a merging approach.  E.g.:


import heapq

def merge_by_heap(*lists):
  sources = [[s.next(), i, s.next]
                    for i, s in enumerate(map(iter,lists))]
  heapq.heapify(sources)
  while sources:
    best_source = sources[0]
    yield best_source[0]
    try: best_source[0] = best_source[-1]()
    except StopIteration: heapq.heappop(sources)
    else: heapq.heapreplace(sources, best_source)

Now, L=list(merge_by_heap(l1, l2, l3)) should work, just as well as,
say, L = sorted(l1+l2+l3).  I suspect the second approach may be faster,
as well as simpler, but it's best to _measure_ (use the timeit.py module
from the standard library) if this code is highly speed-critical for
your overall application.


Alex