|
Re: Check if sort has changed order
by davido (Cardinal) 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.
| [reply]
[d/l] |
|
|
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
| [reply]
[d/l] |
Re: Check if sort has changed order
by LanX (Saint) on May 10, 2013 at 12:39 UTC
|
| [reply] |
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"
}
| [reply]
[d/l] |
|
|
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.
| [reply]
[d/l] |
|
|
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.
| [reply] |
|
|
|
|
This seems to be a very clever way "to actually compare the lists."
| [reply] |
Re: Check if sort has changed order
by johngg (Canon) 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.
| [reply]
[d/l]
[select] |
Re: Check if sort has changed order
by hdb (Monsignor) 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.
| [reply] |
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.
| [reply] |
Re: Check if sort has changed order
by Rahul6990 (Beadle) on May 10, 2013 at 10:54 UTC
|
| [reply] |
|
|
| [reply] |
|
|
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.
| [reply] |
|
|
