• Author / Uploaded
• MrScribd_2010

• Categories
• Arquitectura de Computadores
• Ingeniería Informática
• Áreas de informática
• Informática
• Tecnología

Citation preview

1.- Estudio Llevaremos a cabo la comparación de los dos tipos de tablas Hash la abierta y la cerrada, el estudio se centra sobre todo en las comparaciones temporales de las diferentes operaciones que llevaremos a cabo sobre las tablas. Además la conclusión del estudio nos indicará el tipo de tabla que emplearemos en el módulo y veremos las ventajas e inconvenientes de cada una de ellas.

2.- Descripción de la máquina para emplearlo La máquina es un AMD Athlon de 3000 MHz con un procesador de 64 bits y con una memoria RAM de 2 GBytes. Sistema Operativo el Windows XP Professional con el Service Pack II. El número de procesos abiertos en la máquina son los imprescindibles y básicos del sistema operativo a la hora de llevar a cabo la ejecución de los mismos.

3.- Generación de las palabras para probarlo Para llevar a cabo la prueba del estudio necesitamos un fichero de texto con una gran cantidad de palabras diferentes, porque no se pueden repetir, para ello en vez de crear un generador de palabras aleatorio que generará secuencias de caracteres aleatorios y sin sentido. Buscamos un fichero de texto que contenga palabras con significado para ello buscamos las palabras del diccionario de la R.A.E. que aunque no llega al número exacto exigido es una cantidad considerable para llevar a cabo las pruebas. Este fichero de texto tendrá palabras distintas y con significado.

4.- Tiempos de inserción y de búsqueda (milisegundos)

Tiempo en crearse Tiempo en construirse Tiempo medio por búsqueda (texto) Tiempo medio por búsqueda (posición) Colisiones

T.H.Cerrada

T.H.Abierta

16 797 125 0 9763

32 406 78 -

El número de colisiones para aproximadamente 22.000 palabras está muy bien porque es aproximadamente la mitad de las mismas, algo que nos demuestra la eficiencia de los métodos. Podemos apreciar la mejora de la búsqueda en la tabla abierta.

5.- Extra Llevaremos a cabo a parte de la redispersión, la redispersión inversa para optimizar el rendimiento de la tabla hash y que así se produzca un número más pequeño de colisiones en la tabla hash cerrada. Intentaremos además que la función sea lo más eficiente posible para que el número de colisiones se reduzca considerablemente. En unas 1000 posiciones de la tabla hash nos tendrán que aparecer entorno a unas 500 colisiones más o menos. Como tamaño para la tabla hash, el valor de B será 200057 que es el número primo más próximo a ese tamaño de problema.

6.- Conclusiones En la tabla hash abierta las consultas resultan más eficientes debido a que, si buscamos algo en una determinada lista nada más sepamos la posición ya estamos en disposición de averiguarlo, mientras que en las cerradas tenemos que ir averiguando cada una de las posiciones que siguen los elementos en la tabla. El resto de casos la creación, construcción, serán más eficientes en la tabla hash cerrada y las consultas tampoco son malas del todo, concluimos que nuestro módulo emplearemos la tabla hash cerrada para llevar a cabo la organización de los contactos.