• Publicidad

script consume mucha CPU pero poca memoria

¿Apenas comienzas con Perl? En este foro podrás encontrar y hacer preguntas básicas de Perl con respuestas aptas a tu nivel.

Re: script consume mucha CPU pero poca memoria

Notapor explorer » 2009-09-30 18:54 @829

Bueno, vamos a empezar...

Primero: los programadores de Perl no escribimos scripts. Hacemos programas :)

Segundo... el programa en sí :)

  • En vez de un declare() y un execute(), usaría un selectall_arrayref() (no probado):
    Sintáxis: [ Descargar ] [ Ocultar ]
    Using perl Syntax Highlighting
    my @array = @{ $dbh->selectall_arrayref("select calle FROM dir where completo = ''  GROUP BY direc ORDER BY direc") };
    Coloreado en 0.002 segundos, usando GeSHi 1.0.8.4

    Lo mismo para @array2. El objetivo es tenerlo todo en arrays, que facilitan la nomenclatura posterior, aparte de que Perl se ahorra varios cálculos a la hora de hacer desreferencias, como cuando queremos averiguar el número de elementos del array.
  • Todos los if() hacen lo mismo, así que se pueden simplificar en uno solo.

Quedaría algo así (no probado):

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
my @array1 = @{ $dbh->selectall_arrayref("select calle FROM dir where completo = ''  GROUP BY direc ORDER BY direc") };
my @array2 = @{ $dbh->selectall_arrayref("select UCASE(calle), compl FROM c1 GROUP BY calle ORDER BY calle") };

$dbh->disconnect();

for my $linea1 ( @array1 ) {    ### Normalizando [|||        ] % Completado \n
for my $linea2 ( @array2 ) {
    my $smlty = String::Trigram::compare( $linea1->[0], $linea2->[0], minSim => 0.5, ngram => 7, );

    if ( $smlty >= 0.5 ) {
        printf "[%s]\t=>\t[%s][%s] %.2f\n", $linea1->[0], $linea2->[0], $linea2->[1], 100*$smlty;
    }
}}
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4


Ahora quedaría la parte de decidir qué hacer cuando los casos de coincidencia. Primero habría que decidir cuándo hay una coincidencia plena. Si suponemos que es cuando la similitud es superior al 90%, entonces podemos incluir una línea al final del bucle más interior con esto:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
last if $smlty > 0.9;
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4

Así, saltamos a probar la siguiente calle del bucle más exterior.

Lo interesante es el poder sacar elementos de los array a medida de que vamos encontrando coincidencias.

Pero... no es tan sencillo. O bueno... es sencillo pero nada recomendable.

Quiero decir que se podría poner una instrucción splice() en el bucle más interior para extraer el elemento que nos interesa (habría que cambiar la forma de recorrer los arrays, pasando de elementos a índices de elementos), y Perl reduciría el tamaño del array.

El problema es que, en la documentación, aconsejan no hacer nada de esto. Podría ser una operación no bien soportada en futuras versiones de Perl.

Hay varias soluciones: una de ellas sería guardar los índices de las calles encontradas en los arrays. Y luego, indefinir esa posición en el segundo array, para que el bucle más interno vaya más rápido.

Algo así (no probado):
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
my @array1 = @{ $dbh->selectall_arrayref("select calle FROM dir where completo = ''  GROUP BY direc ORDER BY direc") };
my @array2 = @{ $dbh->selectall_arrayref("select UCASE(calle), compl FROM c1 GROUP BY calle ORDER BY calle") };

$dbh->disconnect();

my @calles_encontradas;

for my $i ( 0 .. $#array1 ) {    ### Normalizando [|||        ] % Completado \n
for my $j ( 0 .. $#array2 ) {
    next if !$array2[$j];       # Saltamos si ya fue encontrada

    my $smlty = String::Trigram::compare( $array1[$i][0], $array2[$j][0], minSim => 0.5, ngram => 7, );

    if ( $smlty >= 0.5 ) {
        printf "[%s]\t=>\t[%s][%s] %.2f\n", $array1[$i][0], $array2[$j][0], $array2[$j][1], 100*$smlty;
        if ( $smlty >= 0.9 ) {
            push @calles_encontradas, [$i, $j];
            $array2[$j] = undef;
        }
    }
}}
 
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4

