Pascal/Turbo Pascal - hashing u ordenación posterior?

Buenas, tengo que hacer un programa que me guarde en un archivo de acceso directo registros, obvia mente esos registros luego pueden ser consultados, asi que me surge una duda, que creeis que es más eficiente, irlos ordenando directamente según se van introduciendo(mediante una funcion hash), u introducirlos en el orden en el que se van metiendo y después a la hora de consultarlos usar algun procedimiento de busqueda...

también había pensado en usar quicksort, o seleccion, inserccion etc.... que os parece¿?¿?

espero contsteis.muchas gracias

Cada estrategia tiene sus pros y sus contras. Por un lado la ordenación por hash tiene la ventaja de su inmediatez a la hora de encontrar el registro buscado pero la desventaja que debes mover una gran cantidad de registros si quiere poner uno "en el medio", lo que va en detrimento del rendimiento a la hora de escribir en el archivo.
Mientras que la ordenación "bajo demanda", es decir, creando un índice paralelo tiene la ventana de la inmediatiez de la escritura pero lentitud a la hora de buscar un registro.
Deberás poner a prueba estas dos estrategias y ver qué es más importante para ti, si la velocidad de búsqueda o la velocidad de escritura.
Sin embargo yo te propongo otra estrategia: crear una lista doblemente enlazada implementada sobre archivo. Esta estrategia está en equilibrio entre las dos anteriores. A la hora de agregar un registro al archivo lo haces al final, cada registro además de tener los campos propios a almacentar deben llevar dos campos más donde se almacenan las posiciones relativas en el archivo de dónde ubicar el siguiente y el anterior registro según el orden que te interese. Es decir, mantienes un índice interno. Sea cual sea el registro que leas obtienes inmediatamente la posición del siguiente registro que hace que la consulta se mantenga ordenada. Espero que entiendas la idea.

Lo primero muchas gracias por contestar, ahora vamos al grano :D

no te he entendido muy bien, a ver, vamos por partes, dices k el hashing tiene la desventaja de mover gran cantidad de registros si deseas poner uno en el medio..????.. xk?, tu mediante la funcion hash buscar la posicion a la k se debe ir ese registro, por lo tanto si t devuelve k tienes k situarlo n la posicion 30, lo situas ayi y ya está, con esto no alteras ningun registro...

luego me propones un método que se trata de situar en los registros aparte d los campos necesarios (NOMBRE,APELLIDOS,DNI...) 2, uno con l siguiente reg y otro con el anterior...esto me suena a una estructura de Lista(puntero al siguiente y al anterior, etc..) y aki no le veo ninguna utilidad, ya que no tengo que usar listas, si no ficheros de tipo registro...

no se si es k no entendi bien o k, ruego contestes, de antemano muchas gracias!!

Pues sucede que no te he entendido yo a ti cuando te refieres a hash. Y me parece que sigo sin comprenderte pues por lo que me dices entiendo esto.
Supongamos que el archivo está vacío. Y como primer registro da como resultado del hash la posición 198745. Por lo que me dices ignorarás el tamaño actual del archivo (cero) y mandarás ese registro a la posición 198745?. El archivo pesará varios megas solo para almacenar un solo registro.
Respecto a lo de listas sí, te ha sonado bien, lo que propongo es nada más que hacer una lista doblemente enlazada (para que puedas hacer tanto ordenación ascendente como descendente) implementada sobre archivo.
Ten en cuenta que yo no me planteo restricciones para resolver el problema, quizá tú sí.
El problema que te mencionaba al principio es este. Supon que quieres tener los registros almacenados en orden absoluto.
Viene el registro cuyo valor de ordenación es A, ningún problema, va en la primer posición del archivo, luego llega el B, no hay problema, va después del registro A, luego llega D, perfecto va después de B ¿y si después llega C?, ¿cómo haces para meter ese registro entre B y D si no es empujando (moviendo una posición hacia adelante D para hacer espacio para C) el registro que contiene D?, si hay un solo registro, vaya y pase, ¿pero si son 100.000?.

a ver, hay restricciones, ya que el número máximo de registros es.. 8888, por lo tanto el archivo tampoco pesaría tanto si lo hago por hashing, aunque solo es una opcion mas.
otra opcion que pensé es hacer un fichero auxiliar tipo indice, asi todo sera mas facil

No me refería a ese tipo de restricciones pero qué bueno que lo mencionas. Me refería a que solo y únicamente debes usar hashes.
Usar un archivo de índices es una buena idea, lo que yo te proponía es lo mismo excepto que el índice está dentro del propio archivo, claro que teniendo el índice de ordenación en otro archivo tiene la ventaja de que puedes ordenar el archivo por cualquier campo, la pega es que por cada ordenación tienes que reconstruir los índices :S.
Como verás el tema de bases de datos es bastante complicado.

