>>>>> "LP" == Luke Palmer <[EMAIL PROTECTED]> writes:
LP> Uri Guttman writes:
>> >>>>> "GNP" == Gregor N Purdy <[EMAIL PROTECTED]> writes:
>>
GNP> (But, the GRT doesn't apply to sorting general objects, and the
GNP> example has @unsorted containing objects on which we run
GNP> .foo('bar').compute.)
>>
>> there are no restrictions on what the GRT (or ST) can sort. the key is
>> key extraction and that can be from an object or anything. if the
>> compute method has to be called each time during the comparison, you are
>> in deep sort voodoo. so you can just call it during the extract phase
>> (the first executed map in the GRT or ST). if you have the object in $_,
>> you can call a method or do whatever you need to get the key.
LP> Might you explain what the GRT is and what it is intended to do?
LP> I've been lost throughout most of your proposal.
and now you know how i feel about some threads you delve into! my brane
hertz! :)
sorry about the confusion. read the paper at:
http://www.sysarch.com/perl/sort_paper.html
the idea is simple and very old. you extract keys from the records and
merge them (with some munging) into a byte string. then you can run a
straight sort with comparisons on those merged key strings and use fast
string compares. the win is not doing the key extraction on each set of
comparisons which is O(N log N). instead you do the extractions once per
key which is O(N). it is a real world optimization as pure O() theory
wouldn't care as the dominating O(N log N) is still the same in both
cases. :)
all we (larry rosler and myself) did was translate the idea into perl
and document how to do it. one of these days i will actually create a
perl5 module (started one years ago but it got shelved) to implement
this and make it easy to use. i recently came up with a design
breakthrough (just not being as stupid as i was a few years ago) to make
it easier to do so i may get back onto it.
but much of my p6 proposal was to have the sort function reflect the
essence of both the GRT and ST which is to factor out key extraction in
a map before the sort. my syntax examples were meant to show what is
needed to pass into a full sort system and what isn't needed. perl5's
sort exposed everything and required redundant code in the comparison
block, confusing expressions, etc. the ST and GRT removed some of the
redundant code but replaced that with the map/sort/map which has
different redundant code (redundant between different instances of
them. why see the map parts?).
so my proposed syntax isolates the key extraction code and makes it work
on $_. it also removes the comparison operator stuff and allows the
coder to just say what they want in regard to sort order, key type and
collate sequence. the guts will do all the common code (the maps) and
generate/compile the proper key extraction code. in fact, there is no
need for the GRT or ST to even be implemented at all. the key extraction
code and order could be used to generate comparison stuff just like
perl5 does. the ST and GRT are just implementation optimizations and
don't belong in a language level discussion.
hope that helps,
uri
--
Uri Guttman ------ [EMAIL PROTECTED] -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
