Para este proyecto, medimos los resultados experimentales bajo el análisis de dos métricas:

Análisis de accesos a memoria secundaria

Operación	Static Hash	Sequential File
Inserción	O(1 + k)	O(n + k)
Eliminación	O(m + k)	O(log(n) + k)
Búsqueda Puntual	O(1 + k)	O(log(n) + k)
Búsqueda por rango	O(n)	O(n + k)

En el Static Hash el big O basado en los accesos a memoria es casi siempre (1 + k). En la inserción, se hace un acceso para leer el bucket de la posición hashkey y luego de revisar si el bucket está lleno; si lo está, se hace un nuevo acceso a memoria secundaria para escribir el bucket lleno al final y el bucket nuevo en la posición del lleno. En la eliminación, se hace un acceso al bucket de la posición hashkey y se hacen m acceso a memoria secundaria para encontrar el primer bucket no vacío, luego se escribe en este bucket si el elemento a eliminar está ahí o dos veces si se encuentra en otro bucket desbordado. En la búsqueda puntual, se hace un acceso al bucket de la posición hashkey y se recorre buscando la llave; si no está se realiza una búsqueda en los buckets desbordados. En la búsqueda por rango como una estructura hash no mantiene ordenados los registros de ninguna manera se debe recorrer toda la hash table en búsqueda de las llaves de aquellos registros que cumplan con lo solicitado.

En el Sequential File los accesos a memoria secundaria de todas las operaciones poseen un log(n), siendo n la cantidad de registros válidos, pues en cada operación se requiere hacer una búsqueda binaria. En una inserción regular se hace una búsqueda binaria para encontrar la posición donde insertar el nuevo registro y se maneja el caso en el que se deba insertar un registro al inicio, aunque en este último el número de accesos es constante, dando como complejidad un O(log(n)). Sin embargo, el peor caso en la inserción ocurre cuando se debe hacer una reconstrucción. Debido a que la reconstrucción debe leer todos los registros para escribirlos ordenadamente en otro archivo, el número de accesos a memoria secundaria va a ser O(n + k), siendo k el número de registros auxiliares. Asismismo, no se considera el ordenamiento que se hace en los registros auxiliares durante la reconstrucción ya que este se hace en memoria principal. En la eliminación y la búsqueda puntual el número de accesos es O(log(n) + k) pues primero se debe encontrar la posición del registro a buscar o eliminar usando una búsqueda binaria en los registros válidos (log(n)) y, en caso de que no se encuentre, se debe verificar que el siguiente registro no pertenezca a la región auxiliar, ya que de ser así se debe hacer una búsqueda secuencial en los registros auxiliares vinculados al encontrado en los registros válidos a través de los punteros al siguiente registro, búsqueda que en el peor de los casos se va a hacer en todos los registros auxiliares (k). Finalmente, para la búsqueda secuencial se hace primero una búsqueda binaria en los regsitros válidos (log(n)) para encontrar la posición inicial de búsqueda. Luego, se hace una búsqueda secuencial por todo el archivo siguiendo los punteros al siguiente registro hasta llegar al límite para el rango de búsqueda. Esta búsqueda secuencial, en el peor de los casos se hace en todo el archivo (n + k) por lo que el número de accesos va a ser igual a log(n) + (n + k), es decir, O(n + k).

Análisis de tiempos de ejecución

Para realizar el análisis de los tiempos de ejecución de las operaciones de inserción y búsqueda en ambas técnicas implementadas hicimos uso de las funciones testTimeBasket, para el dataset de Market Basket Analysis Data, y testTimeWorld, para el dataset de World Population by Year. Estas funciones ejecutan ambas operaciones con ambas técnicas por dataset con 10 valores generados aleatoriamente, registran el tiempo de ejecución de cada operación en milisegundos, y almacenan los resultados en archivos csv. De este modo, obtenemos las siguientes gráficas con sus respectivos datos:

Market Basket Analysis Data

Sequential File:

imagenes/Sequential File add (basket_analysis).png imagenes/Sequential File search (basket_analysis).png

