在 Perl 中，如何测试序列是否为 n, n + 形式？ 1、n+ 2, ..., n + k？

Question

我正在尝试实现一个子例程，它接受一个数组作为其参数（或使用多个参数 - 仍然没有完全理解差异），并根据该数组是否是一个返回 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 很陌生，想知道是否有更简单或更简洁的方法来实现这一点？另外，我写的内容符合最佳实践吗？

Answer 1

这是我能想到的最短形式，检查映射中的每个元素，看看它是否等于增加的 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;
}

Answer 2

无论您使用哪种实现，事先进行一些快速检查都不会有什么坏处：

sub isSimplyIncreasingSequence {
   return 1 if @_ < 2;
   return 0 if $_[-1] - $_[0] != $#_;
   ...
}

Answer 3

为什么没有人想出智能匹配的解决方案？

虽然这个解决方案不如其他一些解决方案高效，但它还具有使用字符串的额外好处。

编辑

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

我喜欢我的潜艇是单线的！

Answer 4

我最终得到的东西比你的长一点。我认为这意味着您的解决方案没有任何问题:)

#!/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;

Answer 5

使用 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 真值条件”。）

实际上，认为“无”连接运算符有点倒退了这个概念，所以我将使用 all：

sub is_increasing_list { 
    use List::MoreUtils qw<all>;
    my $a = shift;
    return all { [ ( $a, undef ) = ( $_, ( $_ - $a == 1 )) ]->[-1]; } @_;
}

Answer 6

有人必须在这里引入函数式编程解决方案，因为这种数学公式只需要递归。 ;)

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 总是进行引用传递，但可以保护我们免受我们自己的伤害。”有时。在实践中，我在子例程内将自己的副本复制到本地化的“我的”变量中。就这么做吧。

Answer 7

有几点：

1. 为了提高效率，特别是为了最大限度地减少内存占用，您可能希望将对数组的引用传递给子例程。

2. 在列表上下文中，return 0 将返回由单个元素组成的列表，因此为 true。当您想要返回 false 并在所有上下文中执行此操作时，只需 return 就足够了。

通过比较第一个和最后一个、第二个和倒数第二个等之间的差异，可以将比较次数减少一半，以查看差异等于索引差异，但我不认为这样 现在就很清楚了。

这是与您的版本略有不同的版本。请注意，您应该使用 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%   --