X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/blobdiff_plain/eda6c3de95b70888e567be5f4bca0ccfa7518ec0..7c555835b280bcbc38f170ba3b0afc33b1be43c7:/src/galeshapley.cpp diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp index 613c8b7..5667dfe 100644 --- a/src/galeshapley.cpp +++ b/src/galeshapley.cpp @@ -7,37 +7,41 @@ #include GaleShapley:: -GaleShapley() +GaleShapley(size_type capacidad): + Susanita(capacidad) { } void GaleShapley:: -primera_ronda() +primera_ronda() // O(N^2) { - for (personas_type::iterator ih = hombres.begin(); + cant_comprometidos = 0; + 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(); + + // En total es O(N)*(O(N) + O(log(N))) = O(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& prometido = *(m.ofertas.front()); - m.ofertas.pop_front(); - m.comprometer_con(prometido); + Persona* prometido = m.pop_oferta(); // O(log(N)) + m.comprometer_con(*prometido); // O(N) + cant_comprometidos++; } } void GaleShapley:: -nesima_ronda() +nesima_ronda() // O(N^2) { - for (personas_type::iterator ih = hombres.begin(); + // Todo el for es O(N^2) + for (personas_type::iterator ih = hombres.begin(); // O(N) ih != hombres.end(); ++ih) { Persona& h = **ih; @@ -45,75 +49,80 @@ 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^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(); + Persona* ph = m.pop_oferta(); // O(log(N)) if (m.estado == Persona::COMPROMETIDO) { - if (m.cmp(*(m.pareja), *ph) < 0) + if (m.cmp(*(m.pareja), *ph) < 0) // O(1) { // la oferta es mejor, rompemos el compromiso - m.comprometer_con(*ph); + // No cambiamos la cantidad de comprometidos + // porque estamos cambiando uno por otro + 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;//O(1) + + ph->rechazos[(&m)->nombre] = &m; + m.ofertas.clear(); // O(N) } } else { - m.comprometer_con(*ph); + m.comprometer_con(*ph); // O(N) + cant_comprometidos++; } } } bool GaleShapley:: -todos_h_comprometidos() const +todos_h_comprometidos() const // O(1) { - // FIXME: podemos ver de poner esto adentro de nesima_ronda() - for (personas_type::const_iterator ih = hombres.begin(); - ih != hombres.end(); ++ih) - if ((*ih)->estado != Persona::COMPROMETIDO) - return false; - return true; + if (cant_comprometidos == capacidad) { + return true; + } + return false; } void GaleShapley:: -casamentear() +casamentear() // O(N^4) { - primera_ronda(); - while (!todos_h_comprometidos()) - nesima_ronda(); + primera_ronda(); // O(N^2) + + // El bucle podría correrse (haciendo una estimación bruta y + // poco realista) N*N veces, así que sería en total O(N^4) + while (!todos_h_comprometidos()) // O(1) + nesima_ronda(); // O(N^2) }