A Sort Optimization Technique: decorate-sort-dedecorate
Dr.Ruud
rvtol+news at isolution.nl
Mon Aug 28 15:38:47 EDT 2006
Jim Gibson schreef:
> 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. The sort
> can then use these pre-computed keys to sort the objects.
Basically it first builds, than sorts an index.
The pre-computed (multi-)keys can often be optimized, see Uri's
Sort::Maker http://search.cpan.org/search?query=Sort::Maker
for facilities.
--
Affijn, Ruud
"Gewoon is een tijger."
More information about the Python-list
mailing list