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