Al final tenemos un array, @calles encontradas, que contiene los índices dentro de los arrays, de las calles que más coinciden.

Naturalmente, estamos destruyendo la información del segundo array, así que si queremos saber qué valores eran, tendremos que hacer otra consulta a la base de datos. O crear, antes del bucle, una copia de ese array en uno nuevo. Para esto último, no vale con hacer un '='. Como estos arrays son estructuras complejas (array de array), deberás usar un módulo, como por ejemplo Clone, para hacer esa copia. O crear un array que contenga referencias a los elementos del segundo array. En fin, hay varias soluciones. La idea es jugar con la información que tenemos, pero que nos permite ahorrar el máximo posible de tiempo haciendo el mínimo de comparaciones, asignaciones, y ciclos. Y lo dicho para el segundo array se puede extender al primero, si estamos seguros de que, si dos calles coinciden en ambos arrays, los podemos sacar porque no habrá otra calle del segundo array que coincide con alguna del primero.
Última edición por explorer el 2009-10-01 14:58 @665, editado 1 vez en total
Razón: Typo
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Publicidad

Re: script consume mucha CPU pero poca memoria

Notapor preiddy » 2009-10-01 14:29 @645

Es cierto, tengo esa muy mala costumbre de llamar todo script. Un viejo hábito heredado del HTML y Javascript. jajaja.

