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.

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index b50f5bc861591f25a8c2e00c21ebdbc24a9d3cf9..494631cf632f49be945012ac9987e2921f9eab44 100644 (file)
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -16,6 +16,7 @@ void
 GaleShapley::
 primera_ronda() // O(N^2.log(N))
 {
 GaleShapley::
 primera_ronda() // O(N^2.log(N))
 {

+       cant_comprometidos = 0;

        for (personas_type::iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
        {
        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)
                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
                        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
                                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)
                else
                {
                        m.comprometer_con(*ph); // O(N)

+                       cant_comprometidos++;

                }
        }
 }
 
 bool
 GaleShapley::
                }
        }
 }
 
 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::
 }
 
 
 void
 GaleShapley::

-casamentear() // O(N^3.log(N))
+casamentear() // O(N^2.log(N))

 {
        primera_ronda(); // 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))
 }
 
                nesima_ronda(); // O(N^2.log(N))
 }
 

diff --git a/src/galeshapley.h b/src/galeshapley.h
index ca0ac5d795455329eff69e3cdf08951794950d65..93f53f0a34fd7ffc2719ef4b30d3f2881a64b5ba 100644 (file)
--- a/src/galeshapley.h
+++ b/src/galeshapley.h
@@ -11,7 +11,7 @@ struct GaleShapley: Susanita
 {
 
        /// Constructor
 {
 
        /// Constructor

-       GaleShapley();
+       GaleShapley(size_type capacidad);

 
        /// Empieza a emparejar gente
        void casamentear();
 
        /// Empieza a emparejar gente
        void casamentear();


@@ -41,6 +41,10 @@ struct GaleShapley: Susanita
         */
        void nesima_ronda();
 
         */
        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;
 
        /// Se fija si todos los hombres estan comprometidos
        bool todos_h_comprometidos() const;