Agregar una tabla de hash para las preferencias.

Ademas de la lista de preferencias, agregar una tabla hash que relacione el
nombre de la persona con el numero de preferencia, arrancando de 0.

Esto nos permite comparar en O(1) y asi bajar significativamente los ordenes
de varios algoritmos.

En un patch subsecuente se actualizaran los comentarios con los ordenes donde
corresponda.

diff --git a/src/parser.cpp b/src/parser.cpp
index fa2b16ab09dddbd084024c21800b03d85c9e1435..c4453ccdc074fec79b8df1ee5aa5fa50d8a7db67 100644 (file)
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -75,7 +75,7 @@ input(const std::string& filename)
                        susanita.add_persona(pp);
                }
 
-               Persona::prefs_type prefs;
+               int count = 0;
                while (ss)
                {
                        std::string nombre = get_hasta(ss, ',');
@@ -90,6 +90,8 @@ input(const std::string& filename)
                                susanita.add_persona(ppp);
                        }
                        pp->prefs.push_back(ppp);
+                       pp->prefs_hash[ppp->nombre] = count;
+                       count++;
                }
        }
        return true;

diff --git a/src/persona.cpp b/src/persona.cpp
index c93b069da73eca1ea5d501f0c0ebbfcd9a9473d7..607e0e8a0d36f0fff0464c9cdcb3490d61984e4c 100644 (file)
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -5,7 +5,8 @@
 /// Constructor
 Persona::
 Persona(const std::string& nombre, sexo_type sexo, size_type cap):
-       nombre(nombre), estado(SOLTERO), sexo(sexo), pareja(0), rechazos(cap)
+       nombre(nombre), prefs_hash(cap), estado(SOLTERO), sexo(sexo),
+       pareja(0), rechazos(cap)
 {
 }
 
@@ -60,15 +61,14 @@ operator<< (std::ostream& os, const Persona& p)
 /// Función de comparación entre dos personas según nuestras preferencias
 int
 Persona::
-cmp(const Persona& p1, const Persona& p2) const // O(N)
+cmp(const Persona& p1, const Persona& p2) const // O(1)
 {
-       prefs_type::const_iterator pos_p1
-               = std::find(prefs.begin(), prefs.end(), &p1); // O(N)
-       prefs_type::const_iterator pos_p2
-               = std::find(prefs.begin(), prefs.end(), &p2); // O(N)
-       if (pos_p1 < pos_p2)
+       int i1 = prefs_hash.get(p1.nombre); // O(1)
+       int i2 = prefs_hash.get(p2.nombre); // O(1)
+
+       if (i1 < i2)
                return 1;
-       if (pos_p1 == pos_p2)
+       if (i1 == i2)
                return 0;
        return -1;
 }

diff --git a/src/persona.h b/src/persona.h
index 907701452e3dacde8a898135730199a4489be1c4..6f44c887c5126eacd6b15b76e8a593c23c88752f 100644 (file)
--- a/src/persona.h
+++ b/src/persona.h
@@ -27,9 +27,15 @@ struct Persona
        /// Nombre de la persona, sólo con fines de representación
        std::string nombre;
 
-       /// Lista de personas que prefiere, la primera de la lista es la
-       /// que mejor posicionada esta
+       /// Para la lista de personas que prefiere usamos dos estructuras: la
+       /// primera es una lista en donde el primer elemento es la persona
+       /// mejor posicionada; la segunda es un hash indexado por el nombre de
+       /// la persona, y como valor la posicion numerica.
+       /// Esta dualidad nos permite tener iteracion en orden, O(1) en
+       /// encontrar el mejor, y O(1) en ver quien es el preferido entre dos
+       /// personas.
        prefs_type prefs;
+       HashTable<int> prefs_hash;
 
        /// Estado de la persona
        estado_type estado;