Подтвердить что ты не робот

В 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, и мне интересно, есть ли более простой или более сжатый способ достижения этого? Кроме того, что я написал в соответствии с лучшими практиками?

4b9b3361

ОТВЕТЫ

Ответ 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] != $#_;
   ...
}