Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re^2: Sort undef

by sundialsvc4 (Abbot)
on Jun 13, 2017 at 01:46 UTC ( #1192640=note: print w/replies, xml ) Need Help??


in reply to Re: Sort undef
in thread Sort undef

Flinching not-the-slightest from any “down-vote storms” that might possibly originate from my saying so . . .

I have not the slightest idea how this bit of code is supposed to solve this problem, and I am never going to waste my team’s time, ostensibly trying to find out.

If you submitted a “solution” like that once, if you were on my team, then I would kick you up the river.   If you then did it twice, you would not be on my team.

You see, it really does not matter that your “solution,” whatever it turns out to be, “solves the problem.”  (That is to say, “in every test-case, if any, that occurred to you.)   What really matters to the Team is that:   “the problem really is Gone.”   And, provably so.   (Emphasis:   “provably!”)

This is, in fact, a well-known issue that the Perl language is specifically designed to handle.   (And, oh by the way, Perl did it in exactly the same way that every other language with a built-in SORT verb did.)   Therefore, since this is actually a very-old issue that was first very-well solved in the early 1960’s, and which was therefore well-known to even the original Perl implementors, please do not try to plow any new furrows here.

Replies are listed 'Best First'.
Re^3: Sort undef
by marinersk (Priest) on Jun 13, 2017 at 04:20 UTC

    The Wikipedia author is being polite.

    Doing it the 1960s way:

    @sorted = sort { foo($a) cmp foo($b) } @unsorted;

    Doing it the 1990s way*:

    @sorted = map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [$_, foo($_)] } @unsorted;

    The author then gently chastises the older approach:

    While it is shorter to code, the naive approach here could be much less efficient if the key function (called foo in the example above) is expensive to compute.

    The explanation on the Wikipedia page is also pretty straightforward. This should probably be considered a core Perl technique within the profession; that is to say, while not knowing about the Schwartzian Transform is no crime, it is a tragedy compelling immediate correction for anyone in the business, should the topic come up. The efficiency gains, when applied to appropriate circumstances, are too great to ignore. Perl programmers should learn not only the technique, but why it is better so they are empowered to better choose when to use it.

    *We've put people on the Moon in the meantime, so forward progress is not only permissible, but recommended.

      Update: Added undef's to the list to imitate the OP's request regarding undef's. After sorting, move any undef's from the start of the list to the end.

      The following is a fun exercise if wanting to simulate work inside the foo function.

      Thank you, Randal L. Schwartz for the Schwartzian transform technique.

      use strict; use warnings; # http://www.perlmonks.org/?node_id=1192544 use List::Util 'shuffle'; use Time::HiRes 'time'; sub foo { sleep 0; $_[0] } srand 0; my @unsorted = shuffle ( 'aaaa'..'zzzz', (undef) x 7 ); printf "Number of elements to sort : %d\n", scalar @unsorted; { no warnings 'uninitialized'; my $start = time; my @sorted = sort { foo($a) cmp foo($b) } @unsorted; # move any undef's from the start of the list to the end my $i = 0; $i++ until ( defined $sorted[$i] ); push @sorted, splice(@sorted, 0, $i) if $i; printf "Without Schwartzian transform : %6.3f seconds\n", time - $start; } { no warnings 'uninitialized'; my $start = time; my @sorted = map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [ $_, foo($_) ] } @unsorted; # move any undef's from the start of the list to the end my $i = 0; $i++ until ( defined $sorted[$i] ); push @sorted, splice(@sorted, 0, $i) if $i; printf "With ++ Schwartzian transform : %6.3f seconds\n", time - $start; } __END__ Number of elements to sort : 456983 Without Schwartzian transform : 24.939 seconds With ++ Schwartzian transform : 2.832 seconds

      Perl is fun. I'm always learning and had no idea the speed gain possible with the Schwartzian transform until now. I also tried without sleep 0 inside foo to better understand the overhead imposed by method calling. The Schwartzian transform is still faster. Wow!

      sub foo { $_[0] } Number of elements to sort : 456983 Without Schwartzian transform : 4.680 seconds With ++ Schwartzian transform : 2.053 seconds

      Regards, Mario

Re^3: Sort undef
by huck (Vicar) on Jun 13, 2017 at 02:17 UTC

    I am never going to waste my team’s time, ostensibly trying to find out.

    Tisc, Tisc, even a cave-man can learn something new, Ive known of it for decades,

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

    I am glad not to have to be on your team, you dont even care enough to keep trying. How long has it been since you just gave up?

Re^3: Sort undef
by LanX (Bishop) on Jun 13, 2017 at 03:54 UTC
    Calling yourself a Perl expert and not knowing the "Schwartzian transform" is remarkable, but not being able to google it even if it's explicitly mentioned ... wow!

    My deepest respect, you have written over 650 negative nodes here!

    You sir are my anti-hero! :)

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Je suis Charlie!

Re^3: Sort undef
by karlgoethebier (Monsignor) on Jun 13, 2017 at 07:04 UTC
    "...I have not the slightest idea..."

    This is an known issue.

    «The Crux of the Biscuit is the Apostrophe»

    Furthermore I consider that Donald Trump must be impeached as soon as possible

Re^3: Sort undef
by Anonymous Monk on Jun 13, 2017 at 14:59 UTC
    And, oh by the way, Perl did it in exactly the same way that every other language with a built-in SORT verb did.
    Actually, the sort function in Python 3 doesn't take a (two-arg) comparison function. It takes a (one-arg) key-generating function. Essentially, the Schwartzian transformation is built right in.
    >>> x = ['c','B','a'] >>> x.sort(); print(x) ['B', 'a', 'c'] >>> x.sort(key=str.lower); print(x) ['a', 'B', 'c']
    (You can play games with operator overloading to get comparison-function behavior, but that's considered "unpythonic.")

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2018-07-20 14:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    It has been suggested to rename Perl 6 in order to boost its marketing potential. Which name would you prefer?















    Results (435 votes). Check out past polls.

    Notices?