Bueno, supongo que lo haré con indices en otros archivos, aunque stoy esperando confirmacion por parte de la profesora de ke me deje hacerlo asi... lo que pasa que me surge una duda, puedo ordenar el fichero alfabeticamente en Pascal?¿, no se si se podrá mediante los metodos comunes como quicksort, inserccion etc..espero que si porque si no...

si no sepuede hacer con ficheros indice lo ordenaré directamente en el fichero cada vez que me inserten un registro y ya está, no m quiero complicar mucho la vida que tengo que estudiar + asignaturas :D

EN mi página web tienes un ejemplo práctico de la ordenación QuickSort sobre archivos con tipo aunque no usa índices. Es perfectamente posible.

oie, me surge una duda, cada vez que introduzca un nuevo registro, lógicamente debo de actualizar los ficheros de indices, hay 2 formas, o introduzco el nuevo registro en el archivo ppal y le mando to2 los registros al indice y ke los vuelva a ordenar, o bien uso un método de ordenación directamente sobr el fichero indice.

La decisión es importante, ya que aparte de las operaciones de mostrar un registro por nombre, por nº d cuenta, u obtener un listado completo ordenado, hay otras 2 operaciones posibles, que son borrar una cuenta y fusionar (encontrar todas las cuentas del mismo usuario y fusionar todas en una, quedandose la de mas saldo y borrando las otras).

Que yo sepa no se puede borrar un registro en pascal,(se podrían hacer cosas como colocar ese registro al final y truncar el archivo x ai, pero no lo veo factible), asi que en el tipo de registro que use deberé añadir un dato que será tipo de estado, x ej activo o de_baja, por lo tanto al dar de baja a un usuario tendría que actualizarlo en el fichero ppal y en el d los indices...

que me sugieres??

respecto al algoritmo quicksort d tu pag tomo nota ;)

muchas gracias

Sabes... hay libros enteros dedicados especialmente a analizar problemas como este, que no te asuste que sea complicado tal como la llevamos :P.

Es verdad, no hemos tocado el tema de la eliminación de registros. Los grandes motores de base de datos usan el método que tú señalas, agregan un campo de estado que, entre otras cosas, marca si el registro está activo o está "eliminado". Esto tiene varias ventajas, la primera es que no tienes que mover grandes cantidades de registros para "tapar el agujero" lo que redunda en el rendimiento general de la base de datos, la otra ventaja es la posibilidad de hacer un "rollback", es decir, si el usuario metió la pata, poder volver a traer los registros mostrados. Claro que a la larga, si el archivo está lleno de registros borrados las consultas se vuelven más lentas, para ello se usan algoritmos de "packeo", es decir, se ejecuta un pack de la base de datos que vuelca a un nuevo archivo físico solamente los registros que no están marcados como borrados y se elimina el anterior (también se le dice "purgar la base de datos").

Respecto al índice externo pues como te comenté en el mensaje anterior, la lógica sería que el archivo de índice contenga tres campos, el primero almacena el índice (o puntero) del registro físico en el archivo de datos, el segundo el índice (o puntero) al registro siguiente según el criterio de ordenación, y el tercero el índice (o puntero) al registro anterior según el criterio de ordenación.

Cuando llega un registro nuevo al archivo de datos lo agregas al final sin más trámites. Luego recorres usando el archivo de índice para saber en qué lugar de la ordenación debería ir el nuevo registro, cuando estableces el lugar, creas un nuevo registro al final del archivo de índice con los tres campos correspondientes y modificas los otros dos registros para que apunten a los registros apropiados anterior y siguiente.

El código fuente para hacer esto es larguísimo pero eso no quiere decir que sea ineficiente (eficientes son los métodos, no la cantidad de líneas de un código fuente).

no entiendo eso de en el indice apuntar al anterior y al siguiente! no le veo el uso, yo abia pensado en 2 campos: uno ke sea el nº de cuenta(o nombre en el otro fichero indice), otro k sea el nº de registro en el k está en el fichero ppal

pero no se si cada vez ke se meta un registro guardarlo en el ultimo lugar en el fich ppal y en el fichero indice buskarle su sitio, o reescribir el fichero indice una vez que se ha insertado el registro en el fich ppal y ordenarlo enteramente...

lo logico seria el 1er metodo xk si tengo k andar copiando todos los registros cada vez y ordenandolos no es eficient,ya que para eso los ordeno en el fichero ppal y ya esta no??..

pero si lo ago asi no se como implementar la operacion de borrar, y menos aun la de fusionar ????????

salu2

Será mejor que continuemos esta charla por mail...

ok, de acuerdo, espero tu respuesta : [email protected]

x cierto aki te pongo un link con el enunciado de mi practica pra que te quede más claro todo: ftp://www.cc.uah.es/pub/Alumnos/I.INFORMATICA/Programacion_II/LABORATORIO/

el enunciado es el documento de word: modificada......

hay 2 archivos de ejemplo, in y hoped

contesta a ese correo,cuidate