Efectividad de Busqueda Binaria dentro de un archivo

Article View: chile.comp.programacion

Article #1021

Back to chile.comp.programacion Previous Next

#1021

From: Alberto Hormazabal
Date: Thu, 17 May 2007 17:17

29 lines
1859 bytes

Necesito hacer una funcion que busque una linea especifica dentro de un
archivo en base a un id, el archivo es generalmente de gran tama�o.

Cada linea tiene un id correlativo, el cual aumenta de tama�o en cada
fila, lo que me permitiria implementar una busqueda binaria para ubicar
una linea especifica dentro del archivo...


Ahora, leyendo por ahi y por aca, surge la idea de que tal vez no es lo
mas eficiente implementar esto con busqueda binaria, ya que su
comportamiento aleatorio generaria mas busquedas en el disco y haciendo
inutil el cache de lectura del S.O. lo que lo haria mas lento que una
busqueda lineal.


Espero comentarios al respecto.


PD: no me vengan con que la solucion es "crear un indice del archivo"
porque el archivo en cuestion ya es un indice. :P


-- 
El Tuto
tuto@aalc.lj.cl

Clothes make the man.  Naked people have little or no influence on society.
		-- Mark Twain

Technical Details

Message-ID: <464c8e0c@news.vcd.cl>

Path:

arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!news.glorb.com!newsfeed101.telia.com!nf02.dk.telia.net!fu-berlin.de!news.nivel5.cl!news.vcd.cl!not-for-mail!not-for-mail

Show Full Headers

Complete Article Headers

X-Google-Thread: 1593cb,d09191e198c14f86,start
X-Google-Attributes: gid1593cb,public
X-Google-Language: SPANISH,ASCII
Message-ID: <464c8e0c@news.vcd.cl>
From: Alberto Hormazabal <tuto@antonia.lj.cl>
Subject: Efectividad de Busqueda Binaria dentro de un archivo
Newsgroups: chile.comp.programacion
User-Agent: tin/1.7.8-20050315 ("Scalpay") (UNIX) (Linux/2.6.8-3-686-smp (i686))
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
NNTP-Posting-Host: antonia.lj.cl
X-Original-NNTP-Posting-Host: antonia.lj.cl
Date: 17 May 2007 13:17:00 -0400
X-Trace: news.vcd.cl!not-for-mail 1179422220 200.27.221.85 (17 May 2007 13:17:00 -0400)
X-Original-Trace: 17 May 2007 13:17:00 -0400, antonia.lj.cl
Lines: 29
Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!news.glorb.com!newsfeed101.telia.com!nf02.dk.telia.net!fu-berlin.de!news.nivel5.cl!news.vcd.cl!not-for-mail!not-for-mail