algorytm magicznych piątek

0

Witam,
mam problem z zakodowaniem algorytmu magicznych piątek w języku C++. Znalazłem taki pseudokod z objaśnieniami http://inf.ug.edu.pl/~wpawlowski/08-09/asd-b/sel.html nic lepszego i bardziej szczegółowego nie udało mi się znaleźć. Ale mam kilka pytań co do niego. Jestem w trakcie pisania oto co udało mi się napisać do tej pory (problemy napisałem w komentarzach w kodzie):


bool porownaj(const osoba &a, const osoba &b){
    int leks;
    if(a.pesel < b.pesel) return true;
    else if(a.pesel == b.pesel){
        leks = a.nazwisko.compare(b.nazwisko);
        if(leks > 0) return false;
        else if(leks < 0) return true;
        else{
            leks = a.imie.compare(b.imie);
            if(leks > 0) return false;
            else if(leks < 0) return true;
        }
    }
    else return false;
}

osoba magicznepiatki(vector <osoba> tab, int n, int k){
    osoba m5;
    vector <osoba> M;
    if(n<11){
        sort(tab.begin(), tab.end(), porownaj);
        return tab[k];
    }
    else{
        vector < vector<osoba> > piec;
        piec.resize(n/5);
        for (int i = 0; i < n; i++){//narazie zakładam że n jest podzielne przez 5, dla nie podzielnych kodu jeszcze nie ma;)
            piec[i/5].push_back(tab[i]);
            if(piec[i/5].size() == 5){
                sort(piec[i/5].begin(), piec[i/5].end(), porownaj);
                M.push_back(piec[i/5][2]);
            }
        }
        m5 = magicznepiatki(M, M.size()-1, M.size()/2);// nie rozumiem z pseudokodu jak wyliczany parametr k jest
        vector <osoba> tabm, tabr, tabw;//mniejsze, równe, większe bo z tego co mi się wydaje to muszę zrobić takie tablice
        for (int i = 0; i < n; i++){
            if(porownaj(tab[i], m5))
                tabm.push_back(tab[i]);
            else if(porownaj(m5, tab[i]))
                tabw.push_back(tab[i]);
            else
                tabr.push_back(tab[i]);
        }
        if()//tu się zatrzymałem nie wiem czy da się użyć do porównania komparatora, żeby nie pisać przeciążania operatorów. Nie wiem też ja dokładnie co mam porównać, jakikolwiek element tablicy z parametrem k?
    }

}

Dzięki z góry za pomoc;)

0

Zamiast opisywać co i jak postanowiłem przerobić twój program do działającej postaci,
wszak kod wyraża więcej niż 1000 słów ;)
Dodatkowo żeby nie było niejasności wrzuciłem pare komentarzy.

 struct osoba
{
    int pesel;
    std::string nazwisko, imie;
};

const int adHock = 3;//11

//less
bool mniejsze(const osoba &a, const osoba &b)
{
    if (a.pesel != b.pesel)
        return a.pesel < b.pesel;
    else
    if (a.nazwisko != b.nazwisko)
        return a.nazwisko < b.nazwisko;
    else
        return a.imie < b.imie;

}

osoba magicznePiatki(std::vector<osoba> & tab, int k);

osoba pseudoMediana(const std::vector<osoba> & tab)
{
    std::vector<osoba> M, temp(5);
    //liczba grup - 1
    int n = int(ceil(tab.size()/5.0)) - 1;
    //iterujemy po grupach 5-cio elementowych oprocz ostatniej
        for (unsigned int i = 0; i < n; i++)
        {
            std::copy(&tab[5*i], &tab[5*i+5], &temp[0]);
            std::sort(temp.begin(), temp.end(), mniejsze);
            M.push_back(temp[2]);
        }
    //obsługa ostatniej grupy (może być mniej niż 5)
    int d = tab.size()%5;
    std::copy(&tab[5*n], &tab[5*n+d], &temp[0]);
    std::sort(&temp[0], &temp[d], mniejsze);
    M.push_back(temp[d/2]);

    return magicznePiatki(M, M.size()/2);
}

osoba magicznePiatki(std::vector<osoba> & tab, int k)
{
    assert(0 <= k && k < tab.size());
        if(tab.size() < adHock)
        {
                std::sort(tab.begin(), tab.end(), mniejsze);
                return tab[k];
        }
        else
        {
                //obliczamy pseudomediane
                osoba osMed = pseudoMediana(tab);
                //zbior elementow z tab dzielimy na dwa rozlaczne
                //zbiory tj. mniejsze od osMed i pozostale
                std::vector<osoba> tabMniejsze, tabReszta;
                for (unsigned int i = 0; i < tab.size(); i++)
                        if( mniejsze(tab[i], osMed ))
                            tabMniejsze.push_back(tab[i]);
                        else
                            tabReszta.push_back(tab[i]);
                //2 opcje: albo k-ty wpada do mniejszych (wtedy nadal k-ty)
                // albo do wiekszych-rownych. Wtedy trzeba przeskoczyc przez
                //wszystkie mniejsze (dlatego k zmniejszamy)
                if (k < tabMniejsze.size())
                    return magicznePiatki(tabMniejsze, k);
                else
                    return magicznePiatki(tabReszta, k-tabMniejsze.size());
        }
}

Kilka lużnych uwag co do twojego kodu:

  1. Przekombinowałeś z metodą porównującą osoby, można ją napisać prościej (up). Tak w ogóle to można przerobić ją na operator <.
  2. Pisząc vector <osoba> tab zajedziesz stos, wektory przekazujemy przez referencje. Warto też dodać const o ile można (jak w pseudoMediana) żeby zwiększyć szanse na optymalizacje.
  3. parametr n nie był magicznym piątkom do niczego potrzebny, wektor trzyma swój rozmiar.
  4. Próg poniżej którego nie opłaca się odpalać rekurencji dobieramy eksperymentalnie dlatego dodałem stałą adHock.
  5. Dobrą praktyką jest działanie na kolekcji (tu wektora) wskaźników na obiekty co ogranicza kopiowanie. Osoba trzyma dwa napisy, które mogą być dość długie, a kopiowanie napisów (tutaj wymuszone przez kopiowanie struktur osoba) jest bolesne. Za to czas kopiowania wskaźników jest zaniedbywalny.
  6. Piec oraz pare innych zmiennych można było spokojnie wyrzucić :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0