Foro - Perl en Español

por **slopal** » 2006-02-28 11:20 @513

Como ya os he dicho en otro mensaje, tengo problemas de duración de tiempo en mi script. Mirando, mirando, he visto que la parte que más tiempo tarda (¡también es la que hace más cosas!) es esta. Es el algoritmo Horspool y lo he traducido directamente del C. Pero seguro que en Perl se puede optimizar con muchos truquillos de estos que sabéis vosotros

:

Programa Original C

Sintáxis: [ Descargar ] [ Ocultar ]

Using c Syntax Highlighting

void HORSPOOL(char *tupla, int mida_tupla, char *cadena, int mida_cadena) {
   int j, bmBc[ASIZE];
   char c;
 
   /* Preprocessing */
   preBmBc(tupla, mida_tupla, bmBc);
 
   /* Searching */
   j = 0;
   while (j <= mida_cadena - mida_tupla) {
      c = cadena[j + mida_tupla - 1];
      if (tupla[mida_tupla - 1] == c && memcmp(tupla, cadena + j, mida_tupla - 1) == 0)
         OUTPUT(j);
      j += bmBc[c];
   }
}
 
void preBmBc(char *tupla, int mida_tupla, int bmBc[]) {
   int i;
 
   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = mida_tupla;
   for (i = 0; i < mida_tupla - 1; ++i)
      bmBc[tupla[i]] = mida_tupla - i - 1;
}
 
Coloreado en 0.003 segundos,  usando GeSHi 1.0.8.4

Mi Horspool en "mi" Perl...

Sintáxis: [ Descargar ] [ Ocultar ]

Using perl Syntax Highlighting

my ( $j, $c, $k );
 
#### Preprocessat
 
preBmBc();
#### Cerca
 
$j = 0;
 
while ( $j <= $mida_cadena - $mida_tupla ) {
    $c = $cadena[ $j + $mida_tupla - 1 ];
    $k = $j + $mida_tupla - 1;
 
    my $part_a_comparar = join( '', @cadena[ $j .. $k ] );
    if ( ( $tupla[ $mida_tupla - 1 ] eq $c ) and ( $part_a_comparar eq $tupla ) ) {
        $trobada       = 1;
        $freq_trobades = $freq_trobades + 1;    # augmentem la freqüència
        push( @posicions, $j );
    }
    $j = $j + $bmbc{$c};
}
 
sub preBmBc()                          #ordre ==> a c g t
{
    %bmbc = (
        'A' => $mida_tupla,
        'C' => $mida_tupla,
        'G' => $mida_tupla,
        'T' => $mida_tupla,
    );
 
    for ( my $i = 0; $i < $mida_tupla - 1; ++$i ) {
        $bmbc{ $tupla[$i] } = $mida_tupla - $i - 1;
    }
}                                      # sub preBmBc
Coloreado en 0.004 segundos,  usando GeSHi 1.0.8.4

