在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

几点:

1. 为了提高效率,尤其是为了最小化内存占用,您可能希望将对数组的引用传递给子例程.

2. 在列表上下文中,return 0将返回由单个元素组成的列表,因此将为true.裸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%   --

Answer 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

我喜欢它,当我的子线是单线!

Answer 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;

Answer 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真值条件".)

实际上,我认为它是一个'无'的结点运算符是一种落后的概念,所以我将使用all:

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

Answer 5

有人必须在这里投入功能编程解决方案,因为这种数学公式只需要递归.;)

sub isIncreasingArray {
  return 1 if @_ <= 1;   
  return (pop(@_) - $_[-1] == 1) && isIncreasingArray(@_);
}

至于子程序参数是一个数组与多个参数,请按照这种方式考虑:Perl总是向子程序发送一个参数列表作为数组@_.您可以将该数组中的参数作为单个标量移位或弹出,或者以整数列表作为数组运行.从你的子程序里面,它仍然是一个数组,句号.

如果你进入引用,是的,你可以将引用数组传递给子程序.该引用在技术上仍然作为包含一个标量值的数组(列表)传递给子例程:引用.首先,我会忽略所有这些,并在没有引用的情况下围绕基本操作.

调用子程序.这样,Perl就会秘密地将你的scalars列表转换为一系列标量:

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总是通过引用,但保护我们自己." 有时.实际上,我在子程序中创建自己的副本到本地化的"我的"变量.就这样做.