From 9544fcaa595b6a6f14b86768429c1883fa39ec6d Mon Sep 17 00:00:00 2001 From: Alberto Bertogli Date: Mon, 7 Nov 2005 02:27:35 +0000 Subject: [PATCH] Hacer que todos_h_comprometidos() sea O(1). Usamos una variable propia del GS para contar la cantidad de hombres comprometidos, y cuando esta alcanza a la capacidad, ya estamos. --- src/galeshapley.cpp | 21 ++++++++++++--------- src/galeshapley.h | 6 +++++- 2 files changed, 17 insertions(+), 10 deletions(-) diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp index b50f5bc..494631c 100644 --- a/src/galeshapley.cpp +++ b/src/galeshapley.cpp @@ -16,6 +16,7 @@ void GaleShapley:: primera_ronda() // O(N^2.log(N)) { + cant_comprometidos = 0; for (personas_type::iterator ih = hombres.begin(); // O(N) ih != hombres.end(); ++ih) { @@ -31,6 +32,7 @@ primera_ronda() // O(N^2.log(N)) Persona& prometido = *(m.ofertas.front()); // O(1) m.ofertas.pop_front(); // O(1) m.comprometer_con(prometido); // O(N) + cant_comprometidos++; } } @@ -77,6 +79,8 @@ nesima_ronda() // O(N^2.log(N)) if (m.cmp(*(m.pareja), *ph) < 0) // O(1) { // la oferta es mejor, rompemos el compromiso + // No cambiamos la cantidad de comprometidos + // porque estamos cambiando uno por otro m.comprometer_con(*ph); // O(N) } else @@ -96,29 +100,28 @@ nesima_ronda() // O(N^2.log(N)) else { m.comprometer_con(*ph); // O(N) + cant_comprometidos++; } } } bool GaleShapley:: -todos_h_comprometidos() const // O(N) +todos_h_comprometidos() const // O(1) { - // FIXME: podemos ver de poner esto adentro de nesima_ronda() - for (personas_type::const_iterator ih = hombres.begin(); // O(N) - ih != hombres.end(); ++ih) - if ((*ih)->estado != Persona::COMPROMETIDO) - return false; - return true; + if (cant_comprometidos == capacidad) { + return true; + } + return false; } void GaleShapley:: -casamentear() // O(N^3.log(N)) +casamentear() // O(N^2.log(N)) { primera_ronda(); // O(N^2.log(N)) - while (!todos_h_comprometidos()) // O(N) + while (!todos_h_comprometidos()) // O(1) nesima_ronda(); // O(N^2.log(N)) } diff --git a/src/galeshapley.h b/src/galeshapley.h index ca0ac5d..93f53f0 100644 --- a/src/galeshapley.h +++ b/src/galeshapley.h @@ -11,7 +11,7 @@ struct GaleShapley: Susanita { /// Constructor - GaleShapley(); + GaleShapley(size_type capacidad); /// Empieza a emparejar gente void casamentear(); @@ -41,6 +41,10 @@ struct GaleShapley: Susanita */ void nesima_ronda(); + // Cantidad de hombres comprometidos; se usa para optimizar + // todos_h_comprometidos(). + unsigned int cant_comprometidos; + /// Se fija si todos los hombres estan comprometidos bool todos_h_comprometidos() const; -- 2.43.0