El algoritmo Boyer-Moore-Horspool se encuentra descrito en el libro Mastering Algorithms with Perl (http://www.azet.org/pub/ebooks/O'Reilly ... tering.pdf), páginas 373-376.

Bueno, más bien sólo está descrito el Boyer-Moore, y luego comentan la reducción al Hospool.

En cuanto a trucos, sí que se pueden poner algunos, como por ejemplo, reordenar las condiciones dentro de los if para que se evalúen las condiciones más ligeras (como por ejemplo, poner $part_a_comparar eq $tupla antes de ($tupla[$mida_tupla -1] eq $c)).

Lo que he visto es muy parecido al algoritmo original, pero distinto del que aparece en el libro.

De todas formas... depende de lo grande que sea el lugar donde estás buscando. Si es muy, muy grande, yo lo haría en C, dentro del código Perl, con el módulo Inline::C. Yo lo hice una vez cuando necesitaba velocidad y me fue muy bien. Lo más difícil fue ver cómo pasar los argumentos a la parte de C, pero si son variables sencillas, igual de sencillo es pasarlas.

por **slopal** » 2006-03-02 13:10 @590

Gracias, ¡me miraré todo esto!

Si no tengo problemas para acceder al módulo éste de C..... Pues también lo intentaré (ojalá).

por **slopal** » 2006-03-15 15:06 @671

Por no crear otro hilo lo pongo aquí. Tengo esta parte de código, no sé si lo estoy haciendo bien, es una de las partes que más tarde, y en parte es normal porque los ficheros pueden ser "grandes"... pero por si acaso. No tengo muy claro qué valor tendría que poner para que fuera óptimo, en el campo del número del read (¿¿¿¿ qué he puesto ???? Para que quede más claro?)

Sintáxis: [ Descargar ] [ Ocultar ]

Using perl Syntax Highlighting

while ( my $bytesread = read( $Input{'cadena'}, my $buffer, ??
        ? ??
                ? ) ) {
            print OUTFILE $buffer;
    }
 
    close(OUTFILE);
Coloreado en 0.001 segundos,  usando GeSHi 1.0.8.4

Si sabéis otra manera mucho más mejor

Acepto todo tipo de comentarios. thanx!

por **explorer** » 2006-03-15 18:35 @816

Una opción sería... no leer el fichero a memoria...

Me explico... en el caso de que los ficheros que tengas que leer sean muy grandes y estés usando Linux (o UNIX), lo más cómodo es usar la función del sistema 'mmap', cuya función es hacer 'mapear' el fichero a memoria, como si se estuviera leyendo, pero lo bueno es que todas las operaciones de lectura/escritura y gestión de direcciones de memoria las realiza el sistema operativo (una tarea muy rápida).

En Perl v5.8.8. está la opción de usar PerlIO con un 'layer' mmap. Sería algo así como esto:

open($bases, "<:raw:mmap", "raton_almizclero_cromosoma_2.txt");

y a partir de ese momento, hacer seek() para posicionarte dentro del fichero en la posición que quieras leer, y luego, read().

Hay dos opciones más. Con el módulo Sys::Mmap se puede mapear todo un fichero a una variable escalar:

Sintáxis: [ Descargar ] [ Ocultar ]

Using perl Syntax Highlighting

use Sys::Mmap;
 
# Aquí abres el fichero y el FILEHANDLE es el file handle del fichero. Luego lo mapeas con
mmap($foo, 0, PROT_READ, MAP_SHARED, FILEHANDLE) or die "mmap: $!";
 
# Trabajar aquí con $foo, por ejemplo substr( )
munmap($foo) or die "munmap: $!";
close FILEHANDLE;
Coloreado en 0.001 segundos,  usando GeSHi 1.0.8.4

Otra forma:

Sintáxis: [ Descargar ] [ Ocultar ]

Using perl Syntax Highlighting

use Sys::Mmap;
 
new Mmap $cadena, 0, 'humano_bases_8333.txt' or die $!;
# Trabajar con el escalar $cadena como si fuera cualquier otra cadena.
Coloreado en 0.001 segundos,  usando GeSHi 1.0.8.4

Y otra opción interesante es Tie::MmapArray, que mapea un fichero a un array en vez de a un escalar.

Si no tienes más remedio que usar el bucle que has escrito antes, el tamaño a indicar en ????? debería ser igual o múltiplo al tamaño del búfer que el sistema operativo usa para el intercambio de datos entre el disco y la memoria. En algunos sistemas pueden ser 4 Kb, en otros 32 Kb, etc... Puedes realizar experimentos cambiando el tamaño y comprobar con la función timer si ha tardado más o menos. Debes ejecutar el mismo bucle con el mismo tamaño dos o tres veces para tener una confirmación del tiempo que tarda.

En este tema puede pasar una cosa muy curiosa... puede que con un tamaño de 16 Kb vaya más rápido que con uno de 32 Kb, pero menos que uno de 8 Kb.

Foro - Perl en Español

Optimizar esta traducción

Optimizar esta traducción

Publicidad

Re: Optimizar esta traducción

Re: Optimizar esta traducción

¿Quién está conectado?