Ficheros
Hola, estoy realizando una práctica de ficheros de una asignatura de la universidad y me han surgido unas dudas, a ver si me las puede resolver:
-Con unos registros tenemos que utilizar dispersión, guardarlos en un fichero y que este tenga un área de desbordamiento por si hay registros que no caben en un bloque, y en el enunciado de la práctica dice:
" La gestión de desbordamiento es con encadenamiento de claves sinónimas dentro de una organización serial"
¿Qué es esto y como se puede implementar?
Las claves sinónimas se que son los registros que al aplicarles una función hash obtenemos el mismo número o misma clave.
Lo que he podido recopilar es que cuando un registro no cabe en un bloque, debo llevarlo al área de desbordamiento, pero no se si en el área de desbordamiento debo insertarlo en el primero hueco libre que encuentre o a continuación del último registro insertado.
Te agradecería mucho que me indicases como puedo implementar esto.
Muchas gracias
-Con unos registros tenemos que utilizar dispersión, guardarlos en un fichero y que este tenga un área de desbordamiento por si hay registros que no caben en un bloque, y en el enunciado de la práctica dice:
" La gestión de desbordamiento es con encadenamiento de claves sinónimas dentro de una organización serial"
¿Qué es esto y como se puede implementar?
Las claves sinónimas se que son los registros que al aplicarles una función hash obtenemos el mismo número o misma clave.
Lo que he podido recopilar es que cuando un registro no cabe en un bloque, debo llevarlo al área de desbordamiento, pero no se si en el área de desbordamiento debo insertarlo en el primero hueco libre que encuentre o a continuación del último registro insertado.
Te agradecería mucho que me indicases como puedo implementar esto.
Muchas gracias
1 Respuesta
Respuesta de villalvilla
1
No me quitas tiempo, tranqui!
Yo ayudo por voluntad propia, y porque cuando estaba en tu brete me sentía igual que tú! Los funcionarios lo son siempre, y no ayudan más de lo imprescindible y con unos tecnicismos dignos de los dioses supremos del olimpo!
Y además cuando aprendes algo te das cuenta de que no tenían npi! Se aprovechan de temarios del siglo 19! Y no se puede estar durante 15 ó 20 con el mismo temario...¡Y encima les pagan!... pero ese no es tu problema ahora... vamos con el!
1. Lo del tema de los punteros: si la implementación es en disco, como me has dicho, te sirven para metérselos por el culo al catedrático... aunque no es recomendado hasta que acabes la carrera... sería en pascal lo siguiente:
RECORD t_estructura;
begin
catedratico:integer;
catedratico1:integer;
PosiciónColisionSiguiente:integer;
end;
f1:file of t_estructura;
function fHash(num:integer):integer;
(*suponemos la función de arriba declarada*)
var
miregistro:t_estructura;
nHash:integer;(*para valor devuelto por fhash*)
miParametro:integer;
begin (*prog ppal*)
assign(f1,'c:\mifichero');
reset(f1); (*ojo, reset te machaca el fichero! Si tienes que acceder sin machacar contenidos, seek!
(*pido 1 posicion*);
miParametro:=readln;(*para pillar la clave indice*)
nHash:=fHash(miParametro);
(*en nHash tendré la posición del fichero donde meter el nuevo registro*)
seek(f1,nHash);
miRegistro.Catedratico:=5;
miRegistro.Catedratico1:=6;
miRegistro.PosiciónColisionSiguiente:=-1;
write(f1,miRegistro);
close(f1);
end;
Esto es para introducir en 1 fichero datos! No te hace falta comprobar tamaños de los registros porque son de 1024!
Para búsquedas con seek. Date cuenta del parámetro
PosiciónColisionSiguiente, que es con el que tienes que hacer la cadena de colisiones. Cuando en la inserción colisiones, da 1 posición del fichero donde esté tu overflow y que esté libre y le pones esa posición de fichero en ese campo al primer registro y así! Lo único que tienes que recorrer es esa lista si hay más colisiones, por eso es lineal! Si no fuera lineal, tendrías dos enteros, 1 para saber el último elemento y otro para el primero! Al leer, si el hash te da 1 registro que no tiene la clave que buscas, recorre la misma lista hasta que lo encuentres!
Espero haber sido de ayuda! Suerte y no dudes en preguntar!
Yo ayudo por voluntad propia, y porque cuando estaba en tu brete me sentía igual que tú! Los funcionarios lo son siempre, y no ayudan más de lo imprescindible y con unos tecnicismos dignos de los dioses supremos del olimpo!
Y además cuando aprendes algo te das cuenta de que no tenían npi! Se aprovechan de temarios del siglo 19! Y no se puede estar durante 15 ó 20 con el mismo temario...¡Y encima les pagan!... pero ese no es tu problema ahora... vamos con el!
1. Lo del tema de los punteros: si la implementación es en disco, como me has dicho, te sirven para metérselos por el culo al catedrático... aunque no es recomendado hasta que acabes la carrera... sería en pascal lo siguiente:
RECORD t_estructura;
begin
catedratico:integer;
catedratico1:integer;
PosiciónColisionSiguiente:integer;
end;
f1:file of t_estructura;
function fHash(num:integer):integer;
(*suponemos la función de arriba declarada*)
var
miregistro:t_estructura;
nHash:integer;(*para valor devuelto por fhash*)
miParametro:integer;
begin (*prog ppal*)
assign(f1,'c:\mifichero');
reset(f1); (*ojo, reset te machaca el fichero! Si tienes que acceder sin machacar contenidos, seek!
(*pido 1 posicion*);
miParametro:=readln;(*para pillar la clave indice*)
nHash:=fHash(miParametro);
(*en nHash tendré la posición del fichero donde meter el nuevo registro*)
seek(f1,nHash);
miRegistro.Catedratico:=5;
miRegistro.Catedratico1:=6;
miRegistro.PosiciónColisionSiguiente:=-1;
write(f1,miRegistro);
close(f1);
end;
Esto es para introducir en 1 fichero datos! No te hace falta comprobar tamaños de los registros porque son de 1024!
Para búsquedas con seek. Date cuenta del parámetro
PosiciónColisionSiguiente, que es con el que tienes que hacer la cadena de colisiones. Cuando en la inserción colisiones, da 1 posición del fichero donde esté tu overflow y que esté libre y le pones esa posición de fichero en ese campo al primer registro y así! Lo único que tienes que recorrer es esa lista si hay más colisiones, por eso es lineal! Si no fuera lineal, tendrías dos enteros, 1 para saber el último elemento y otro para el primero! Al leer, si el hash te da 1 registro que no tiene la clave que buscas, recorre la misma lista hasta que lo encuentres!
Espero haber sido de ayuda! Suerte y no dudes en preguntar!
Vamos por pasos...
1024 es el tamaño de lo que se denomina en el mundo de las estructuras de datos como "UBLE"=Unidad Básica de Lectura Escritura...
Una vez sabido eso, tienes que saber también si lo que te mandan hacer en la práctica, como te dije en el anterior mail, es la estructura indice hash en disco o en memoria ram! Diferencias:
Si la haces en disco no hay punteros ni cristo que lo fundó... y si es así es para darle 2 ostias a tu "cateto" de profesor porque al decirte "A cierto registro le hago la función hash y obtengo una clave, entonces, con esta clave se donde tengo que insertar el registro. Si un segundo registro que me da la misma clave me desborda el bloque, lo tengo que llevar al área de desbordamiento y colocar un puntero que indique donde se encuentra este registro en el área de desbordamiento" te está confundiendo, y entonces no sabes ni en que cubo meas... eso lo suelen hacer mucho... pero no desesperes.. tranqui! En contraposición está la implementación en memoria, que es más sencilla por otro lado!
Bien, sabido esto, debes explicarme si es en disco o no! Si es en disco, todo funciona con ficheros de registros de 1 tipo definido por ti. En este caso ese tipo tendrá que tener 1 espacio máximo de 1024bytes (tamaño de la UBLE).
Sabido esto también, has de haber valorado algunos aspectos, como son el tamaño de tu indice hash para que con el 4% de su tamaño de zona de overflow te sea suficiente... además puede que te dé tantas colisiones porque la función hash que estás usando sea muy ineficiente... también tendrás que valorar la posibilidad de elegir otra, o si por el contrario la función te la da ya el profesor pues pegarle un tiro o una paliza, lo dejo a tu elección, porque el tío es como todos los profes de universidad, experto en acertijos y/o adivinanzas!
Lo del encadenamiento significa algo así como ir haciendo "listas dinámicas" dentro de tu indice hash para albergar las colisiones que te va dando la inserción de nuevos registros. Ejemplo:
Inserto un registro y a continuación otro que me da la misma dirección que el primero, por tanto lo tengo que almacenar en mi zona de overflow... donde tengo el primer registro ya insertado me apunto donde voy a insertar el segundo que tiene colisión e inserto este último allí.
Si ahora inserto un tercer registro que colisione con el primero, me voy a la dirección que me apunté donde se encontraba el segundo, le apunto la dirección donde voy a almacenar dicho tercer registro y me almaceno allí... y así sucesivamente!
1024 es el tamaño de lo que se denomina en el mundo de las estructuras de datos como "UBLE"=Unidad Básica de Lectura Escritura...
Una vez sabido eso, tienes que saber también si lo que te mandan hacer en la práctica, como te dije en el anterior mail, es la estructura indice hash en disco o en memoria ram! Diferencias:
Si la haces en disco no hay punteros ni cristo que lo fundó... y si es así es para darle 2 ostias a tu "cateto" de profesor porque al decirte "A cierto registro le hago la función hash y obtengo una clave, entonces, con esta clave se donde tengo que insertar el registro. Si un segundo registro que me da la misma clave me desborda el bloque, lo tengo que llevar al área de desbordamiento y colocar un puntero que indique donde se encuentra este registro en el área de desbordamiento" te está confundiendo, y entonces no sabes ni en que cubo meas... eso lo suelen hacer mucho... pero no desesperes.. tranqui! En contraposición está la implementación en memoria, que es más sencilla por otro lado!
Bien, sabido esto, debes explicarme si es en disco o no! Si es en disco, todo funciona con ficheros de registros de 1 tipo definido por ti. En este caso ese tipo tendrá que tener 1 espacio máximo de 1024bytes (tamaño de la UBLE).
Sabido esto también, has de haber valorado algunos aspectos, como son el tamaño de tu indice hash para que con el 4% de su tamaño de zona de overflow te sea suficiente... además puede que te dé tantas colisiones porque la función hash que estás usando sea muy ineficiente... también tendrás que valorar la posibilidad de elegir otra, o si por el contrario la función te la da ya el profesor pues pegarle un tiro o una paliza, lo dejo a tu elección, porque el tío es como todos los profes de universidad, experto en acertijos y/o adivinanzas!
Lo del encadenamiento significa algo así como ir haciendo "listas dinámicas" dentro de tu indice hash para albergar las colisiones que te va dando la inserción de nuevos registros. Ejemplo:
Inserto un registro y a continuación otro que me da la misma dirección que el primero, por tanto lo tengo que almacenar en mi zona de overflow... donde tengo el primer registro ya insertado me apunto donde voy a insertar el segundo que tiene colisión e inserto este último allí.
Si ahora inserto un tercer registro que colisione con el primero, me voy a la dirección que me apunté donde se encontraba el segundo, le apunto la dirección donde voy a almacenar dicho tercer registro y me almaceno allí... y así sucesivamente!
Hola de nuevo, más o menos me voy aclarando, y me encuentro en el siguiente punto.
Mi zona de overflow se encuentra en el mismo fichero y es un 4% del área de direccionamiento.
Además, en el área de direccionamiento debo guardar espacio para un puntero.
Cada vez que leo de fichero lo hago por bloques de 1024 bytes, es decir, tengo un array de 1024 posiciones de tipo char.
Entonces, un profesor de la universidad me ha dicho que debo utilizar punteros de la siguiente forma:
A cierto registro le hago la función hash y obtengo una clave, entonces, con esta clave se donde tengo que insertar el registro. Si un segundo registro que me da la misma clave me desborda el bloque, lo tengo que llevar al área de desbordamiento y colocar un puntero que indique donde se encuentra este registro en el área de desbordamiento, pero aquí vienen los problemas,
Si me dicen que este área es serial, los punteros no me sirven de nada ya que tengo que recorrerme entera el área de desbordamiento para buscar algo, ¿no?
Suponiendo que utilice punteros, ¿cómo los utilizo? Ya que en mi práctica me desbordan como unos 50 registros y si cada bloque del área de desbordamiento lo utilizo para una misma clave sinónima no tengo espacio para todos (mi área de desborda tiene como mucho 14 o 15 líneas).
Y por último, no se si se refieren con encadenamiento a encadenar los registros con punteros o a la forma que he colocado los registros uno detrás de otros y si he utilizado algún carácter diferenciador.
Muchas gracias
Mi zona de overflow se encuentra en el mismo fichero y es un 4% del área de direccionamiento.
Además, en el área de direccionamiento debo guardar espacio para un puntero.
Cada vez que leo de fichero lo hago por bloques de 1024 bytes, es decir, tengo un array de 1024 posiciones de tipo char.
Entonces, un profesor de la universidad me ha dicho que debo utilizar punteros de la siguiente forma:
A cierto registro le hago la función hash y obtengo una clave, entonces, con esta clave se donde tengo que insertar el registro. Si un segundo registro que me da la misma clave me desborda el bloque, lo tengo que llevar al área de desbordamiento y colocar un puntero que indique donde se encuentra este registro en el área de desbordamiento, pero aquí vienen los problemas,
Si me dicen que este área es serial, los punteros no me sirven de nada ya que tengo que recorrerme entera el área de desbordamiento para buscar algo, ¿no?
Suponiendo que utilice punteros, ¿cómo los utilizo? Ya que en mi práctica me desbordan como unos 50 registros y si cada bloque del área de desbordamiento lo utilizo para una misma clave sinónima no tengo espacio para todos (mi área de desborda tiene como mucho 14 o 15 líneas).
Y por último, no se si se refieren con encadenamiento a encadenar los registros con punteros o a la forma que he colocado los registros uno detrás de otros y si he utilizado algún carácter diferenciador.
Muchas gracias
Gracias por la rapidez.
Pues el hash lo tengo que hacer en un fichero, es decir, en disco. Y como muy bien dices, cada bloque es de 1024 bytes.
Lo único que no entiendo muy bien es el porque de los punteros si el área de desbordamiento es serial. Y al ser serial, cada vez que quiera buscar algo debo recorrerla entera.
Entonces es esto lo que no entiendo, porque punteros si cuando quiera buscar o insertar algo voy a tener que recorrer las 14 o 15 líneas que tengo de área de desbordamiento.
Una última cosa, si tengo que utilizar punteros porque si, ¿cómo coloco los registros en el área de desborda?
Yo lo estaba colocando en el bloque que me entrase, es decir, leo serialmente desde el principio del área de desborda, por cada bloque miro el espacio libre y si cabe lo inserto, si no cabe, pues busco en los bloques siguientes, y cuando quiera buscar algo, como tengo que hacer en la práctica hago lo siguiente:
Se introduce el titulo del libro que quiero buscar, que es mi caso, le hago el hash a la suma de caracteres ascii, una vez obtenido la clave me voy al bloque del área de direccionamiento y lo busco, si no está ahí, busco serialmente en el área de desbordamiento.
Lo de que el área de desbordamiento sea suficientemente grande ya lo tengo comprobado, ya que parto de un fichero optimizado al que le he quitado espacios y demás historias, este fichero optimizado es de 290 bloques y le he tenido que sumar otros 211 bloques para que al hacer el 4% del área de desbordamiento pueda almacenar todos los registros.
Estudio en la Carlos III de Madrid y el único profesor con el que he podido contactar era extranjero y no me ha terminado de aclarar, me dijo que pasara por su despacho a finales de Agosto pero claro, la práctica la tengo que entregar el día 3 y esto lo tengo que solucionar ya mismo ya que tengo que hacer una especie de base de datos en SQL.
No te quito más tiempo y muchas gracias por tus respuestas
Pues el hash lo tengo que hacer en un fichero, es decir, en disco. Y como muy bien dices, cada bloque es de 1024 bytes.
Lo único que no entiendo muy bien es el porque de los punteros si el área de desbordamiento es serial. Y al ser serial, cada vez que quiera buscar algo debo recorrerla entera.
Entonces es esto lo que no entiendo, porque punteros si cuando quiera buscar o insertar algo voy a tener que recorrer las 14 o 15 líneas que tengo de área de desbordamiento.
Una última cosa, si tengo que utilizar punteros porque si, ¿cómo coloco los registros en el área de desborda?
Yo lo estaba colocando en el bloque que me entrase, es decir, leo serialmente desde el principio del área de desborda, por cada bloque miro el espacio libre y si cabe lo inserto, si no cabe, pues busco en los bloques siguientes, y cuando quiera buscar algo, como tengo que hacer en la práctica hago lo siguiente:
Se introduce el titulo del libro que quiero buscar, que es mi caso, le hago el hash a la suma de caracteres ascii, una vez obtenido la clave me voy al bloque del área de direccionamiento y lo busco, si no está ahí, busco serialmente en el área de desbordamiento.
Lo de que el área de desbordamiento sea suficientemente grande ya lo tengo comprobado, ya que parto de un fichero optimizado al que le he quitado espacios y demás historias, este fichero optimizado es de 290 bloques y le he tenido que sumar otros 211 bloques para que al hacer el 4% del área de desbordamiento pueda almacenar todos los registros.
Estudio en la Carlos III de Madrid y el único profesor con el que he podido contactar era extranjero y no me ha terminado de aclarar, me dijo que pasara por su despacho a finales de Agosto pero claro, la práctica la tengo que entregar el día 3 y esto lo tengo que solucionar ya mismo ya que tengo que hacer una especie de base de datos en SQL.
No te quito más tiempo y muchas gracias por tus respuestas
A parte date cuenta de que es imposible hacerlo con punteros! ¿1 puntero a donde?
¿Cuándo r los registros muy bien, todo perfecto y chachi powerpoint porque estás con el espacio de ierto y las referencias a memoria son las mismas siempre, pero cuando cambiaras de zona dasignada por el sistema operativo que? Es decir, si cierras la aplicación y la vuelves a aila del sistema te adjudica otras áreas de memoria completamente distintas, y los punterosaste apuntando a 1as determinadas zonas de memoria querrán apuntar a ellas, ¿por qué están a en memoria no volátil... y a que cojones van a acceder si donde apuntaban era a 1 posic? En fin, que lo tienes bien hecho a mi modo de ver en disco... pero lo de la estructura setienes que recorrer toda la estructura de overflow hasta encontrar el elemento creo yo... e ver donde se encuentra en su lista particular de colisiones como te dije...
1 saludo. P finaliza las preguntas en que no vayas a seguir preguntando si puede ser porque me llena mensajes el todoexpertos este... son mu pesados!
¿Cuándo r los registros muy bien, todo perfecto y chachi powerpoint porque estás con el espacio de ierto y las referencias a memoria son las mismas siempre, pero cuando cambiaras de zona dasignada por el sistema operativo que? Es decir, si cierras la aplicación y la vuelves a aila del sistema te adjudica otras áreas de memoria completamente distintas, y los punterosaste apuntando a 1as determinadas zonas de memoria querrán apuntar a ellas, ¿por qué están a en memoria no volátil... y a que cojones van a acceder si donde apuntaban era a 1 posic? En fin, que lo tienes bien hecho a mi modo de ver en disco... pero lo de la estructura setienes que recorrer toda la estructura de overflow hasta encontrar el elemento creo yo... e ver donde se encuentra en su lista particular de colisiones como te dije...
1 saludo. P finaliza las preguntas en que no vayas a seguir preguntando si puede ser porque me llena mensajes el todoexpertos este... son mu pesados!
A ver, vamos por pasos todoexpertos!
0. Depende de la universidad en la que estés, a lo mismo le llaman de 1 forma o de otra... tus apuntes podrían ayudar en este punto!
1. Este tipo de estructuras de datos, también llamadas ficheros índice, se suelen utilizar para ahorrar el número de accesos al disco duro, ya que es mucho más costoso que a memoria principal, de tal forma que sacas la posición en disco de los datos con 1 acceso y pico de media a disco y luego accedes mediante esa posición al fichero de datos.
2. Creo que por lo que me has contado que lo que te piden es 1 práctica de ficheros hash con almacenamiento externo con zona de overflow! Pero es importante la segunda parte... no es igual que hagas el tratamiento de colisiones con almacenamiento externo que con almacenamiento interno... y ya no digamos con buckets o sin buckets.
3. Otro handicap es si este fichero índice del que te hablo lo tienes que implementar en disco o en memoria... en memoria es mucho más rápido, pero caben pocos registros porque, como sabrás, la memoria ram es limitada...
4. Voy a intentarte explicar brevemente de que se trata lo que tienes que hacer. Bueno, la historia es tener 2 ficheros, 1 índice, donde tienes que implementar las movidas estas que no entendías lo que significaban (fichero índice) y otro secuencial de datos. El problema que tu tienes con los ficheros hash (problema adicional) es que es muy difícil hacer 1 función hash que no tenga colisiones (que no genere claves sinónimas), por lo tanto hay dos maneras principales de solucionar esto:
a) Almacenamiento interno: se trata de meter las claves sinónimas dentro del mismo fichero hash en el primer hueco que encuentres.(Resulta en una mala implementación porque genera a priori más colisiones. Se usa para bases de datos con muy poca carga de datos)
b) Almacenamiento externo:
Utilizando 1 fichero adicional llamado "zona de overflow" para almacenar los datos que te han creado colisión! Este fichero adicional, además, para que tengas que hacer menos accesos a disco, lo puedes organizar con buckets. ¿Qué es 1 bucket? Muy sencillo, en lugar de tener en cada registro del fichero 1 solo hueco de memoria, tienes 1 array que te traes a memoria de golpe de 1 sola vez y así minimizas los accesos.
5. Además tienes que saber si vas a implementar lista de huecos o no, que creo que no es el caso! La lista de huecos no sirve nada más que para recompactar el fichero hash cuando has hecho muchos accesos a su estructura! Te indica donde puedes meter la siguiente colisión con seguridad sin tener que buscarle sitio.
0. Depende de la universidad en la que estés, a lo mismo le llaman de 1 forma o de otra... tus apuntes podrían ayudar en este punto!
1. Este tipo de estructuras de datos, también llamadas ficheros índice, se suelen utilizar para ahorrar el número de accesos al disco duro, ya que es mucho más costoso que a memoria principal, de tal forma que sacas la posición en disco de los datos con 1 acceso y pico de media a disco y luego accedes mediante esa posición al fichero de datos.
2. Creo que por lo que me has contado que lo que te piden es 1 práctica de ficheros hash con almacenamiento externo con zona de overflow! Pero es importante la segunda parte... no es igual que hagas el tratamiento de colisiones con almacenamiento externo que con almacenamiento interno... y ya no digamos con buckets o sin buckets.
3. Otro handicap es si este fichero índice del que te hablo lo tienes que implementar en disco o en memoria... en memoria es mucho más rápido, pero caben pocos registros porque, como sabrás, la memoria ram es limitada...
4. Voy a intentarte explicar brevemente de que se trata lo que tienes que hacer. Bueno, la historia es tener 2 ficheros, 1 índice, donde tienes que implementar las movidas estas que no entendías lo que significaban (fichero índice) y otro secuencial de datos. El problema que tu tienes con los ficheros hash (problema adicional) es que es muy difícil hacer 1 función hash que no tenga colisiones (que no genere claves sinónimas), por lo tanto hay dos maneras principales de solucionar esto:
a) Almacenamiento interno: se trata de meter las claves sinónimas dentro del mismo fichero hash en el primer hueco que encuentres.(Resulta en una mala implementación porque genera a priori más colisiones. Se usa para bases de datos con muy poca carga de datos)
b) Almacenamiento externo:
Utilizando 1 fichero adicional llamado "zona de overflow" para almacenar los datos que te han creado colisión! Este fichero adicional, además, para que tengas que hacer menos accesos a disco, lo puedes organizar con buckets. ¿Qué es 1 bucket? Muy sencillo, en lugar de tener en cada registro del fichero 1 solo hueco de memoria, tienes 1 array que te traes a memoria de golpe de 1 sola vez y así minimizas los accesos.
5. Además tienes que saber si vas a implementar lista de huecos o no, que creo que no es el caso! La lista de huecos no sirve nada más que para recompactar el fichero hash cuando has hecho muchos accesos a su estructura! Te indica donde puedes meter la siguiente colisión con seguridad sin tener que buscarle sitio.