Operación	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	Promedio
add	1,9959	4,0000	9,9910	2,2002	6,0128	40,9879	1,9988	2,2006	4,2003	6,9998	8,0587
search	3,0010	9,9970	4,0232	4,9757	6,2007	1,9992	13,0015	6,0105	5,9900	1,9989	5,7198

Static Hash:

imagenes/Static Hash add (basket_analysis).png imagenes/Static Hash search (basket_analysis).png

Operación	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	Promedio
add	7,9996	7,0055	2,9953	1,9988	0,9987	10,0004	5,9996	0,9998	4,2001	4,1961	4,6394
search	1,9999	0,999	6,0005	2,0012	1,9994	3,0072	0,9939	0,9996	0,9982	0	1,8999

Observamos, a través de las gráficas y los tiempos de ejecución promedio de las pruebas, que tanto la inserción como la búsqueda tienden a ser más rápidas en el Static Hash que en el Sequential File. Adicionalmente, en la búsqueda en el Sequential File hay una iteración en la que el tiempo de ejecución es significativamente mayor. Esto se debe a que, según los parámetros pasados por defecto a las funciones de prueba, el auxFactor de los Sequential File usados es de 5 lo que significa que, al llamar a la función de inserción por sexta vez, antes de realizar la operación en sí se va a hacer la reconstrucción del archivo.

World Population by Year

Sequential File:

imagenes/Sequential File add (WorldPopulation).png imagenes/Sequential File search (WorldPopulation).png

Operación	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	Promedio
add	2,2024	1,9964	3,003	3,0009	2,015	6,9862	2,0035	1,9925	2,9995	2,0089	2,8208
search	1,9969	3,0025	1,9985	2,002	1,0011	2,9991	3,0161	1,9821	2,0018	2,0319	2,2032

Static Hash:

imagenes/Static Hash add (WorldPopulation).png imagenes/Static Hash search (WorldPopulation).png

Operación	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	Promedio
add	3,0018	3	0,9998	0,9988	2,0004	0,9993	1,0002	2,0038	0,9963	1,0004	1,6001
search	1,0001	1,0012	1,0114	0	0,9883	1,0037	1,0122	0,9831	1,0006	0	0,8001

Se puede observar que el comportamiento del Sequential File y el Static Hash en este dataset es similar al comportamiento de estos mismos pero en el dataset de Market Basket Analysis Data. Osea que, sin importar el dataset que se use en las técnicas implementadas, estas siguen ejecutando un funcionamiento deseado. En el caso de las inserciones del Sequential File en ambos datasets se observa como al momento de insertar el sexto registro hay una subida en el tiempo de ejecución. Cabe aclarar que como el World Population tiene menos registros, el incremento que experimenta cuando se inserta el sexto registro es menor que cuando pasa lo mismo pero en el Sequential File con el dataset de Basket. Ahora, en el caso de las operaciones del Static Hash en ambos datasets se observa como los tiempos son muy bajos y casi constantes. Es decir, se comprueba que nuestra implementación del Static Hash tiene tiempos de ejecución constantes, como es de esperarse de esta técnica.

Conclusiones

Como podemos observar, hemos podido alcanzar los resultados esperados. El Sequential File y el Static Hash realizan los funcionamientos esperados en tiempos convenientes, siendo este último en general más eficiente que el primero para operaciones tanto de inserción como búsqueda puntual. Esto se debe a que un orden de crecimiento logarítmico, en el caso del Sequential File, es menos eficiente que uno que tiende a ser constante, en el caso del Static Hash. Asimismo, las técnicas implementadas funcionan de la misma manera para dos datasets con distintas cantidades de campos. También hemos podido analizar su funcionamiento respecto a los accesos a memoria secundaria y a su tiempo de ejecución. En el análisis de tiempos podemos comprobar lo explicado en el análisis de accesos a memoria secundaria pues en ambos casos las técnicas tienen el mismo comportamiento. Por ejemplo, en el análisis de accesos mencionamos que el Sequential File tendrá un costo extra de reconstrucción cuando haya una cierta cantidad de registros auxiliares y en el análisis de tiempos de ejecución esto se puede ver en los gráficos y las tablas de tiempos.