in reply to pop sort strangeness

pop pulls one item off the array. sort returns a list. That list may be assigned to an array, or it may be kept as a list. You're keeping it as a list, in a sort of scratch storage. In that form, it's not popable. ;)

This will work: 

my $max = pop @{[ sort @vals ]};

[download]

This works because you're turning the list returned by sort into an anonymous array, which is immediately dereferenced.

Either way, this is an inefficient solution, as it requires that the entire list be sorted each time you take a max. Use the List::Util max() function, or if you're going to roll your own, just do a linear search.


Dave

Replies are listed 'Best First'.
Re^2: pop sort strangeness
by Brovnik (Hermit) on Nov 15, 2004 at 16:18 UTC 
    my $max = pop @{[ sort @vals ]};

    [download]
    is the answer I was looking for, thanks. I realise it is inefficient, just came across the error and didn't immediately twig the list/array issue.

    --
    Brovnik
[reply]
[d/l]

      Indeed, it is very inefficient, by comparison to simply doing a linear search. First, you're sorting the list. That's O(N log N) for Perl's default sort type. Next, you're taking a copy of the list (yes, you're copying it) for the purpose of creating the anonymous array. That's about O(N). Next, you're dereferencing the array (a pretty quick action), and then you're popping something off the array (which is also pretty quick, but still is another step).

      So what you've got is O( N + N log N ), when you could just have O(N). That's not so good. And as someone else already pointed out, sort @vals does a string sort, not a numeric sort, so 11 will be sorted next to 1 instead of next to 12. If you must use the sort routine, at least change it to doing a numeric sort:

      my $max = pop @{[ sort { $a <=> $b } @vals ]};

      [download]

      And here's a linear search for max. 

      my $max = $vals[0];
$max = ( $_ > $max ) ? $_ : $max foreach @vals;

      [download]

      This version is a little terse, on purpose, to demonstrate that it's possible to do the linear search in just slightly more keystrokes than the sort pop method.


      Dave

[reply]
[d/l]
[select]
        Just for reference, here's some timing results on my machine for the following code snippet... 
        #!/usr/bin/perl -w

#Initialization
@vals = reverse "a".."daaaa";

#O(NlogN)
my $max = pop @{[ sort @vals ]};

#O(N)
#my $max = $vals[0];
#$max = ( $_ gt $max ) ? $_ : $max foreach @vals;

$e=@vals;
print "elements=$e max=$max\n";

        [download]
        Commenting out everything but the initialization section (i.e. not finding any maximum at all), this snippet executes in about 4.4 seconds on my machine. Using the sort to find the max, it takes about 6.2 seconds. Finally, using the linear method, it executes in about 5.1 seconds. So, for the 1,846,183 elements in this example, the sort method is about 2.5 times slower (6.2-4.4)/(5.1-4.4) than the linear search method. But the test is still dominated by just generating the large array. So you might not notice the efficiency gain if your data set is smaller than 1.8 million elements.

        -- All code is 100% tested and functional unless otherwise noted.
[reply]
[d/l]

In Section Seekers of Perl Wisdom