Imagino que esto:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
for my $i ( 0 .. #array1 ) {    ### Normalizando [|||        ] % Completado \n
for my $j ( 0 .. #array2 ) {
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4

debería ser:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
for my $i ( 0 .. $array1 ) {    ### Normalizando [|||        ] % Completado \n
for my $j ( 0 .. $array2 ) {
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4


¿no?

Me temo que estoy un poco espeso y no entiendo y lo del Clone.

¡De verdad que muchas gracias!
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Re: script consume mucha CPU pero poca memoria

Notapor explorer » 2009-10-01 15:09 @673

Pues sí que hay un fallo, pero la solución no es la que pones :)

He reeditado el código y ya lo he dejado bien. Se trata de $#array1, que devuelve el índice del último elemento del array.

Lo del Clone es una posibilidad más. Es un módulo que se usa para copiar estructuras de datos complejas.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: script consume mucha CPU pero poca memoria

Notapor preiddy » 2009-10-02 02:45 @156

Ya lo he probado, pero no quita el nombre cuando coincide, se siguen evaluando del 100% hasta llegar al 50%.

Lo que estoy haciendo como "primera fase" de identificación es ejecutar una instrucción SQL que casa las del 100%.

Luego aplico este programa para las variantes.

El test lo realicé con una tabla de 700 registros contra otra de 8000, de las cuales esas 700 tienen coincidencias del 100%. El tiempo de trabajo del programa fue de 35 min.

Si disminuyo el nivel de coincidencia se repiten por cada registro, no hace el next.
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Re: script consume mucha CPU pero poca memoria

Notapor explorer » 2009-10-02 08:17 @386

Vamos a ver... eso no puede ser... media hora para solo 5.600.000 comparaciones... es demasiado tiempo.

He hecho un programa que me genera 8000 cadenas aleatorias, entre 20 y 80 caracteres. De ellas me extraigo 700:

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
my @letras = ('a' .. 'z', ' ', 0 .. 9);

my @array1;
for (1..8000) {
    my $calle = join '', map{ $letras[rand @letras] } 1 .. 20 + rand 60;
    push @array1, $calle;
}

my @array2;
for (1..700) {
    push @array2, $array1[rand @array1];
}
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4


Haciendo el doble bucle propuesto:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
for my $i ( 0 .. $#array1 ) {    ### Normalizando [|||             ] % Completado \n
for my $j ( 0 .. $#array2 ) {
    next if !$array2[$j];       # Saltamos si ya fue encontrada

    my $smlty = String::Trigram::compare( $array1[$i], $array2[$j], minSim => 0.5, ngram => 7);

        if ( $smlty >= 0.9 ) {
            push @calles_encontradas, [$i, $j];
            $array2[$j] = undef;
        }
}}

use Data::Dumper;
print Dumper \@calles_encontradas;
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4

me salen tiempos de 15 minutos. El módulo Smart::Comments apenas aporta retraso. El módulo informa que tardará 29 minutos, pero luego, con la ayuda del next, va acelerando.

Sigue siendo demasiado tiempo.

Entonces, es cuando debemos volver a leer la documentación... porque el culpable es String::Trigram, naturalmente.

Leyendo con cuidado, vemos que hemos elegido la peor solución que nos ofrece el módulo:
* no le damos una base de cadenas de caracteres para entrenar la red de ngramas.
* usamos la función compare(), que es lo más lento del módulo, ya que crea un objeto nuevo en cada comparación.

Respetemos la decisión de preiddy de elegir que el tamaño de los ngramas sean de 7 caracteres.

Solo queda reescribir el programa para hacer las comparaciones según lo recomienda el módulo:

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use diagnostics;
  5.  
  6. use String::Trigram;
  7.  
  8. my @letras = ('a' .. 'z', ' ', 0 .. 9);
  9.  
  10. my @array1;
  11. for (1..8000) {
  12.     my $calle = join '', map{ $letras[rand @letras] } 1 .. 20 + rand 40;
  13.     push @array1, $calle;
  14. }
  15.  
  16. my @array2;
  17. for (1..700) {
  18.     push @array2, $array1[rand @array1];
  19. }
  20.  
  21. $|++;
  22. print 'Alimentando la base... ';
  23. my $trig = String::Trigram->new(cmpBase => \@array1, minSim => 0.5, ngram => 7);
  24. print "Ok\n";
  25. #print 'Alimentando la base (y 2)... ';
  26. #$trig->extendBase(\@array2);
  27. #print "Ok\n";
  28.  
  29. my @calles_encontradas;
  30. my %resultados;
  31.  
  32. for my $i ( 0 .. $#array2 ) {
  33.  
  34.     my $numOfSimStrings = $trig->getSimilarStrings($array2[$i], \%resultados);
  35.  
  36.     print "$i: Encontradas $numOfSimStrings cadenas similares.\n";
  37.  
  38.     foreach my $calle (keys %resultados) {
  39.         printf "%s tiene una similitud de %.02f%%\n", calle, $resultados{$calle} * 100;
  40.     }
  41. }
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4


Tiempo: 8 segundos. 6 segundos si quitamos los print().

Eso ya me gusta más. :)

Incluso si descomentamos la línea 26, para agregar en la base de conocimiento las cadenas de @array2, la diferencia es pequeña (no las he agregado porque son copias de @array1).

Ahora solo queda jugar con el parámetro minSim y ngram para filtrar aún más las coincidencias.
Última edición por explorer el 2009-10-05 01:53 @120, editado 3 veces en total
Razón: Typo. Error en el segundo código
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: script consume mucha CPU pero poca memoria

Notapor preiddy » 2009-10-02 10:39 @485

Eso es lo malo de "heredar" código de los compañeros de trabajo, jajajajaa.

El programa es de otro compañero, me lo pasó para que le echara un ojo y lo menos que hice fue leer la documentación. :oops:

En una oportunidad leí que para los nombres en español los ngramas funcionan mejor con 7. El argumento era muy razonable, jajaja.

De nuevos muchas gracias y en cuanto lo pueda probar te comento los resultados.
preiddy
Perlero nuevo
Perlero nuevo
 
Mensajes: 70
Registrado: 2006-03-29 05:43 @280
Ubicación: Madrid, España

Anterior

Volver a Básico

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado

cron