Mar Nov 20, 2007 4:09 pm
|
 |
rfm
Perlero Nuevo

|
Registrado: 09 Nov 2007
Mensajes: 37
|
|
| Búsqueda binaria en un fichero |
|
|
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 |
|
|
|
Mar Nov 20, 2007 5:45 pm
|
 |
explorer
Moderador

|
Registrado: 24 Jul 2005
Mensajes: 4092
Ubicación: Valladolid, España
|
|
|
|
|
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 |
|

Mie Nov 21, 2007 3:27 am
|
 |
Jenda
Perlero Frecuente

|
Registrado: 29 Oct 2007
Mensajes: 104
Ubicación: Praga, Republica Checa
|
|
| Re: Quicksort de un fichero |
|
|
| 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 |
|

Mie Nov 21, 2007 5:29 am
|
 |
rfm
Perlero Nuevo

|
Registrado: 09 Nov 2007
Mensajes: 37
|
|
|
|
|
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. |
|
Mie Nov 21, 2007 7:18 am
|
 |
explorer
Moderador

|
Registrado: 24 Jul 2005
Mensajes: 4092
Ubicación: Valladolid, España
|
|
|
|
|
| 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. |
|
Mie Nov 21, 2007 7:44 am
|
 |
explorer
Moderador

|
Registrado: 24 Jul 2005
Mensajes: 4092
Ubicación: Valladolid, España
|
|
|
|
|
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. |
|
Jue Nov 22, 2007 12:51 pm
|
 |
Norther
Perlero Frecuente

|
Registrado: 24 Jul 2007
Mensajes: 117
Ubicación: Asturias
|
|
|
|
|
También es casualidad que ayer en clase hicimos búsqueda binaria y dicotómica en C  |
|
Powered by phpBB © 2001, 2005 phpBB Group
|