 Mar Feb 28, 2006 10:20 am
|
 |
slopal
Perlero Nuevo
|
Registrado: 23 Nov 2005
Mensajes: 78
|
|
| Optimizar esta traducción... |
 |
|
Como ya os he dicho en otro post, tengo problemas de duración de tiempo en mi script. Mirando, mirando, he visto que la parte que más tiempo tarda (tb es la q hace mas cosas!) es esta. Es el algorismo horspool y lo he traducido directamente del C. Pero seguro que en Perl se puede optimizar con muchos truquillos de estos que sabeis vosotros  :
Programa Original C
| Código: |
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];
}
}
|
| Código: |
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;
}
|
-----------------
mi horspool en "mi" Perl...
| Código: |
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};
}
|
| Código: |
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
|
|
|
|
|
|
Mie Mar 01, 2006 12:45 pm
|
|
explorer
Moderador
|
Registrado: 24 Jul 2005
Mensajes: 4082
Ubicación: Valladolid, España
|
|
|
|
|
El algoritmo Boyer-Moore-Horspool se encuentra descrito en el libro Mastering Algorithms with Perl (http://www.azet.org/pub/ebooks/O'Reilly%20-%20Perl%20-%20Algorithms%20-%20Mastering.pdf), páginas 373-376. Bueno, más bién 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 evaluen 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 fué muy bien. Lo más difícil fué ver cómo pasar los argumentos a la parte de C, pero si son variables sencillas, igual de sencillo es pasarlas. |
|
|
Jue Mar 02, 2006 12:10 pm
|
|
slopal
Perlero Nuevo
|
Registrado: 23 Nov 2005
Mensajes: 78
|
|
|
|
|
Gracias me mirare todo esto!
Si no tengo problemas para acceder al modulo este de C..... Pues también lo intentare (ojala). |
|
|
Mie Mar 15, 2006 2:06 pm
|
|
slopal
Perlero Nuevo
|
Registrado: 23 Nov 2005
Mensajes: 78
|
|
|
|
|
por no crear otro hilo lo pongo aqui. Tengo esta parte de código, no se si lo estoy haciendo bien, es una de las partes que más tarde, y en parte es normal pq los ficheros pueden ser "grandes"... pero por si a caso. No tengo muy claro que valor tendría que poner para que fuera óptimo, en el campo dl número del read (que he puesto ???? para que quede mas claro?:
| Código: |
while (my $bytesread = read($Input{'cadena'}, my $buffer, ??????))
{
print OUTFILE $buffer;
}
close (OUTFILE); |
si sabeis otra manera mucho más mejor  acepto todo tipo d comentarios. thanx! |
|
|
Mie Mar 15, 2006 5:35 pm
|
|
explorer
Moderador
|
Registrado: 24 Jul 2005
Mensajes: 4082
Ubicación: Valladolid, España
|
|
|
|
|
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 5.8.8. está la opción de usar PerlIO con un 'layer' mmap. Sería algo así como esto:
| Código: |
| 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:
| Código: |
use Sys::Mmap;
# Aqui 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; |
Otra forma:
| Código: |
use Sys::Mmap;
new Mmap $cadena, 0, 'humano_bases_8333.txt' or die $!;
# Trabajar con el escalar $cadena como si fuera cualquier otra cadena. |
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 buffer que el sistema operativo usa para el intercambio de datos entre el disco y la memoria. En algunos sistemas pueden ser 4KB, en otros 32Kb, 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 16K vaya más rápido que con uno de 32K, pero menos que uno de 8K. |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
