Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Check if sort has changed order

by HYanWong (Acolyte)
on May 10, 2013 at 09:31 UTC ( #1032922=perlquestion: print w/ replies, xml ) Need Help??
HYanWong has asked for the wisdom of the Perl Monks concerning the following question:

Hi all, Is there a simple way to check if a call to sort has changed the order of a list? Or do I have to actually compare the lists before and after the sort (e.g. using ~~)?

Comment on Check if sort has changed order
Download Code
Re: Check if sort has changed order (eq)
by Anonymous Monk on May 10, 2013 at 09:38 UTC
    my @f = ( 4, 2 ); my @g = sort @f; if( "@f" eq "@g" ){ die "already sorted, can't have that\n" }

      Ha, stupid memory allocation tricks

      my @f = ( 4, 2 ); print join ' ', int \$_, \$_, "$_\n" for @f;print "\n"; @f = sort @f; print join ' ', '#', int \$_, \$_, "$_\n" for @f;print "\n"; my $prev = 0; for my $next ( @f ){ if( $prev ){ die "BEEN SORTED" if $prev > \$next; } $prev = \$next; } __END__ $ perl fa 4165804 SCALAR(0x3f90ac) 4 4165980 SCALAR(0x3f915c) 2 # 4165980 SCALAR(0x3f915c) 2 # 4165804 SCALAR(0x3f90ac) 4 BEEN SORTED at fa line 8.
        That won't work for whatever sort condition.

        I'd probably rather compare the MD5 checksum of the scalar references in the list before and after the sort.

      This seems to be a very clever way "to actually compare the lists."
      Bill
Re: Check if sort has changed order
by Rahul6990 (Beadle) on May 10, 2013 at 10:54 UTC
      > This link will help.

      Actually it will not!

      The SO question is about comparing unordered sets, while the OP explicitly needs to assure that the order of identical sets didn't change.

      Cheers Rolf

      ( addicted to the Perl Programming Language)

        You can apply array_diff function on the sorted and unsorted file and check the output file to see weather sort had done any modification or not.
Re: Check if sort has changed order
by LanX (Canon) on May 10, 2013 at 12:39 UTC
    > Or do I have to actually compare the lists before and after the sort (e.g. using ~~)?

    Yes!

    But could you please explain your use case? I'm smelling an XY question... =)

    Cheers Rolf

    ( addicted to the Perl Programming Language)

Re: Check if sort has changed order
by hdb (Prior) on May 10, 2013 at 14:22 UTC

    Why don't you test if the array needs sorting first? This probably takes as much time as comparing the result to the original. And you might save the sorting if not needed.

Re: Check if sort has changed order
by Anonymous Monk on May 10, 2013 at 14:22 UTC

    Well, I had the hair-ball idea of cooking the sort-compare function to detect if it actually produced a particular result-type during the sort ... but it didn’t work.   Oh, well.

Re: Check if sort has changed order
by davido (Archbishop) on May 10, 2013 at 15:07 UTC

    Sorting is an O(n log n) operation. Testing a list for sortedness is an O(n) operation. Test first, then sort if necessary.

    use strict; use warnings; use List::Util qw( first ); my @x = qw( 1 3 2 4 5 ); if( defined first { $x[$_] > $x[$_+1] } 0 .. $#x - 1 ) { @x = sort { $a <=> $b } @x; }

    Strategies for testing whether a change has been made after sorting has been applied will either involve a checksum of some type (ie, take an MD5 of the list's contents before and again after), or keeping a copy of the pre-sorted list for comparison. One way you're throwing CPU cycles at the problem, and the other way, you're throwing memory at it. If you can just check whether sorting is necessary ahead of time, you conserve both.


    Dave

      If you can just check whether sorting is necessary ahead of time, you conserve both.

      I think I agree with you :)

      I thought maybe its detectible from within sort callback if order has changed, but it doesn't look that way

Re: Check if sort has changed order
by johngg (Abbot) on May 10, 2013 at 15:47 UTC

    Use Digest::MD5 to see if something has changed. The md5_hex() function will concatenate its arguments then operate on the concatenated string.

    $ perl -Mstrict -Mwarnings -MDigest::MD5=md5_hex -E ' my @arr1 = qw{ tiger bear shark lion }; say md5_hex( @arr1 ); say md5_hex( sort @arr1 );' 4c15f2e87b25ac112649edfd426d5082 27f304e4e99072211806f923bbb39705 $ perl -Mstrict -Mwarnings -MDigest::MD5=md5_hex -E ' > my @arr1 = qw{ antelope cow deer sheep }; > say md5_hex( @arr1 ); > say md5_hex( sort @arr1 );' 1f0210f9b5d6dababea92da7018905da 1f0210f9b5d6dababea92da7018905da $

    I hope this is of interest.

    Cheers,

    JohnGG

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1032922]
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (11)
As of 2014-11-28 23:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (200 votes), past polls