Perl en Español

  1. Home
  2. Tutoriales
  3. Foro
  4. Artículos
  5. Donativos
  6. Publicidad
 

Búsqueda binaria en un fichero

 
Publicar nuevo tema   Responder al tema    Foros de discusión -> Intermedio
Mensaje Mar Nov 20, 2007 4:09 pm
rfm
Perlero Nuevo
Perlero Nuevo
Registrado: 09 Nov 2007
Mensajes: 37
Búsqueda binaria en un fichero Responder citando

Hola todos.

En mi actual proyecto accedo secuencialmente a un fichero de log en busca de una fecha en concreto y me preguntaba si no es más eficiente una búsqueda por algún método como quicksort, es decir ir a la mitad del fichero, comparar, si es mayor, ir a la mitad de la mitad anterior, etc...

¿Hay alguna función ya implementada en Perl o hay que implementar el código?

Muchas gracias y un saludo
Mensaje Mar Nov 20, 2007 5:45 pm
explorer
Moderador
Moderador
Registrado: 24 Jul 2005
Mensajes: 4092
Ubicación: Valladolid, España
Responder citando

Humm... File::SortedSeek. Y seguro que debe haber alguno más, si el fichero de log es de un formato conocido...

Y si el fichero de log cabe en memoria, sería fácil hacer una búsqueda binaria. Hay otro módulo con la búsqueda binaria ya implantada: Search::Binary.

Ultima edición por explorer el Mie Nov 21, 2007 7:31 am, editado 1 vez
Mensaje Mie Nov 21, 2007 3:27 am
Jenda
Perlero Frecuente
Perlero Frecuente
Registrado: 29 Oct 2007
Mensajes: 104
Ubicación: Praga, Republica Checa
Re: Quicksort de un fichero Responder citando

rfm escribió:
En mi actual proyecto accedo secuencialmente a un fichero de log en busca de una fecha en concreto y me preguntaba si no es más eficiente una búsqueda por algún método como quicksort, es decir ir a la mitad del fichero, comparar, si es mayor, ir a la mitad de la mitad anterior, etc...


No es quicksort, es la búsqueda binaria. Podrías hacerlo, pero no creo que te vaya a ayudar mucho. Ora vas a tener que buscar los fines y principios de las líneas cada vez, ora preparar un array con los posiciones de líneas en el fichero. Lo primero va a complicar el código mucho, lo segundo sólo ayuda si buscas más fechas.

Si buscas más fechas puedes recordar las líneas o las posiciones y hacer algo así:

Perl:
#!/usr/bin/perl
use strict;
use warnings;

use constant FECHA => 3; # en que posición de cada línea es la fecha

sub prepara_datos {
  my ($fichero) = @_;
  my %fechas;
  open my $IN, '<', $fichero or die "No se puede abrir '$fichero': $^E\n";
  my $posicion=0;
  while (<$IN>) {
    chomp;
    my @columns = split /\t/, $_;
    $fechas{$columns[FECHA]} = $posicion;
    $posicion = tell($IN);
  }
  return ( $IN, \%fechas);
}

sub busca_fecha {
  my ($FICHERO, $fechas, $fecha) = @_;
  if (exists $fechas->{$fecha}) {
    seek($FICHERO, $fechas->{$fecha}, 0);
    my $linea = <$FICHERO>;
    chomp($linea);
    my @columns = split /\t/, $linea;
    return \@columns;
  } else {
    return; # la fecha no esta en el fichero
  }
}

#...
my ($FICHERO, $fechas) = prepara_datos( $fichero);

foreach my $fecha (@fechas_para_buscar) {
  my $datos = busca_fecha( $FICHERO, $fechas, $fecha);
  if (! $datos) {
   print "No he encontrado $fecha!\n";
  } else {
     # haga algo con @$datos
  }
}


Si el fichero es demasiado grande y no puedes guardar todas las fechas y posiciones en un array, puedes usar BerkeleyDB.pm o AnyDBM_File.pm módulo para poner los datos al disk.

Y si quieres buscar usando otros datos o encontrar todos los datos entre dos fechas o algo similar, puedes importar todos los datos en una base de datos (por ejemplo con DBD::SQLite - es una base de datos en un módulo, no necesitas instalar nada más).

Jenda
Mensaje Mie Nov 21, 2007 5:29 am
rfm
Perlero Nuevo
Perlero Nuevo
Registrado: 09 Nov 2007
Mensajes: 37
Responder citando

Lo que quiero hacer realmente es posicionarme en la primera línea que contenga una fecha en concreto y a raíz de ahí parsear el resto del fichero de log (esto último lo tengo ya implementado).

Entonces la cuestión es que no me tarde tanto en comprobar línea a línea si coincide o no con la fecha que le paso.

¿Alguna otra sugerencia?

Miraré lo del sqlite.

Muchas gracias a los dos.
Mensaje Mie Nov 21, 2007 7:18 am
explorer
Moderador
Moderador
Registrado: 24 Jul 2005
Mensajes: 4092
Ubicación: Valladolid, España
Responder citando

Se podría hacer una búsqueda binaria moviendo el puntero de lectura del fichero, y luego hacer una lectura de una línea completa para ver la fecha que tiene esa línea, y seguir buscando, hasta encontrarlo.
Mensaje Mie Nov 21, 2007 7:44 am
explorer
Moderador
Moderador
Registrado: 24 Jul 2005
Mensajes: 4092
Ubicación: Valladolid, España
Responder citando

Acabo de darme cuenta de que lo que he dicho en el último mensaje, lo hace el módulo que te comenté antes: File::SortedSeek.

He mirado el código fuente y hace exactamente eso.
Mensaje Jue Nov 22, 2007 12:51 pm
Norther
Perlero Frecuente
Perlero Frecuente
Registrado: 24 Jul 2007
Mensajes: 117
Ubicación: Asturias
Responder citando

También es casualidad que ayer en clase hicimos búsqueda binaria y dicotómica en C Razz
Publicar nuevo tema   Responder al tema    Foros de discusión -> Intermedio Todas las horas son GMT - 6 Horas
Página 1 de 1



Powered by phpBB © 2001, 2005 phpBB Group