Недавно я наткнулся на следующий фрагмент кода на Perl, который возвращает минимальное числовое значение среди всех переданных аргументов.
return 0 + ( sort { $a <=> $b } grep { $_ == $_ } @_ )[0];
Я обычно использую простой линейный поиск, чтобы найти минимум/максимум в списке, который мне кажется простым и достаточно оптимальным. Является ли приведенный выше код лучше, чем простой линейный поиск? Что делать с perl в этом случае? Спасибо!
O() ничего не говорит о том, сколько времени занимает алгоритм. Например, при прочих равных условиях я всегда выбираю алгоритм 2 из следующих двух:
O() указывает, как время, необходимое алгоритму, масштабируется по мере увеличения размера входных данных. (Ну, его можно использовать для любых ресурсов, а не только для времени.) Поскольку два предыдущих ответа говорят только с точки зрения O(), они бесполезны.
Если вы хотите узнать, насколько быстр алгоритм, какой алгоритм лучше подходит для ввода заданного размера, вам нужно будет сравнить их.
В этом случае min для List::Util равно всегда значительно лучше.
$ 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% --
Код:
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);
Ты прав. Если вам не нужны отсортированные данные для какой-либо другой цели, простой линейный поиск будет самым быстрым. В любом случае, чтобы выполнить свою работу, сортировка должна просмотреть каждое данное как минимум один раз.
Только тогда, когда отсортированные данные будут полезны для других целей — или когда меня не заботят время работы, энергопотребление, тепловыделение и т. д., — я буду сортировать данные, чтобы найти минимальное и максимальное значения.
Теперь @SimeonVisser прав. Сортировка имеет O(n*log(n)). Это не намного медленнее, чем O(n), как думают многие программисты. В практических случаях накладные расходы на управление сбалансированным двоичным деревом сортировки (или другой подобной структурой), вероятно, имеют такое же значение, как и фактор log(n). Так что не надо пугаться перспективы сортировки! Однако линейный поиск все же быстрее: в этом вы совершенно правы.
Более того, @DavidO добавляет такой проницательный комментарий, что я бы процитировал его здесь своими словами:
Линейный поиск также является более простым алгоритмом для обобщения. Например, линейный поиск может быть легко (и относительно эффективно) основан на диске для больших наборов данных. Принимая во внимание, что сортировка на основе диска становится относительно дорогой и даже более сложной, если размеры полей не нормализованы.
Линейный поиск — O(n) по очевидным причинам. Сортировка — O(n log n) (см. сортировать в документации Perl). Так что да, линейный поиск действительно быстрее с точки зрения сложности. Это относится не только к Perl, но и к любому языку программирования, реализующему эти алгоритмы.
Как и во многих других задачах, существует несколько способов ее решения, а также несколько способов получить минимальное/максимальное значение списка. Концептуально я бы сказал, что линейный поиск лучше, когда вам нужен только минимум или максимум списка, поскольку проблема не требует сортировки.
