Eficiencia de Diccionarios en sus Diferentes Representaciones

Nombre: Oscar Daniel Crdenas P.Cdigo: 285723

Se compararon diccionarios empleando representaciones mediante:

Sorted Chain. BST. HashTable.

SortedChain fue demasiado ineficiente para las operaciones con el milln de datos, por lo cual, este tipo de diccionario se trabaj solo con 10.000 datos, as que sus resultados no pueden ser comparados directamente con los correspondientes a las otras representaciones.

Se hicieron mediciones bajo la variacin de dos parmetros, los cuales son:

Divisor del HashTable. Cantidad de repeticin de los datos.

Cada uno de los parmetros se trabaj en tres niveles: bajo, medio y alto. Los valores asociados a cada uno de ellos se presentan en la siguiente tabla:

BajoMedio Alto

Divisor del Hash200.000500.0001000000

Cant. de Repeticiones5 rep/valor2 rep/valor0 rep

Resultados: El primer valor de nivel corresponde a la cantidad de repeticiones y el segundo, al divisor del hash.

BAJO-BAJO

BAJO-MEDIO

BAJO-ALTO

MEDIO-MEDIO

MEDIO-ALTO

ALTO-ALTO

Las posibles combinaciones de niveles que faltaron por tomar, no se hicieron porque en esos casos, el diccionario con HashTable arrojo la excepcin de full (lleno).

CONCLUSIONES

En el caso de altas repeticiones y un divisor de Hash bajo, el diccionario con BST se empieza a comportar mejor que el diccionario con Hash Table.

El diccionario con hash table toma la mayor cantidad de tiempo en el mtodo remove, pero su mtodo get es muy rpido comparado con el get del diccionario con BST.

A medida que empieza a disminuir el nmero de repeticiones, se descongestiona el tiempo de uso para el mtodo remove en el diccionario con Hash, lo que mejora considerablemente el rendimiento. Por otro lado se aumenta fuertemente el tiempo de ejecucin para el diccionario con BST, pues los mtodos get y put gastan ms tiempo por dato insertado y se ha aumentado la variedad de datos a agregar.

El diccionario con chain en todos los escenarios analizados, fue mucho menos eficiente que sus competidores.