In Perl, how can I test whether a sequence is of the form n, n + 1, n + 2, ..., n + k?

Question

I'm trying to implement a subroutine that takes an array as its argument (or uses multiple arguments — still haven't quite grokked the difference), and returns true or false depending on whether that array is an increasing sequence (each number must be 1 more than the last):

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

This is what I've come up with:

sub isIncreasingArray {

    my $last;

    foreach $n (@_) {
        return 0 if defined($last) && $last != $n - 1;
        $last = int($n);
    }

    return 1;

}

I'm quite new to Perl and am wondering if there's a simpler or more concise way of achieving this? Also, is what I've written in line with best practices?

Answer 1

A couple of points:

1. For efficiency, especially to minimize memory footprint, you probably want to pass a reference to an array to the subroutine.

2. In list context, return 0 will return a list consisting of a single element and thus will be true. a bare return suffices when you want to return false and does the job in all contexts.

It is probably possible to cut the number of comparisons in half by comparing the difference between the first and the last, the second and the second last etc. to see differences equal difference in indexes, but I am not thinking that clearly right now.

Here is a slightly different version based on yours. Note that you should use strict and make sure to scope your loop variable using 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;
}

And, of course, some benchmarks:

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