В Perl, как я могу проверить, имеет ли последовательность форму n, n + 1, n + 2,..., n + k?
Я пытаюсь реализовать подпрограмму, которая принимает массив в качестве аргумента (или использует несколько аргументов — все еще не совсем разглядела разницу) и возвращает true или false в зависимости от того, является ли этот массив возрастающей последовательностью ( каждое число должно быть на 1 больше, чем последнее):
isIncreasingArray(1,2,3,4); # true
isIncreasingArray(1,2,3,1); # false
isIncreasingArray(0,9,1); # false
isIncreasingArray(-2,-1,0); # true
isIncreasingArray(1,1,1,1); # false
Вот что я придумал:
sub isIncreasingArray {
my $last;
foreach $n (@_) {
return 0 if defined($last) && $last != $n - 1;
$last = int($n);
}
return 1;
}
Я совершенно новый для Perl, и мне интересно, есть ли более простой или более сжатый способ достижения этого? Кроме того, что я написал в соответствии с лучшими практиками?
Ответы
Ответ 1
Несколько пунктов:
-
Для эффективности, особенно для минимизации объема памяти, вы, вероятно, захотите передать ссылку на массив подпрограмме.
-
В контексте списка return 0
будет возвращен список, состоящий из одного элемента и, таким образом, будет истинным. голый return
достаточно, если вы хотите вернуть false
и выполняет задание во всех контекстах.
Вероятно, можно сократить количество сравнений пополам, сравнив разницу между первой и последней, второй и второй последней и т.д., чтобы увидеть различия, равные разнице в индексах, но я не думаю, что ясно право Теперь.
Вот немного другая версия, основанная на вашем. Обратите внимание, что вы должны использовать strict
и не забудьте указать свою переменную цикла с помощью my
:
#!/usr/bin/env perl
use strict; use warnings;
use Carp qw(croak);
use Test::More;
ok( isSimplyIncreasingSequence( [ 1298 ] ) ); # true
ok( isSimplyIncreasingSequence( [1,2,3,4] ) ); # true
ok( not isSimplyIncreasingSequence( [1,2,3,1] ) ); # false
ok( not isSimplyIncreasingSequence( [0,9,1] ) ); # false
ok( isSimplyIncreasingSequence( [-2,-1,0] ) ); # true
ok( not isSimplyIncreasingSequence( [1,1,1,1] ) ); # false
done_testing();
sub isSimplyIncreasingSequence {
my ($seq) = @_;
unless (defined($seq)
and ('ARRAY' eq ref $seq)) {
croak 'Expecting a reference to an array as first argument';
}
return 1 if @$seq < 2;
my $first = $seq->[0];
for my $n (1 .. $#$seq) {
return unless $seq->[$n] == $first + $n;
}
return 1;
}
И, конечно, некоторые ориентиры:
#!/usr/bin/env perl
use strict; use warnings;
use Benchmark qw( cmpthese );
use Carp qw( croak );
my %cases = (
ordered_large => [1 .. 1_000_000],
ordered_small => [1 .. 10],
unordered_large_beg => [5, 1 .. 999_000],
unordered_large_mid => [1 .. 500_000, 5, 500_002 .. 1_000_000],
unordered_large_end => [1 .. 999_999, 5],
);
for my $case (keys %cases) {
print "=== Case: $case\n";
my $seq = $cases{$case};
cmpthese -3, {
'ref' => sub { isSimplyIncreasingSequence($seq) },
'flat' => sub {isIncreasingArray(@{ $seq } ) },
};
}
sub isSimplyIncreasingSequence {
my ($seq) = @_;
unless (defined($seq)
and ('ARRAY' eq ref $seq)) {
croak 'Expecting a reference to an array as first argument';
}
return 1 if @$seq < 2;
my $first = $seq->[0];
for my $n (1 .. $#$seq) {
return unless $seq->[$n] == $first + $n;
}
return 1;
}
sub isIncreasingArray {
my $last;
foreach my $n (@_) {
return 0 if defined($last) && $last != $n - 1;
$last = int($n);
}
return 1;
}
=== Case: unordered_large_mid
Rate flat ref
flat 4.64/s -- -18%
ref 5.67/s 22% --
=== Case: ordered_small
Rate ref flat
ref 154202/s -- -11%
flat 173063/s 12% --
=== Case: ordered_large
Rate flat ref
flat 2.41/s -- -13%
ref 2.78/s 15% --
=== Case: unordered_large_beg
Rate flat ref
flat 54.2/s -- -83%
ref 315/s 481% --
=== Case: unordered_large_end
Rate flat ref
flat 2.41/s -- -12%
ref 2.74/s 14% --
Ответ 2
Почему никто не придумал решение с умным совпадением?
Несмотря на то, что это не так эффективно, как некоторые другие решения, он имеет дополнительное преимущество в работе со строками.
ИЗМЕНИТЬ
Sub теперь возвращает true для пустых и одноэлементных списков, потому что то, что эксперты говорят, что он должен делать:
use strict;
use warnings;
use 5.010;
sub is_simply_increasing { @_ < 2 || @_ ~~ [$_[0] .. $_[-1]] }
say ( is_simply_increasing(1,2,3,4) ? 'true' : 'false' ); # true
say ( is_simply_increasing(1,2,3,1) ? 'true' : 'false' ); # false
say ( is_simply_increasing(0,9,1) ? 'true' : 'false' ); # false
say ( is_simply_increasing(-2,-1,0) ? 'true' : 'false' ); # true
say ( is_simply_increasing(1,1,1,1) ? 'true' : 'false' ); # false
say ( is_simply_increasing(1,4,1,-1) ? 'true' : 'false' ); # false
say ( is_simply_increasing('a','c') ? 'true' : 'false' ); # false
say ( is_simply_increasing('love'..'perl') ? 'true' : 'false' ); # true
say ( is_simply_increasing(2) ? 'true' : 'false' ); # true
say ( is_simply_increasing() ? 'true' : 'false' ); # true
Мне нравится, когда мой sub - однострочный!
Ответ 3
У меня получилось что-то немного дольше твоего. Что означает, я полагаю, что нет ничего плохого в вашем решении:)
#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Test::More;
sub is_increasing_array {
return unless @_;
return 1 if @_ == 1;
foreach (1 .. $#_) {
return if $_[$_] != $_[$_ - 1] + 1;
}
return 1;
}
ok(is_increasing_array(1,2,3,4)); # true
ok(!is_increasing_array(1,2,3,1)); # false
ok(!is_increasing_array(0,9,1)); # false
ok(is_increasing_array(-2,-1,0)); # true
ok(!is_increasing_array(1,1,1,1)); # false
done_testing;
Ответ 4
Использование предварительного 6 "перехода":
sub is_increasing_list {
use List::MoreUtils qw<none>;
my $a = shift;
return none {
( my $v, $a ) = (( $_ - $a != 1 ), $_ );
$v;
} @_;
}
Выражение none
также может быть написано (более критически) как
return none { [ ( $a, undef ) = ( $_, ( $_ - $a - 1 )) ]->[-1]; } @_;
(Если ограничение состоит в том, что $x [$ n + 1] - $x [$ n] == 1, то вычитание 1 также делает "условие истинности Perl".)
На самом деле, подумайте об этом, оператор "none" -перехода отчасти отстает от концепции, поэтому я буду использовать all
:
sub is_increasing_list {
use List::MoreUtils qw<all>;
my $a = shift;
return all { [ ( $a, undef ) = ( $_, ( $_ - $a == 1 )) ]->[-1]; } @_;
}
Ответ 5
Кто-то должен бросить здесь функциональное программирование, так как эта математическая формула просто требует рекурсии.;)
sub isIncreasingArray {
return 1 if @_ <= 1;
return (pop(@_) - $_[-1] == 1) && isIncreasingArray(@_);
}
Что касается аргумента подпрограммы, являющегося массивом в сравнении с несколькими аргументами, подумайте об этом так: Perl всегда отправляет список аргументов вашей подпрограмме в виде массива @_. Вы можете сдвигать или вызывать аргументы из этого массива в виде отдельных скаляров или иначе использовать весь список в виде массива. Изнутри вашей подпрограммы это еще массив, период.
Если вы попадаете в ссылки, да, вы можете передать ссылку на массив в подпрограмму. Эта ссылка по-прежнему технически передается вашей подпрограмме как массив (список), содержащий одно скалярное значение: ссылка. Сначала я проигнорировал все это и обернул бы голову вокруг базовой операции без ссылок.
Вызов подпрограммы. Таким образом, Perl тайно преобразует ваш голый список скаляров в массив скаляров:
isIncreasingArray(1,2,3,4);
Таким образом, Perl передает ваш массив:
@a = (1,2,3,4);
$answer = isIncreasingArray(@a);
В любом случае подпрограмма получает массив. И это копия *, следовательно, полезность говорит о ссылках здесь. Не беспокойтесь об этом за K < 10 000 даже с моим нелепо неэффективным, академичным, элегантным, рекурсивным решением здесь, которое по-прежнему занимает менее 1 секунды на моем ноутбуке:
print isIncreasingArray(1..10000), "\n"; # true
* Копия: вроде, но не совсем? См. Комментарии ниже и другие ресурсы, например. PerlMonks. "Можно было бы утверждать, что Perl всегда делает Pass-By-Reference, но защищает нас от самих себя". Иногда. На практике я делаю свои собственные копии внутри подпрограмм локализованными "моими" переменными. Просто сделайте это.
Ответ 6
Это кратчайшая форма, которую я мог бы придумать, проверить каждый элемент на карте, чтобы убедиться, что она равна увеличению self, вернуть набор из 0 и 1, считать 1 и сопоставить с исходным размером набор.
print isIncreasingArray(1,2,3),"\n";
print isIncreasingArray(1,2,1),"\n";
print isIncreasingArray(1,2),"\n";
print isIncreasingArray(1),"\n";
sub isIncreasingArray {
$i = $_[0];
(scalar grep { 1 == $_ } map { $i++ == $_ } @_) == scalar(@_) || 0;
}
Ответ 7
Какую бы реализацию вы ни использовали, было бы не очень полезно сделать некоторые быстрые проверки заранее:
sub isSimplyIncreasingSequence {
return 1 if @_ < 2;
return 0 if $_[-1] - $_[0] != $#_;
...
}