What's a one-liner with low computational complexity for returning the two biggest values of an array?

Question

This is more of a "I am interested if it's possible" than a "I really need it" question, but anyway: I know if I want the smallest value in a list using a custom function comparison, I can do it easily with List::Util::reduce.

my $biggest = reduce {comparison($a, $b) ? $b:$a} @myArray;

But if I want the two biggest values in that array? Again, with just one traversal of the array.

I can do it by writing a for loop, but I would really like a more perlish one-liner.

---

Edit: By just one traversal of the array, I meant that the computational complexity won't be bigger than O(n). Sorting all the articles is not that effective since I don't need everything sorted, just the two biggest values.

But I am probably asking too much :)

Answer 1

To find the max two values of a list, you can either loop across the values with two variables to hold the maximums:

my @list = qw(3 1 2 5 9 7 8 6 4);

my ($x, $y) = (0, 0);

($x, $y) = $_ > $x ? ($_, $x) :
           $_ > $y ? ($x, $_) : next for @list;

say "$x $y";  # '9 8'

or you can use a fold to reduce the list:

use List::Util 'reduce';

my $max = reduce {
    $b > $$a[0] ? [$b, $$a[0]] : 
    $b > $$a[1] ? [$$a[0], $b] : $a
} [0, 0], @list;

say "@$max"; # '9 8'

The two solutions are equivalent, the first is procedural in nature and requires external state, the second is functional and does not. The first is likely faster since it does not create any internal arrays for storage. Each only loops over the list once, so both are O(n)

Answer 2

There's always (sort { compare($b, $a) } @array)[0 .. 1] -- which works for any number of outputs you want, as long as you make sure not to try to take more items than exist in @array. The downside is that it does more work in sorting the whole array than it really has to.

You can also extend the reduce solution to keep any number of largest values seen so far, but I haven't yet been able to write a version of that that still has the "one-liner" feel :)

Answer 3

my @biggest_two = ( sort { $b <=> $a } @myArray )[0..1]