• Publicidad

Segmentar una cadena

Perl aplicado a la bioinformática

Segmentar una cadena

Notapor abhortas » 2017-04-19 11:59 @541

Hola, amigos. A ver si alguien me puede ayudar.

Estoy intentando segmentar una cadena en fragmentos más pequeños para imprimirlos en columna. Es decir, tengo:

$cadena="XXXXXAAAAABBBBBCCCCC"

y quiero poder imprimir:

XXXXX
AAAAA
BBBBB
CCCCC

Es decir, meter un salto de línea cada x caracteres (en este ejemplo, 5 caracteres).

Preparé este pequeño código que resuelve el problema:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. while(length($cadena) > x){
  2.         $sec=substr($cadena,0,x);
  3.         print "$sec\n";
  4.         $cadena=substr($cadena,x);
  5. }
  6. print "$cadena\n";
Coloreado en 0.006 segundos, usando GeSHi 1.0.8.4

donde "x" es la longitud deseada.

El problema es que las longitudes de las cadenas en cuestión son de decenas de millones de caracteres, por lo que el código anterior se vuelve extremadamente lento.

¿Alguna idea para optimizar lo que quiero hacer y que se ejecute en un tiempo razonable? Le estoy dando vueltas pero no se me ocurre cómo hacerlo.

Si alguien puede echarme una mano estaría enormemente agradecido.

Saludos.
abhortas
Perlero nuevo
Perlero nuevo
 
Mensajes: 7
Registrado: 2015-10-23 05:57 @290

Publicidad

Re: Segmentar una cadena

Notapor explorer » 2017-04-19 12:42 @571

Bienvenido a los foros de Perl en Español, abhortas.

Esta solución, usando expresiones regulares, tarda 1 segundo por cada millón de caracteres (en mi ordenador):
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. my $cadena = "XXXXXAAAAABBBBBCCCCC" x 1E7;      # generamos decenas de millones de copias
  2.  
  3. my $antes = time;
  4.  
  5. my @x = $x =~ /\G.{5}/g;                        # partimos la $cadena en bloques de 5 caracteres
  6.  
  7. $x = join("\n" => @x) . "\n";                   # unimos los bloques, usando "\n" como delimitador (y uno más al final)
  8.  
  9. say time-$antes;                                # ver cuántos segundos ha tardado
Coloreado en 0.006 segundos, usando GeSHi 1.0.8.4

Lo malo es que solo funciona si la longitud de la cadena es múltiplo de los trozos a cortar. Se podría complicar un poco más la expr. reg., pero eso alargaría el proceso.

Con un poco más de información, se podría mirar otra solución.

Esta otra solución tarda casi la mitad:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. my $x = "XXXXXAAAAABBBBBCCCCC" x 1E7;
  2. my $antes = time;
  3.  
  4. my $p = 0;                                      # índice dentro de la cadena
  5. my $l = length $x;
  6. my @x;
  7. while ($p < $l) {
  8.     push @x, substr $x, $p, 5;                  # sacamos el bloque y lo guardamos en @x
  9.     $p += 5;
  10. }
  11. $x = join("\n" => @x) . "\n";                   # reconstrucción
  12.  
  13. say time-$antes;
Coloreado en 0.006 segundos, usando GeSHi 1.0.8.4

Lo importante, cuando estamos manejando grandes volúmenes de datos, es... no "moverlos" mucho. En tu código, estás modificando la cadena en cada ciclo, así que si es muy grande, es normal que tarde mucho.
JF^D Perl Programming Language
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14102
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Segmentar una cadena

Notapor abhortas » 2017-04-20 08:49 @409

Gracias, explorer.

Tengo algo de soltura con el lenguaje Perl, pero aún me cuesta la utilización de las expresiones regulares. Había pensado en utilizar la función split(), en una solución muy similar a la que utilizas en la expresión regular, pero no sabía cómo indicarle a la función que cortase cada x elementos. Mediante esa expresión regular, estaría solucionado.

Lo que no entiendo es por qué debe ser múltiplo de la longitud a cortar. De todas formas eso se solucionaría chequeando la longitud de la cadena al inicio, y de no ser múltiplo de x, añadir elementos hasta completar, que después eliminaríamos.

Realmente, lo que estoy manejando son secuencias de cromosomas que, para realizar unas transformaciones y cortes en su día creé un archivo con cada cromosoma en una línea. Ahora quiero realizar en el proceso inverso, crear un archivo que sea mucho más legible, para abrir con un bloc de notas, por ejemplo.

Muchas gracias por tu ayuda.
abhortas
Perlero nuevo
Perlero nuevo
 
Mensajes: 7
Registrado: 2015-10-23 05:57 @290

Re: Segmentar una cadena

Notapor explorer » 2017-04-20 09:54 @454

La multiplicidad de la longitud de la cadena la exige la propia exp. reg. Si no es múltiplo, descartará el último bloque de la cadena.

split() se utiliza para partir una cadena según un determinado delimitador. En tu caso, no hay delimitador. Bueno, se podría usar una expresión regular parecida a la mostrada, usándolo con un grupo de captura. El resultado sería también la cadena partida, pero habría que desechar los grupos vacíos:
Sintáxis: [ Descargar ] [ Ocultar ]
Using bash Syntax Highlighting
  1. perl -E '$x = "XXXXXAAAAABBBBBCCCCC" x 1E7; $ahora = time;  $y = join "\n" => grep { length > 0 } split /(.{5})/, $x;  say time-$ahora'
Coloreado en 0.007 segundos, usando GeSHi 1.0.8.4

Esta solución me tarda 67 segundos, tres veces más que la segunda solución más rápida que te di antes.

A propósito, ¿por qué has preferido la solución de la expresión regular si es más lenta que la siguiente solución, la del substr()?
JF^D Perl Programming Language
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14102
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Segmentar una cadena

Notapor abhortas » 2017-04-20 11:09 @506

Finalmente he implementado la segunda opción que me indicas.

En el mensaje anterior comentaba la primera porque me tiré directa a ella, pero después revisando la segunda opción, comprobé que es más rápida. De hecho, es una solución muy lógica y sencilla, y sin tirar de expresiones regulares, que me vuelven la cabeza loca :lol:

Muchas gracias de nuevo.
abhortas
Perlero nuevo
Perlero nuevo
 
Mensajes: 7
Registrado: 2015-10-23 05:57 @290


Volver a Bioinformática

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 0 invitados