Joachim Durchholz <[EMAIL PROTECTED]> wrote: > Jim Gibson schrieb: > > > > The problem addressed by what is know in Perl as the 'Schwartzian > > Transform' is that the compare operation can be an expensive one, > > regardless of the whether the comparison uses multiple keys. Since in > > comparison sorts, the compare operation will be executed N(logN) times, > > it is more efficient to pre-compute a set of keys, one for each object > > to be sorted. That need be done only N times. > > Wikipedia says it's going from 2NlogN to N. If a sort is massively > dominated by the comparison, that could give a speedup of up to 100% > (approximately - dropping the logN factor is almost irrelevant, what > counts is losing that factor of 2).
It seems to me that ln 1,000,000 is 13.8, and that 13.8 is quite a bit greater than 2. Cheers, Xho -- -------------------- http://NewsReader.Com/ -------------------- Usenet Newsgroup Service $9.95/Month 30GB -- http://mail.python.org/mailman/listinfo/python-list