Conseptos basicos de electricidad
Páginas: 10 (2443 palabras)
Publicado: 23 de abril de 2010
CAPITULO 6.
LOCALIZACIÓN RAPIDA DE DATOS EN UN ARCHIVO: INTRODUCCIÓN A LA CLASIFICACIÓN Y A LA BÚSQUEDA BINARIA.
El grado de diferencia entre el acceso a memoria RAM y a un disco fijo esta que en RAM representa 20 segundos y a disco 116 días.
La búsqueda en un archivo hace que el costo de los desplazamientos se convierta en un factor importante.
Una buen algoritmode clasificación incluso implica muchas comparaciones.
Si cada una de esas comparaciones implica un desplazamiento, la clasificación es muy lenta.
Entonces se desarrollan enfoques que minimicen el número de accesos a disco y también la cantidad de tiempo invertido.
6.1 LOCALIZACION DE DATOS EN LOS ARCHIVOS YA DESARROLLADOS.
Hasta ahora la única forma de extraer oencontrar un registro con algún grado de rapidez es buscar por su número relativo de registro (NRR).
Si el archivo tiene registros de longitud fija, conocer el NRR permite saltar al registro usando acceso directo.
Pero si no se conoce el NRR del registro que se desea es mucho mas factible que se conozca la identidad de un registro por su llave .
Hasta aquí el acceso porllave implica una búsqueda secuencial hasta que se encuentra el que contiene la llave; entonces si no existe ningún registro con esa llave tiene que revisarse todo el archivo; y si hay mas de un registro que contenga la llave y se pretende encontrarlos todos hay que examinar también todos los registros del archivo.
Se necesita encontrar una mejor forma de manejar los accesos mediante llave.6.2 BUSQUEDA POR CONJETURA: BÚSQUEDA BINARIA.
Suponer que se busca el registro, María López de un archivo de 1000 registros de longitud fija y que el archivo está clasificado de tal forma que los registros aparecen en orden ascendente por llave. Los NRR son del 0 al 999.
Se inicia comparando LOPEZ MARIA (forma canónica) con la llave que está a la mitad del archivo con NRR500. El resultado de la comparación indica cuál mitad del archivo contiene el registro María López.
Pero si se encuentra que el registro 500 es de Elisa Suárez, el resto de la búsqueda se concentra en la 1ª mitad del archivo, en los registros que van desde 0 hasta 499. Luego se compara LOPEZ MARIA con la llave de la mitad entre los registros que van desde 0 y 499, para saber en cual cuartodel archivo está el registro María López. Este proceso se repite hasta se encuentre el registro o se haya reducido el número de registros potenciales a cero.
Esta búsqueda donde la mitad de los objetos de información restantes se eliminan con cada comparación, se llama búsqueda binaria.
La búsqueda binaria realiza a los sumo
(log n) + 1 comparaciones
y enpromedio
(log n) + ½ comparaciones
Para encontrar el registro María López:
- Busqueda binaria A lo sumo 10 comparaciones
- Búsqueda secuencial A lo sumo 1000 comparaciones
En promedio 500 ½n comparaciones.
- Búsqueda binaria es O (log n)
- Búsqueda secuencial es O (n)Si se duplica el # registros del archivo, se duplica el número de comparaciones para la búsqueda secuencial, cuando se usa la búsqueda binaria, duplicar el tamaño del archivo implica hacer sólo una conjetura mas para el peor caso.
Para encontrar el registro. María López en un archivo de 2000 registros implicaría a lo sumo 1 + (log 2000)=11 comparaciones en la búsqueda secuencialimplicaría en promedio: ½ n = 1000 comparaciones y podría efectuar hasta 2000.
La búsqueda binaria funciona solo cuando la lista de registro está ordenada en términos de la llave que se esta usando en la búsqueda entonces para hacer uso de la búsqueda binaria se debe poder clasificar una lista con base en una llave.
/* Función para efectuar una búsqueda binaria en el archivo asociado con...
LOCALIZACIÓN RAPIDA DE DATOS EN UN ARCHIVO: INTRODUCCIÓN A LA CLASIFICACIÓN Y A LA BÚSQUEDA BINARIA.
El grado de diferencia entre el acceso a memoria RAM y a un disco fijo esta que en RAM representa 20 segundos y a disco 116 días.
La búsqueda en un archivo hace que el costo de los desplazamientos se convierta en un factor importante.
Una buen algoritmode clasificación incluso implica muchas comparaciones.
Si cada una de esas comparaciones implica un desplazamiento, la clasificación es muy lenta.
Entonces se desarrollan enfoques que minimicen el número de accesos a disco y también la cantidad de tiempo invertido.
6.1 LOCALIZACION DE DATOS EN LOS ARCHIVOS YA DESARROLLADOS.
Hasta ahora la única forma de extraer oencontrar un registro con algún grado de rapidez es buscar por su número relativo de registro (NRR).
Si el archivo tiene registros de longitud fija, conocer el NRR permite saltar al registro usando acceso directo.
Pero si no se conoce el NRR del registro que se desea es mucho mas factible que se conozca la identidad de un registro por su llave .
Hasta aquí el acceso porllave implica una búsqueda secuencial hasta que se encuentra el que contiene la llave; entonces si no existe ningún registro con esa llave tiene que revisarse todo el archivo; y si hay mas de un registro que contenga la llave y se pretende encontrarlos todos hay que examinar también todos los registros del archivo.
Se necesita encontrar una mejor forma de manejar los accesos mediante llave.6.2 BUSQUEDA POR CONJETURA: BÚSQUEDA BINARIA.
Suponer que se busca el registro, María López de un archivo de 1000 registros de longitud fija y que el archivo está clasificado de tal forma que los registros aparecen en orden ascendente por llave. Los NRR son del 0 al 999.
Se inicia comparando LOPEZ MARIA (forma canónica) con la llave que está a la mitad del archivo con NRR500. El resultado de la comparación indica cuál mitad del archivo contiene el registro María López.
Pero si se encuentra que el registro 500 es de Elisa Suárez, el resto de la búsqueda se concentra en la 1ª mitad del archivo, en los registros que van desde 0 hasta 499. Luego se compara LOPEZ MARIA con la llave de la mitad entre los registros que van desde 0 y 499, para saber en cual cuartodel archivo está el registro María López. Este proceso se repite hasta se encuentre el registro o se haya reducido el número de registros potenciales a cero.
Esta búsqueda donde la mitad de los objetos de información restantes se eliminan con cada comparación, se llama búsqueda binaria.
La búsqueda binaria realiza a los sumo
(log n) + 1 comparaciones
y enpromedio
(log n) + ½ comparaciones
Para encontrar el registro María López:
- Busqueda binaria A lo sumo 10 comparaciones
- Búsqueda secuencial A lo sumo 1000 comparaciones
En promedio 500 ½n comparaciones.
- Búsqueda binaria es O (log n)
- Búsqueda secuencial es O (n)Si se duplica el # registros del archivo, se duplica el número de comparaciones para la búsqueda secuencial, cuando se usa la búsqueda binaria, duplicar el tamaño del archivo implica hacer sólo una conjetura mas para el peor caso.
Para encontrar el registro. María López en un archivo de 2000 registros implicaría a lo sumo 1 + (log 2000)=11 comparaciones en la búsqueda secuencialimplicaría en promedio: ½ n = 1000 comparaciones y podría efectuar hasta 2000.
La búsqueda binaria funciona solo cuando la lista de registro está ordenada en términos de la llave que se esta usando en la búsqueda entonces para hacer uso de la búsqueda binaria se debe poder clasificar una lista con base en una llave.
/* Función para efectuar una búsqueda binaria en el archivo asociado con...
Leer documento completo
Regístrate para leer el documento completo.