Autor Tema: Perl golf, primalidad y expresiones regulares

0 Usuarios y 1 Visitante están viendo este tema.

29 Octubre, 2015, 14:38
Leído 1234 veces

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3.386
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hace un tiempo, leyendo el fantástico libro Perl One-Liners: 130 Programs That Get Things Done de Peteris Krumins, me encontré con una expresión regular que chequea si un número dado es primo  :o.

En realidad, chequea si es compuesto siendo el test de primalidad de la forma unario($candidato_a_primo) !~ $regex (o sea, da por primo un entero sii un string de unos formado a partir de él mediante la función unario(), NO verifica cierta expresión regular).

La expresión regular aparentemente es de la autoría del famoso Perl hacker alemán Abigail (del cual se desconoce en realidad si es una mujer: hay foros que hablan de él y otros de ella), y apareció en Internet por primera vez en 1998. Abigail es un personaje enigmático en la comunidad Perl y se hizo muy conocido/a a partir de sus brillantes programas JAPHs, así como por su genial destreza con las expresiones regulares. (Un programa JAPH es un programa que imprime en la salida estándar el texto "Just another Perl hacker," de la forma más críptica posible, tal como lo hace el programa que está en mi firma, que se me ocurrió un día que estaba aburrido  :laugh:).

Suponiendo que el candidato a primo está en la variable $_, el test de primalidad es el siguiente:

(1x$_) !~ /^1?$|^(11+?)\1+$/

La idea es extremadamente sencilla, pero de una belleza y creatividad inusitadas. Hay quienes han tenido problemas en desentrañar cómo es que la anterior expresión regular funciona; en mi caso, capté la idea antes de leer la explicación en el libro, y reitero, que la idea es muy sencilla y muy bella. Pongo la explicación en el Spoiler para dar la oportunidad a que lo piensen antes de ver la solución.

Explicación
Primero que nada, se convierte el número a su representación unaria con 1x$_, que no es otra cosa que el string "1" concatenado consigo mismo tantas veces como $_, que es el número cuya primalidad queremos determinar. Por ejemplo, si $_ vale 5, 1x$_ será el string "11111". La idea detrás es la siguiente: si el número es compuesto, entonces es posible descomponer esa cadena de unos en subcadenas de unos de igual tamaño. Por ejemplo, si el número es 4, entonces "1111" puede descomponerse como "11"."11" lo que puede interpretarse como \[ 4=2\times 2 \] (el primer 2 es la cantidad de subcadenas, y el segundo 2 la longitud de las mismas). Si es 6, entonces "111111" es "111"."111" (\[ 3\times 2 \]) o también "11"."11"."11" (\[ 2\times 3 \]).

Luego la expresión regular tiene dos partes: la primer parte es ^1?$ que matchea "1" y el string vacío. Ninguno de éstos es un número primo así que esa parte de la regexp los descarta. La segunda parte, ^(11+?)\1+$ chequea si una subcadena de 2 o más unos (que es capturada con los paréntesis) repetida una o más veces, determina la representación unaria entera. Si se cumple esa condición, el número es compuesto o de lo contrario, es primo.

Por ejemplo, para el caso del número 5, su representación unaria es "11111" entonces (11+?), como el cuantificador +? es non-greedy, captura inicialmente "11" y la backreference \1 queda conteniendo "11" luego toda la expresión regular se transforma en ^11(11)+$. Como "11111" no matchea esta expresión regular, falla. A continuación, el motor de expresiones regulares prueba avanzar un "1" más en la captura de (11+?), o sea, ahora captura "111" y \1 queda con "111". La expresión regular se vuelve ^111(111)+$, que también falla. Luego continúa el backtracking capturando "1111" y "11111", fallando en ambos casos. Como fracasa con todas las posibles capturas, "11111" no matchea la regexp y se concluye que 5 es primo.
[cerrar]

Si están en un SO basado en Unix, pueden probar esta expresión regular de esta manera:

$ perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ es primo"'

La opción -n pone cada línea de la entrada estándar en $_ de manera que cuando presionen enter, perl quedará esperando a que introduzcan un número para evaluar la condición. Una vez que terminen de "jugar", pueden presionar ^C para enviare la señal SIGINT al proceso e interrumpir su ejecución, o bien ^D (carácter EOF). También pueden usar un pipe | para conectar la salida de un programa con la entrada de otro. Por ejemplo,

$ perl -le 'print for 1..100' | perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ es primo"'
2 es primo
3 es primo
5 es primo
7 es primo
11 es primo
13 es primo
17 es primo
19 es primo
23 es primo
29 es primo
31 es primo
37 es primo
41 es primo
43 es primo
47 es primo
53 es primo
59 es primo
61 es primo
67 es primo
71 es primo
73 es primo
79 es primo
83 es primo
89 es primo
97 es primo
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

29 Octubre, 2015, 14:43
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7.291
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

29 Octubre, 2015, 15:45
Respuesta #2

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3.386
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
¡Es muy buena la regexp de primos!

Sí  :)

¿Alguna estimación del costo computacional?  >:D

Bueno, dada la entrada \[ n \], en el peor caso, o sea, si \[ n \] es NO primo, ¿cuántas iteraciones efectuaría el motor de expresiones regulares? Por lo pronto, (11+?) haría que se pruebe con \[ n-1 \] capturas (en el caso del 5, capturó "11", "111", "1111" y "11111" es decir 4), y fijada cada una de esas posibles capturas, la backereference \1+ hace que se pruebe con esa secuencia repetida una cantidad variable de veces (que depende de la longitud de \1 disminuyendo a medida que la longitud de \1 es mayor), pero que se puede acotar por \[ n \]. En el peor caso diría que es \[ O(n^2) \].

El clásico algoritmo es \[ O(\sqrt{n}) \].
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

29 Octubre, 2015, 17:00
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3.386
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Un benchmark comparando con el otro algoritmo:

$ time perl -le 'print for 1..1e4' | perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ es primo"'
real    0m9.956s
user    0m9.768s
sys     0m0.113s


$ time perl -le 'print for 1..1e4' | perl -lne '
next if $_<=1;
($primo, $sq) = (1, sqrt($_));
foreach $div (2..$sq) {
  --$primo, last if !($_%$div)
}
print "$_ es primo" if $primo'
real    0m0.037s
user    0m0.028s
sys     0m0.009s


Ya con los primos menores a 10000 empieza a notarse la diferencia.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print