Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Re: Re: ${Schwartzian transform} ?

by sfink (Deacon)
on Sep 19, 2003 at 17:04 UTC ( #292713=note: print w/replies, xml ) Need Help??

in reply to Re: ${Schwartzian transform} ?
in thread ${Schwartzian transform} ?

I think the real answer is that the Schwartzian Transform is only applicable when you truly have an expensive key extraction that swamps the overhead of making copies, creating references and dereferencing them, etc. Your non-copying approach would only be valid when the expense of copying is significant. It doesn't change the fundamental purpose of the transform, which is is save on the O(n lg n) portion at the expense of the O(n) portion.

If you do have expensive copying, or just a not-very-expensive key extraction, then a better approach would be to eliminate both the copying and all of the reference stuff in one shot, by using indexes instead. Try adding this code into the benchmark:

Idx => '@pre = map {substr $_, 81} @array; @::d = @array[sort {$pre[$a] <=> $pre[$b]} 0..$#array]',
I get:
Benchmark: running GRT, Idx, Liz, ST for at least 5 CPU seconds...
       GRT:  5 wallclock secs ( 5.23 usr +  0.02 sys =  5.25 CPU) @ 67.24/s (n=353)
       Idx:  5 wallclock secs ( 5.25 usr +  0.03 sys =  5.28 CPU) @ 57.77/s (n=305)
       Liz:  5 wallclock secs ( 5.26 usr +  0.02 sys =  5.28 CPU) @ 37.50/s (n=198)
        ST:  5 wallclock secs ( 5.20 usr +  0.03 sys =  5.23 CPU) @ 36.52/s (n=191)
      Rate   ST  Liz  Idx  GRT
ST  36.5/s   --  -3% -37% -46%
Liz 37.5/s   3%   -- -35% -44%
Idx 57.8/s  58%  54%   -- -14%
GRT 67.2/s  84%  79%  16%   --
I haven't tried that with huge arrays to see if the expense of slicing starts to add up, though.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://292713]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2018-06-21 18:43 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (118 votes). Check out past polls.