logo - En Perl, ¿cómo puedo probar si una secuencia tiene la forma n, n+1, n+2,..., n+k?

perl vs python

Question

Estoy tratando de implementar una subrutina que toma una matriz como argumento ( o usa argumentos múltiples, todavía no han asimilado la diferencia ), y devuelve verdadero o falso dependiendo de si esa matriz es una secuencia creciente (cada número debe ser 1 más que el último):

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

Esto es lo que se me ocurrió:

sub isIncreasingArray {

    my $last;

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

    return 1;

}

Soy bastante nuevo para Perl y me pregunto si hay una manera más simple o más concisa de lograr esto. Además, ¿es lo que he escrito en línea con las mejores prácticas?

Answer 1

Alguien tiene que lanzar la solución de programación funcional aquí, ya que este tipo de fórmula matemática simplemente pide recursividad. ;)

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

En cuanto a que un argumento de subrutina sea una matriz versus múltiples argumentos, piénselo de esta manera: Perl siempre está enviando una lista de argumentos a su subrutina como la matriz @_. Puede desplazar o extraer argumentos de esa matriz como escalares individuales, u operar de otra manera en toda la lista como una matriz. Desde dentro de su subrutina, sigue siendo una matriz, punto.

Si entra en referencias, sí puede pasar una referencia a un arreglo en una subrutina. Esa referencia todavía se está pasando técnicamente a su subrutina como una matriz (lista) que contiene un valor escalar: la referencia. Primero, ignoraría todo esto y me enfocaría en la operación básica sin referencias.

Llamar a la subrutina. De esta forma, Perl está convirtiendo en secreto su lista de escalares en una matriz de escalares:

isIncreasingArray(1,2,3,4); 

De esta manera, Perl está pasando su matriz:

@a = (1,2,3,4);
$answer = isIncreasingArray(@a); 

De cualquier manera, la subrutina obtiene una matriz. Y es una copia *, de ahí la charla de eficiencia de referencias aquí. No se preocupe por eso para K <10,000, incluso con mi solución ridículamente ineficiente, académica, elegante y recursiva aquí, que todavía demora menos de 1 segundo en mi computadora portátil:

print isIncreasingArray(1..10000), "/n"; # true

* Una copia: más o menos, ¿pero no realmente? Consulte los comentarios a continuación y otros recursos, por ejemplo, PerlMonks . "Se podría argumentar que Perl siempre hace Pass-By-Reference, pero nos protege de nosotros mismos". A veces. En la práctica, hago mis propias copias dentro de las subrutinas en "mis" variables localizadas. Solo haz eso.

Answer 2

Cualquiera que sea la implementación que use, no estaría de más hacer algunas comprobaciones rápidas de antemano:

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

Answer 3

Esta es la forma más corta a la que podría llegar, verifique cada elemento en un mapa para ver si es igual al yo aumentado, devuelva un conjunto de 0 y 1, cuente el 1 y haga coincidir el tamaño original del conjunto.

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 4

Terminé con algo un poco más largo que el tuyo. Lo que significa, supongo, que no hay nada de malo en tu solución :)

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

Un par de puntos:

1. Para mayor eficiencia, especialmente para minimizar la huella de memoria, probablemente desee pasar una referencia a una matriz a la subrutina.

2. En el contexto de la lista, return 0 devolverá una lista que consta de un único elemento y, por lo tanto, será verdadera. un return simple es suficiente cuando se quiere devolver false y hace el trabajo en todos los contextos.

Probablemente sea posible reducir el número de comparaciones a la mitad al comparar la diferencia entre el primero y el último, el segundo y el segundo, etc. para ver las diferencias en los índices, pero no lo estoy pensando claramente en este momento.

Aquí hay una versión ligeramente diferente basada en la tuya. Tenga en cuenta que debe usar strict y asegurarse de que alcance su variable de bucle con 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;
}

Y, por supuesto, algunos puntos de referencia:

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

Usando una "unión" pre-6:

sub is_increasing_list { 
    use List::MoreUtils qw<none>;
    my $a = shift;
    return none { 
        ( my $v, $a ) = (( $_ - $a != 1 ), $_ ); 
        $v;
    } @_;
}

La expresión none también podría escribirse (más crípticamente) como

return none { [ ( $a, undef ) = ( $_, ( $_ - $a - 1 )) ]->[-1]; } @_;

(Si la restricción es esa $ x [$ n + 1] - $ x [$ n] == 1, entonces al restar 1 también se produce una "condición de verdad Perl").

En realidad, ahora que lo pienso, un operador de unión "nula" es un poco retrógrado al concepto, así que usaré el all :

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

Answer 7

¿Cómo es que nadie ha encontrado una solución inteligente?

Si bien este no es tan eficiente como algunas de las otras soluciones, tiene el beneficio adicional de trabajar con cadenas también.

EDITAR

Sub ahora devuelve true para listas vacías y de elemento único porque eso es lo que los expertos dicen que debería hacer :

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

¡Me encanta cuando mi sub es de una sola línea!