Perl: ordenar caracteres dentro de una cadena

Question

Tengo dos cadenas y me gustaría probar si son anagramas entre sí.

Para comprobar si la cadena A es un anagrama de la secuencia B, los caracteres de A y B están ordenados. Si las cadenas ordenadas resultantes coinciden exactamente, la cadena A y la cadena B son anagramas entre sí.

estoy split ing las cuerdas arriba en las matrices de caracteres, utilizando la rutina de Perl sort, join ing los caracteres de nuevo juntos, y las pruebas de igualdad de cadenas con eq:

sub anagram 
{ 
    my ($s1, $s2) = @_; 

    return (join '', sort { $a cmp $b } split(//, $s1)) eq 
     (join '', sort { $a cmp $b } split(//, $s2)); 
} 

¿Hay una manera de evitar tener que convertir entre los tipos escalar y de matriz (confiando en join y split)? Y si es así, ¿qué método es más eficiente?

Answer 1

Si ambas cadenas son variables, no creo que pueda hacerlo mucho mejor. Una alternativa es construir un algoritmo hash que asigne caracteres a sus recuentos, y luego comparar que los hash tengan las mismas claves y valores. Creo que esto es O (n) en lugar de O (n log n) para su enfoque, pero probablemente tendría un rendimiento real peor, excepto en cadenas muy largas.

Si quiere comparar cadenas de variables con una cadena de referencia fija, entonces tal vez el enfoque basado en hash podría pagar dividendos antes, ya que solo necesita usar la referencia una vez.

Answer 2

¿Hay una manera de evitar tener que convertir entre los tipos escalares y matrices (que dependen de join y split)? Y si es así, ¿qué método es más eficiente?

Dado que estas son dos preguntas separadas, responderé a ambas.

Sí, hay formas de hacerlo sin crear una matriz @ o hash % o lo que sea, y voy a resumir algunas; pero tu camino es más eficiente que cualquiera de estos.

Una forma es para tratar una cadena como una matriz de caracteres utilizando the substr function ($c = substr $s, 4, 1 conjuntos $c al quinto elemento del $s y substr($s, 4, 1) = $c establece el quinto elemento de $s a $c), e implementar cualquier algoritmo típico de clasificación en ella .

De forma alternativa, estoy bastante seguro de que podría implementar bubble-sort utilizando solo sustituciones de expresiones regulares con /e.

Por último, si usted está dispuesto a prescindir del enfoque de tipo-entonces comparar, se podría escribir:

sub anagram 
{ 
    my ($s1, $s2) = @_; 
    while($s1 =~ m/\G(.)/s) 
     { $s2 =~ s/\Q$1// or return ''; } 
    return $s2 eq ''; 
} 

Pero, de nuevo, el split -then- join es más eficiente que cualquiera de estos .

Answer 3

pensé usando combinaciones inteligentes para comparar las matrices sin necesidad de volver a crear la cadena tendría que oportunidad de superar el método de la OP

sub anagram_smatch { 
    return [sort split//,$_[0]] ~~ [sort split//,$_[1]]; 
} 

pero los puntos de referencia no llevan cuenta de eso.

  Rate smatch join 
smatch 1.73/s  -- -54% 
join 3.72/s 116%  -- 

Answer 4

Bueno, he encontrado una manera que es más de 30 veces más rápida, aunque, podría decirse que es una trampa. He incluido el código de Benchmark.pm para compararlo, ya que aparentemente no estás familiarizado con él.

El punto de referencia es:

  Rate Join Cheat 
Join 83294/s -- -97% 
Cheat 2580687/s 2998% -- 

Y el código. Después de la tercera línea, creo que vas a entender por qué su engaño podría decirse:

use v5.14; 
use Benchmark qw(cmpthese); 
use Inline 'C'; 

sub an_join { 
    my ($s1, $s2) = @_; 
    return (join '', sort split(//, $s1)) eq 
     (join '', sort split(//, $s2)); 
} 

use constant { 
    STR1 => 'abcdefghijklm', 
    STR2 => 'abcdefghijkmm', 
    STR3 => 'abcdefghijkml', 
}; 

cmpthese(
    0, 
    { 
     'Join' => 'an_join(STR1, STR2); an_join(STR1, STR3)', 
     'Cheat' => 'an_cheat(STR1, STR2); an_cheat(STR1, STR3)', 
    }); 

__END__ 
__C__ 

int an_cheat(const char *a, const char *b) { 
    unsigned char vec_a[26], vec_b[26]; 
    const char *p, *end; 

    memset(vec_a, 0, sizeof(vec_a)); 
    memset(vec_b, 0, sizeof(vec_b)); 

    end = a+strlen(a); 
    for (p = a; p < end; ++p) 
     if (*p >= 'a' && *p <= 'z') 
      ++vec_a[(*p)-'a']; 
    end = b+strlen(b); 
    for (p = b; p < end; ++p) 
     if (*p >= 'a' && *p <= 'z') 
      ++vec_b[(*p)-'a']; 

    return 0 == memcmp(vec_a, vec_b, sizeof(vec_a)); 
} 

Por supuesto, su engaño porque no es escrito en Perl-its en C. Además, tiene limitaciones no tiene la versión de Perl (solo funciona con caracteres ASCII en minúscula siendo el más significativo; simplemente ignora todo lo demás). Pero si realmente necesitas velocidad, puedes usar trampas como esta.

edición:

La extensión a todos Latin1 (así, los caracteres de 8 bits sin formato, en realidad). Además, encontré que el compilador logró optimizar un bucle más simple (sin aritmética de puntos) mejor, y es más fácil de leer también, entonces ... Benchmark me dice que la versión solo en minúscula ASCII es aproximadamente 10% más rápida:

int an_cheat_l1b(const char *a, const char *b) { 
    unsigned char vec_a[UCHAR_MAX], vec_b[UCHAR_MAX]; 
    size_t len, i; 

    memset(vec_a, 0, sizeof(vec_a)); 
    memset(vec_b, 0, sizeof(vec_b)); 

    len = strlen(a); 
    for (i = 0; i < len; ++i) 
     ++vec_a[((const unsigned char *)(a))[i]]; 
    len = strlen(b); 
    for (i = 0; i < len; ++i) 
     ++vec_b[((const unsigned char *)(b))[i]]; 

    return 0 == memcmp(vec_a, vec_b, sizeof(vec_a)); 
} 

Tenga en cuenta que la ventaja de la versión C aumenta a medida que la cadena se alarga, lo que se espera, ya que su Θ (n) en comparación con las versiones de Perl O (n · logn). También disminuye la penalización para Latin1 completo, lo que significa que la pena es probablemente el memcmp.