06/12/2019, 09:34:14 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Perl golf, primalidad y expresiones regulares  (Leído 1162 veces)
0 Usuarios y 1 Visitante están viendo este tema.
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.353


Ver Perfil
« : 29/10/2015, 02:38:05 pm »

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  :sorprendido:.

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  :risa:).

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.

Spoiler: Explicación (click para mostrar u ocultar)

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
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #1 : 29/10/2015, 02:43:01 pm »

¡Es muy buena la regexp de primos!

¿Alguna estimación del costo computacional?  :malvado:
En línea

pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.353


Ver Perfil
« Respuesta #2 : 29/10/2015, 03:45:34 pm »

¡Es muy buena la regexp de primos!

Sí  :sonrisa:

¿Alguna estimación del costo computacional?  :malvado:

Bueno, dada la entrada [texx]n[/texx], en el peor caso, o sea, si [texx]n[/texx] es NO primo, ¿cuántas iteraciones efectuaría el motor de expresiones regulares? Por lo pronto, (11+?) haría que se pruebe con [texx]n-1[/texx] 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 [texx]n[/texx]. En el peor caso diría que es [texx]O(n^2)[/texx].

El clásico algoritmo es [texx]O(\sqrt{n})[/texx].
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.353


Ver Perfil
« Respuesta #3 : 29/10/2015, 05:00:28 pm »

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.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!