Hacer que Persona.rechazos sea una HashTable y no una deque.

Esto elimina el orden O(N) en partes de la nesima_ronda().

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index 613c8b76cff06bf8c3fd9f18a56657adf386e8a6..b2f2ac3363365304b559518ddc4355772c994f8d 100644 (file)
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -7,37 +7,39 @@
 #include <algorithm>
 
 GaleShapley::
-GaleShapley()
+GaleShapley(size_type capacidad):
+       Susanita(capacidad)
 {
 }
 
 void
 GaleShapley::
-primera_ronda()
+primera_ronda() // O(N^3.log(N^2))
 {
-       for (personas_type::iterator ih = hombres.begin();
+       for (personas_type::iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
        {
-               (*ih)->declarar_a(*((*ih)->prefs[0]));
+               (*ih)->declarar_a(*((*ih)->prefs.front())); // O(1)
        }
-       for (personas_type::iterator im = mujeres.begin();
+       for (personas_type::iterator im = mujeres.begin(); // O(N)
                        im != mujeres.end(); ++im)
        {
                Persona& m = **im;
-               if (m.ofertas.empty())
+               if (m.ofertas.empty()) // O(1)
                        continue;
-               m.ordenar_ofertas();
-               Persona& prometido = *(m.ofertas.front());
-               m.ofertas.pop_front();
-               m.comprometer_con(prometido);
+               m.ordenar_ofertas(); // O(N^2.log(N^2))
+               Persona& prometido = *(m.ofertas.front()); // O(1)
+               m.ofertas.pop_front(); // O(1)
+               m.comprometer_con(prometido); // O(N)
        }
 }
 
 void
 GaleShapley::
-nesima_ronda()
+nesima_ronda() // O(N^3.log(N^2))
 {
-       for (personas_type::iterator ih = hombres.begin();
+       // Todo el for es O(N^3)
+       for (personas_type::iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
        {
                Persona& h = **ih;
@@ -45,62 +47,65 @@ nesima_ronda()
                        continue;
 
                Persona* pm = 0;
-               for (personas_type::iterator im = h.prefs.begin();
+               for (personas_type::iterator im = h.prefs.begin(); // O(N)
                                im != h.prefs.end(); ++im)
                {
                        pm = *im;
-                       if (std::find(h.rechazos.begin(), h.rechazos.end(), pm)
-                                       != h.rechazos.end()) // Si está
+
+                       if (h.rechazos[pm->nombre] != NULL) // O(1)
+                               // Si está
                                continue;
                        break;
                }
-               assert(pm);
-               h.declarar_a(*pm);
+               assert(h.rechazos[pm->nombre] == NULL);
+               h.declarar_a(*pm); // O(1)
        }
 
-       for (personas_type::iterator im = mujeres.begin();
+       // Todo el for es O(N^3.log(N^2))
+       for (personas_type::iterator im = mujeres.begin(); // O(N)
                        im != mujeres.end(); ++im)
        {
                Persona& m = **im;
-               if (m.ofertas.empty())
+               if (m.ofertas.empty()) // O(1)
                        continue;
 
-               m.ordenar_ofertas();
-               Persona* ph = m.ofertas.front();
-               m.ofertas.pop_front();
+               m.ordenar_ofertas(); // O(N^2.log(N^2))
+               Persona* ph = m.ofertas.front(); // O(1)
+               m.ofertas.pop_front(); // O(1)
                if (m.estado == Persona::COMPROMETIDO)
                {
-                       if (m.cmp(*(m.pareja), *ph) < 0)
+                       if (m.cmp(*(m.pareja), *ph) < 0) // O(N)
                        {
                                // la oferta es mejor, rompemos el compromiso
-                               m.comprometer_con(*ph);
+                               m.comprometer_con(*ph); // O(N)
                        }
                        else
                        {
                                // estamos mejor con nuestra pareja actual, asi
                                // que no hacemos mas que rechazar a todos
                                // (incluyendo el mejor candidato)
-                               for (Persona::ofertas_type::iterator i
+                               for (Persona::ofertas_type::iterator i // O(N)
                                                = m.ofertas.begin();
                                                i != m.ofertas.end(); ++i)
-                                       (*i)->rechazos.push_back(&m);
-                               ph->rechazos.push_back(&m);
-                               m.ofertas.clear();
+                                       (*i)->rechazos[(&m)->nombre] = &m;
+
+                               ph->rechazos[(&m)->nombre] = &m;
+                               m.ofertas.clear(); // O(N)
                        }
                }
                else
                {
-                       m.comprometer_con(*ph);
+                       m.comprometer_con(*ph); // O(N)
                }
        }
 }
 
 bool
 GaleShapley::
-todos_h_comprometidos() const
+todos_h_comprometidos() const // O(N)
 {
        // FIXME: podemos ver de poner esto adentro de nesima_ronda()
-       for (personas_type::const_iterator ih = hombres.begin();
+       for (personas_type::const_iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
                if ((*ih)->estado != Persona::COMPROMETIDO)
                        return false;
@@ -110,10 +115,10 @@ todos_h_comprometidos() const
 
 void
 GaleShapley::
-casamentear()
+casamentear() // O(N^4.log(N^2))
 {
-       primera_ronda();
-       while (!todos_h_comprometidos())
-               nesima_ronda();
+       primera_ronda(); // O(N^3.log(N^2))
+       while (!todos_h_comprometidos()) // O(N)
+               nesima_ronda(); // O(N^3.log(N^2))
 }
 

diff --git a/src/parser.cpp b/src/parser.cpp
index b5fccb43edb77676ac3b5906b9f59e3cbaba34ef..fa2b16ab09dddbd084024c21800b03d85c9e1435 100644 (file)
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -50,6 +50,9 @@ input(const std::string& filename)
                return false;
        Persona::sexo_type sexo = Persona::M;
        Persona::sexo_type opuesto = Persona::F;
+
+       Susanita::size_type cap = get_n(filename);
+
        std::string l;
        while (std::getline(f, l))
        {
@@ -68,7 +71,7 @@ input(const std::string& filename)
                Persona* pp = susanita.get_persona(nombre);
                if (!pp)
                {
-                       pp = new Persona(nombre, sexo);
+                       pp = new Persona(nombre, sexo, cap);
                        susanita.add_persona(pp);
                }
 
@@ -83,7 +86,7 @@ input(const std::string& filename)
                        Persona* ppp = susanita.get_persona(nombre);
                        if (!ppp)
                        {
-                               ppp = new Persona(nombre, opuesto);
+                               ppp = new Persona(nombre, opuesto, cap);
                                susanita.add_persona(ppp);
                        }
                        pp->prefs.push_back(ppp);

diff --git a/src/persona.cpp b/src/persona.cpp
index e35f0421eca2c879ffc1243601681e508601e340..a8726ab031f4701c42b0a4b465599f25429ed3f2 100644 (file)
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -4,8 +4,8 @@
 
 /// Constructor
 Persona::
-Persona(const std::string& nombre, sexo_type sexo):
-       nombre(nombre), estado(SOLTERO), sexo(sexo), pareja(0)
+Persona(const std::string& nombre, sexo_type sexo, size_type cap):
+       nombre(nombre), estado(SOLTERO), sexo(sexo), pareja(0), rechazos(cap)
 {
 }
 
@@ -60,12 +60,12 @@ operator<< (std::ostream& os, const Persona& p)
 /// Función de comparación entre dos personas según nuestras preferencias
 bool
 Persona::
-cmp(const Persona& p1, const Persona& p2) const
+cmp(const Persona& p1, const Persona& p2) const // O(N)
 {
        prefs_type::const_iterator pos_p1
-               = std::find(prefs.begin(), prefs.end(), &p1);
+               = std::find(prefs.begin(), prefs.end(), &p1); // O(N)
        prefs_type::const_iterator pos_p2
-               = std::find(prefs.begin(), prefs.end(), &p2);
+               = std::find(prefs.begin(), prefs.end(), &p2); // O(N)
        if (pos_p1 < pos_p2)
                return 1;
        if (pos_p1 == pos_p2)
@@ -84,7 +84,7 @@ namespace
                /// devuelve true si p1 < p2
                bool operator ()(const Persona* const p1, const Persona* const p2)
                {
-                       return p.cmp(*p1, *p2) < 0;
+                       return p.cmp(*p1, *p2) < 0; // O(N)
                }
        };
 }
@@ -92,27 +92,28 @@ namespace
 /// Ordenamos las ofertas segun nuestras preferencias
 void
 Persona::
-ordenar_ofertas()
+ordenar_ofertas() // O(N^2.log(N^2))
 {
        // este sort es in-place y O(N.log(N))
        // Más info en: http://www.sgi.com/tech/stl/sort.html
+       // Pero el PersonaCmp() es O(N)
        std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this));
 }
 
 /// Nos declaramos a la persona p
 void
 Persona::
-declarar_a(Persona& p)
+declarar_a(Persona& p) // O(1)
 {
        estado = DECLARADO;
        pareja = &p;
-       p.ofertas.push_back(this);
+       p.ofertas.push_back(this); // O(1)
 }
 
 /// Nos comprometemos con la persona p, quien se nos habia declarado previamente
 void
 Persona::
-comprometer_con(Persona& p)
+comprometer_con(Persona& p) // O(N) ( es O(len(ofertas)) )
 {
        assert(p.estado == DECLARADO);
        assert(p.pareja == this);
@@ -123,7 +124,7 @@ comprometer_con(Persona& p)
                assert(pareja != 0);
                pareja->estado = SOLTERO;
                pareja->pareja = 0;
-               pareja->rechazos.push_back(this);
+               pareja->rechazos[this->nombre] = this; // O(1)
        }
 
        // nos comprometemos
@@ -133,12 +134,12 @@ comprometer_con(Persona& p)
        p.pareja = this;
 
        // si tenemos ofertas, las rechazamos
-       for (ofertas_type::iterator pretendiente = ofertas.begin();
+       for (ofertas_type::iterator pretendiente = ofertas.begin(); // O(N)
                        pretendiente != ofertas.end(); ++pretendiente)
        {
-               (*pretendiente)->rechazos.push_back(this);
+               (*pretendiente)->rechazos[this->nombre] = this; // O(1)
        }
-       ofertas.clear();
+       ofertas.clear(); // O(N)
 }
 
 // Nos comprometemos con la otra persona y a ella la comprometemos con nosotros

diff --git a/src/persona.h b/src/persona.h
index d46090a794b03ac52894e0bec62b229cb57bf007..f9ab9121c433c050e29611836d2a08417cdba612 100644 (file)
--- a/src/persona.h
+++ b/src/persona.h
@@ -5,13 +5,15 @@
 #include <string>
 #include <ostream>
 #include <istream>
+#include "hashtable.h"
 
 struct Persona
 {
        /// Tipos de listas
        typedef std::deque< Persona* > prefs_type;
        typedef std::deque< Persona* > ofertas_type;
-       typedef std::deque< Persona* > rechazos_type;
+       typedef HashTable rechazos_type;
+       typedef HashTable::size_type size_type;
 
        /// Estados posibles de una persona
        enum estado_type { SOLTERO, DECLARADO, COMPROMETIDO };
@@ -20,8 +22,8 @@ struct Persona
        enum sexo_type { M, F };
 
        /// Constructor
-       Persona(const std::string& nombre, sexo_type sexo);
-       
+       Persona(const std::string& nombre, sexo_type sexo, size_type cap);
+
        /// Nombre de la persona, sólo con fines de representación
        std::string nombre;