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). Regards, Jo -- http://mail.python.org/mailman/listinfo/python-list