A Sort Optimization Technique: decorate-sort-dedecorate

[Jim Gibson]

In article <pan.2006.08.28.08.53.08.647908 at gmx.net>, Marc 'BlackJack'
Rintsch <bj_666 at gmx.net> wrote:

> In <1156723602.192984.49610 at m79g2000cwm.googlegroups.com>, Tom Cole wrote:
> 
> > In Java, classes can implement the Comparable interface. This interface
> > contains only one method, a compareTo(Object o) method, and it is
> > defined to return a value < 0 if the Object is considered less than the
> > one being passed as an argument, it returns a value > 0 if considered
> > greater than, and 0 if they are considered equal.
> > 
> > The object implementing this interface can use any of the variables
> > available to it (AKA address, zip code, longitude, latitude, first
> > name, whatever) to return this -1, 0 or 1. This is slightly different
> > than what you mention as we don't have to "decorate" the object. These
> > are all variables that already exist in the Object, and if fact make it
> > what it is. So, of course, there is no need to un-decorate at the end.
> 
> Python has such a mechanism too, the special `__cmp__()` method
> has basically the same signature.  The problem the decorate, sort,
> un-decorate pattern solves is that this object specific compare operations
> only use *one* criteria.

I can't believe I am getting drawn into a thread started by xahlee, but
here goes anyway:

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. See, for example:

http://en.wikipedia.org/wiki/Schwartzian_transform

-- 
Jim Gibson

 Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
    ** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------        
                http://www.usenet.com