From: Leandro Lucarella Date: Fri, 4 Nov 2005 06:17:41 +0000 (+0000) Subject: Agrega y usa tabla hash. X-Git-Tag: darcs_import~41 X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/commitdiff_plain/a0283c7c8bac089e59bd47b1c25ee795d96e03e3 Agrega y usa tabla hash. Este parche agrega una tabla hash de hashing abierto _MUY_ simple, de tamaño inmutable (elegido al construirla). Sólo se pueden obtener elementos del hash, no eliminar (total la población de claves no cambia en todo el programa). En fin, bien específica para este problema. La implementación consiste en un vector donde cada elemento es una lista donde cada elemento es una tupla (clave, valor). Si la lista está vacía, entonces esa posición del hash está vacía, si tiene un elemento obtenerlo es O(1) y si tiene más (colisión) es O(colision) (no está ordenada ni nada porque podemos garantizar MUY fácil que casi no haya colisiones dandole una capacidad apropiada a la tabla hash). Como para construir la tabla de hash necesitamos saber la cardinalidad de la población de antemano, hice un hack medio feo pero útil que lee la 1ra línea del archivo y cuenta la cantidad de nombres en la lista de preferencias de la 1ra persona, con eso basta para obtener el N del problema. La tabla de hash la crea con capacidad N * 2 (así tiene un factor de ocupación de 50% como decían en la práctica). Por último, uso el hash para Susanita::nombres, cosa que no sé si es del todo útil (se usa sólo en el parser, calculo que para que el algoritmo sea O(N^2) deberíamos usar el hash en la resolución). Pero bueno, tenía que ponerlo en algún lado para probarlo =) ---