George Sakkis <[EMAIL PROTECTED]> wrote: ... > > 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 ?
Oops, 2.5 times (for 10 streams) -- the ratio keeps getting bigger with the number of streams, the figure 4 I had in mind was probably from comparisons with 50 streams or so. timsort needs N comparisons even if the list is already ordered (just to check it is) while heaps can do with log(N) comparisons or even less in the best case -- that's the key issue here. > > sources = [[s.next(), i, s.next] for i, s in enumerate(streams)] ... > 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 ? Making sure that, if the first items are identical, the sorting (or comparison for heap) does not compare the _methods_ -- no big deal if it does, but that doesn't logically make sense. If we had key= arguments, that would ENSURE no such comparison, but heaps didn't support that in 2.4 and I wanted to keep the playing field level, so I used the above old trick to ensure stable sorting without comparisons beyond a given field (more details were explained in the 1st edition of the Cookbook, but I hope I give the general idea). Alex -- http://mail.python.org/mailman/listinfo/python-list