Thread View: chile.comp.programacion
3 messages
3 total messages
Started by Alberto Hormazabal
Thu, 17 May 2007 17:17
Efectividad de Busqueda Binaria dentro de un archivo
Author: Alberto Hormazabal
Date: Thu, 17 May 2007 17:17
Date: Thu, 17 May 2007 17:17
29 lines
1859 bytes
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
Re: Efectividad de Busqueda Binaria dentro de un archivo
Author: Alberto Hormazabal
Date: Thu, 17 May 2007 17:18
Date: Thu, 17 May 2007 17:18
41 lines
2299 bytes
2299 bytes
Alberto Hormazabal visito chile.comp.programacion y balbuceo: > 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 otra cosa que se me ocurre es partir con busqueda binaria y cuando llegue a un rango aceptable continuar con busqueda lineal... a todo esto el lenguaje es C, para usar en AIX y Linux. -- El Tuto tuto@aalc.lj.cl Q: Why do ducks have big flat feet? A: To stamp out forest fires. Q: Why do elephants have big flat feet? A: To stamp out flaming ducks.
Re: Efectividad de Busqueda Binaria dentro de un archivo
Author: Tomas Bradanovic
Date: Thu, 17 May 2007 23:39
Date: Thu, 17 May 2007 23:39
40 lines
2365 bytes
2365 bytes
On 17 May 2007 13:17:00 -0400, Alberto Hormazabal <tuto@antonia.lj.cl> wrote: >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 -------> yo pase muchos a�os haciendo pruebas con busqueda lineal, binaria, indexada, etc etec consejo parte con busqueda lineal y ve los tiempos de respuesta, a menos que tengas un archivo enorme normalmente con busqueda lineal basta en los equipos modernos. Ai demora mucho recien empieza por binaria. Muchas veces se sobreprograma innecesariamente saludos/tomas sacar a mil: http://www.bradanovic.cl/blogger/blogger.htm http://www.bradanovic.cl http://www.tombrad.blogspot.cl http://www.infoarica.cl http://www.infoarica.blogspot.com http://www.infoaricaes.blogspot.com
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads