From 9d34215ecaec19da3d96f812c72f146c0e332a55 Mon Sep 17 00:00:00 2001 From: Alberto Bertogli Date: Sun, 6 Nov 2005 22:39:20 +0000 Subject: [PATCH] Hacer que Persona.rechazos sea una HashTable y no una deque. Esto elimina el orden O(N) en partes de la nesima_ronda(). --- src/galeshapley.cpp | 75 ++++++++++++++++++++++++--------------------- src/parser.cpp | 7 +++-- src/persona.cpp | 29 +++++++++--------- src/persona.h | 8 +++-- 4 files changed, 65 insertions(+), 54 deletions(-) diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp index 613c8b7..b2f2ac3 100644 --- a/src/galeshapley.cpp +++ b/src/galeshapley.cpp @@ -7,37 +7,39 @@ #include 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 b5fccb4..fa2b16a 100644 --- 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 e35f042..a8726ab 100644 --- 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 d46090a..f9ab912 100644 --- a/src/persona.h +++ b/src/persona.h @@ -5,13 +5,15 @@ #include #include #include +#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; -- 2.43.0