Sorting vs Linear search for finding min/max

complexity-theory, perl, sorting

Solution

O() doesn't say anything about how long an algorithm takes. For example, all else being equal, I'd always choose Algorithm 2 among the following two:

- Algorithm 1: O(2*N + 1000 days) = O(N)

- Algorithm 2: O(5*N + 100 ms) = O(N log N)

O() specifies how the time the algorihm takes scales as the size of the input increases. (Well, it can be used for any resources, not just time.) Since the earlier two answers only talk in terms of O(), they are useless.

If you want to know how fast an algorithm which algorithm is better for an input of a given size, you'll need to benchmark them.

In this case, it looks like List::Util's `min` is always significantly better.

$ perl x.pl 10
           Rate  sort LUmin
sort  1438165/s    --  -72%
LUmin 5210584/s  262%    --

$ perl x.pl 100
           Rate  sort LUmin
sort   129073/s    --  -91%
LUmin 1485473/s 1051%    --

$ perl x.pl 1000
          Rate  sort LUmin
sort    6382/s    --  -97%
LUmin 199698/s 3029%    --

Code:

use strict;
use warnings;

use Benchmark  qw( cmpthese );
use List::Util qw( min );

my %tests = (
   'sort'  => 'my $x = ( sort { $a <=> $b } @n )[0];',
   'LUmin' => 'my $x = min @n;',
);

$_ = 'use strict; use warnings; our @n; ' . $_
   for values %tests;

local our @n = map rand, 1..( $ARGV[0] // 10 );
cmpthese(-3, \%tests);

Problem

Recently, I came across the following piece of code in perl that returns the minimum numeric value among all passed arguments. ``` return 0 + ( sort { $a <=> $b } grep { $_ == $_ } @_ )[0]; ``` I usually use simple linear search to find the min/max in a list, which for me seems to be simple and adequately optimal. Is the above code in any way better than simple linear search? Anything to do with perl in this case? Thanks!

Original source