"Alex Martelli" <[EMAIL PROTECTED]> wrote: > George Sakkis <[EMAIL PROTECTED]> wrote: > ... > > > manipulation of a heap to place an item in the right spot, but with 4-5 > > > or a few more sources might not make an impact at all. > > > > Unless you're talking about hundreds or thousands sources, it probably > > won't. I would still go for the heap solution since IMO the resulting > > code it's more readable and easier to understand. > > I'm not so sure about either sentence...: > > Helen:~/pynut/samp alex$ python merger.py --numstreams=10 --minlen=100 > --how=S > Best time for 10 loops: 0.247116088867 > > Helen:~/pynut/samp alex$ python merger.py --numstreams=10 --minlen=100 > --how=H > Best time for 10 loops: 0.10344004631 > > i.e., a heap solution may be over 4 times faster than a sort-based one > (in the following implementations).
Interesting; I thought timsort on small almost ordered lists would be practically as fast as the heap. Still, how is 0.10344 over 4 times faster than 0.247116 ? > Readability seems quite comparable > (skipping the rest of the infrastructure, which generates random sorted > streams and ensures a stream is exhausted and verifies it etc etc): > > def merge_by_sort(streams): > sources = [[s.next(), i, s.next] for i, s in enumerate(streams)] > while sources: > sources.sort(reverse=True) > best_source = sources[-1] > yield best_source[0] > try: best_source[0] = best_source[-1]() > except StopIteration: sources.pop() > > def merge_by_heap(streams): > sources = [[s.next(), i, s.next] for i, s in enumerate(streams)] > 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) Indeed, these are almost equivalent as far as readability goes; the previous examples in the thread were less clear. By the way, why do you need 'i' and enumerate above ? > Hmmm, I wonder if something like merge_by_heap would be a good candidate > for itertool. Raymond...? > > > Alex Yes, it would be nice to make it into 2.5. George -- http://mail.python.org/mailman/listinfo/python-list
