Największe liczby z partial_sort

0

Cześć.
Mam problem z zadaniem, polega ono na wybraniu z n (1<n<2^20) par liczb i liter, k liter do których zostały przypisane największe wartości np. n=4, k=2.
Wejście:

4
1 a
2 b
3 c
1 d
2

Wyjście:

c
b

Wypróbowałem wiele rozwiązań ale niestety ciągle coś jest nie tak. W poleceniu podkreślono, że rozwiązań może być wiele, ale decydującą role odgrywa czas..

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <array>


using namespace std;


class para
{
public:
    int liczba;
    string litera;
    para( int xliczba, string xlitera );
};

para::para( int xliczba, string xlitera )
    : liczba( xliczba )
     , litera( xlitera )
{

}

bool mniejsze( para &liczba1, para &liczba2 )
{
    return liczba1.liczba > liczba2.liczba;

}
int main()
{

    using namespace std;
    vector < para > n;
    int k,ile_liczb;
    cin>>k;
    for (int i=0;i<k;++i){
        int odp_liczba;
        cin >> odp_liczba;
        string odp_litera;
        cin >> odp_litera;
        n.push_back( para( odp_liczba, odp_litera ) );
    }
    cin >>ile_liczb;
    partial_sort(n.begin(), n.begin() + ile_liczb, n.end(),mniejsze);

    for( int i = 0; i < ile_liczb; i++ )
            {
                cout << n[ i ].litera;
                if (i!=ile_liczb-1) cout<<endl;
            }

    return 0;
}

Proszę o podpowiedź ;)

0

To zadanie dla std::map i std::unordered_map?

0

Zastosowałem algorytm quick_sort, ale mam problem (tak myślę) z kolejnością wypluwanych literek. Chodzi o przypadek gdy pojawią się np pary "2 d" i "2 e". Co zrobić aby wysortować tylko k największych elementów, a nie całą tablicę? Mój kod na ideone.com.

0

W tym zadaniu chodzi o to że partial sort Ω(n) ma o wiele lepszą złożoność niż całkowity sort Ω(n log n).
Zastosuj QuickSelect:
https://en.wikipedia.org/wiki/Quickselect

0

Użyłem quick_select, jednak chyba ciągle mój kod jest za wolny. Jak mogę to poprawić?

0

Złożoność twojego pierwotnego algorytmu jest Ok (o(n log k)).
Problem, raczej leży w operacjach IO. Ilość danych wejściowych jest dość duża, więc nie można sobie tu pozwolić na rozrzutność.

Czyli:

  • std::sync_with_stdio(false)
  • std::cin.tie(nullptr)
  • zakaz używania std::endl

Inne proste sztuczki, które mogą coś poprawić:

  • zmiana std::string na char (jako, że jest "small string optimalization" raczej dużo nie pomoże).
  • std::vector::reserve zredukuje liczbę alokacji w wektorze do jednego zdarzenia, co powinno pomóc w istotny sposób.

Jakie masz ograniczenia na k?


Rada co do kodowania: * jak zadanie definiuje jakieś symbole, to używaj nazw tych symboli w kodzie tak jak opisano to w zadaniu. Przykładowo to `vector < para > n;` jest sporym utrudnieniem podczas czytania, tak samo `k`, które tak naprawdę pełni rolę `n` z treści zadania.
0

Jeszcze chyba można dodatkowo:

  • zamiast funkcji mniejsze przeładować operator " < " i zdefiniować go od razu w definicji klasy, dzięki czemu zajdzie implicit inline request
  • wstawić const wszędzie tam gdzie to możliwe
  • użyć reserve(k) dla vectora (edit: nie zauważyłem, że zostało to już zasugerowane przez MarekR22)
1
MarekR22 napisał(a):

Jakie masz ograniczenia na k?

(1 <= K <= 2^20)

Dziękuję za porady. Zastosowanie pierwotnego algorytmu + porad MarekR22 pomogło. Zastosowałem też printf i scanf. Właściwie nie wiem co miało decydujący wpływ, w wolnej chwili postaram się to dokładnie przebadać.
Dla osiołków takich jak ja podpowiadam, że wczytując należy pamiętać o pomijaniu białych znaków np.

scanf(" %d",&x) //spacja !!
0

Jeśli chcesz poeksperymentować, to:

  1. uruchom kod poniżej i sprawdź ile kopii zostanie utworzonych (np. dla danych wej. z pierwszego postu)
class para
{
	public:
		int liczba;
		string litera;
		para(int xliczba, string xlitera);
		para(const para &p);
};
para::para(int xliczba, string xlitera) : liczba(xliczba), litera(xlitera)
{
         cout << "tworzę: " << xliczba << " " << xlitera << endl;
}
para::para(const para &p)
{
         liczba = p.liczba;
         litera = p.litera;
         cout << "kopiuję: " << p.liczba << " " << p.litera << endl;
}
bool mniejsze(const para &liczba1, const para &liczba2)
{
         cout << "porównuję: " << liczba1.liczba << " do " << liczba2.liczba << endl;
         return liczba1.liczba > liczba2.liczba;
}
int main()
{
       // ... bez zmian 
}
  1. wstaw n.reserve(k) po cin>>k i porównaj z poprzednim wynikiem (dla tych samych danych wejściowych)
  2. można też wymusić na funkcji sortującej brak kopiowania przez move semantics, ale ta opcja jest dostępna od C++11
class para
{
public:
         int liczba;
         string litera;
         para( int xliczba, string xlitera );
         para(const para &p) = delete;
         para(para &&p) = default;
         para& operator =(para &&p) = default;
};
para::para( int xliczba, string xlitera ) : liczba( xliczba ), litera( xlitera )
{
         cout << "tworzę: " << xliczba << " " << xlitera << endl;
}
//para::para(const para &p)
//{
         //liczba = p.liczba;
         //litera = p.litera;
         //cout << "kopiuję: " << p.liczba << " " << p.litera << endl;
//}
bool mniejsze(const para &liczba1, const para &liczba2 )
{
         cout << "porównuję: " << liczba1.liczba << " do " << liczba2.liczba << endl;
         return liczba1.liczba > liczba2.liczba;
}
int main()
{ 
        // ... bez zmian 
}

Niech ktoś mnie poprawi jeśli coś pomieszałem :)

0

`Witajcie, robię dokładnie to samo zadanie, jednak w czystym C :)
Docelowo wyznaczam** k-ty element z algorytmu Hoara**, po czym sortuję** QuickSortem** elementy od największego do k-tego. Do znalezienia pivota dzielącego na partycje zawsze używam mediany median z algorytmu magicznych piątek. Wszystko działa poprawnie, jednak podczas weryfikacji zadania również pojawia się problem związany z czasem. Może medianę median powinienem liczyć w osobnej tablicy, a nie poprzez swapowanie wartości w tablicy źródłowej? Czy byłby ktoś w stanie wskazać, co możnaby zoptymalizować, aby całość działała sprawniej?

#include <stdio.h>
 
typedef struct{
    int p;
    char c;
} struktura;
 
void swap(struktura *struc, int i, int j){ // zamiana miejscami elementow tablic
    struktura temp;
    temp = struc[i]; struc[i] = struc[j]; struc[j] = temp;
}
 
void insertsort(struktura *zadania, int left, int right){ // insert sort do sortowania piecioelementowych czesci tablic
    int i, j;
    struktura temp;
    for(j = right-1; j>=left; j--){
        temp = zadania[j];
        i=j+1;
        while(i<=right && temp.p > zadania[i].p){
            zadania[i-1] = zadania[i];
            i++;
        }
        zadania[i-1] = temp;
    }
}
 
int magic_fives(struktura *zadania, int left, int right){ // funkcja zwraca index elementu będącego medianą median 5-elementowych podzbiorów
    int left2 = left, right2 = left+4, i=left, med; // left2 i right2 - skrajne wartosci 5-elem. podzbiorow
   
    if(right-left<5){ // gdy zostało tylko 5 lub mniej median po rekurencji...
        insertsort(zadania, left, right); // ... posortuj ten zbiór...
        return (left+right)/2;  //... i zwróć jego element środkowy - jest to MEDIANA MEDIAN
    }
   
    else{ // instrukcje dla 5-elementowych podzbiorów:
        while(right2<=right){
            insertsort(zadania, left2, right2);
            swap(zadania, i, left2+2); // medianę przesuń na początek analizowanego przedziału...    
            i++; // ... pozycja następnej mediany będzie o 1 większa
            left2 += 5; // wyznaczenie lewej granicy kolejnej piątki
            right2 += 5; // wyznaczenie prawej granicy kolejnej piątki
        }
   
        if(left2<=right){ //  sprawdzimy jeszcze, czy w ogóle zostały jakieś elementy, z których jeszcze wyznaczymy ostatnią medianę
            insertsort(zadania,left2,right);
            swap(zadania, i, (left2+right)/2);
            i++;
        }  
        return magic_fives(zadania, left, i-1); // wyznaczenie mediany median od 0 do i-1, gdzie 'i-1' to index ostatniej wyznaczonej mediany
    }  
}
 
int partition(struktura *zadania, int pocz, int j){
    int med_index = magic_fives(zadania, pocz, j);  // podzial zawsze względem mediany median
    swap(zadania, med_index, pocz); // mediana median na poczatek
    int i = pocz;
    while(i<j){
        while(zadania[i].p<=zadania[pocz].p) i++;
        while(zadania[j].p>zadania[pocz].p) j--;
        if(i<j) swap(zadania, i, j);
    }
    swap(zadania,pocz,j);
    return j; // index pivota
}
 
void quick_sort(struktura *zadania, int lewy, int prawy){
    int i = lewy, j = prawy;
    int x = zadania[magic_fives(zadania,i,j)].p; // podzial zawsze względem mediany median
    do {
        while((zadania[i].p < x) && (i <= prawy)) i++;
        while((zadania[j].p > x) && (j > lewy)) j--;
        if(i <= j){
            swap(zadania, i, j);
            i++; j--;
        }
    } while (i <= j);
    if(lewy < j) quick_sort(zadania, lewy, j);
    if(i < prawy) quick_sort(zadania, i, prawy);
}
 
int main(void){  
    int n, k, ki, j, i, pivot, a;
    scanf("%d", &n);
    struktura zadania[n];
    for(a=0;a<n;++a) scanf("%d %c", &zadania[a].p, &zadania[a].c);
    scanf("%d", &k); // chcemy znaleźć k-ty element i posortować wszystkie od niego większe
    j=n-1; i=0;
    pivot = partition(zadania, 0, j); // pivot (w tym wypadku mediana median) - na lewo od niego przerzucam liczby mniejsze, na prawo wieksze - zwraca nam jego index
    ki=n-k; // liczymy od końca (k-ty element ma index: n-k)
 
    while(ki!=pivot){  //zasada jest prosta - jeśli index pivota jest inny niż index k-tego elementu, wykonuj pętlę while
        if(pivot<ki) i = pivot+1; // nasze nowe i musi być jedną pozycję na prawo od pivota
        else j=pivot-1;
        pivot = partition(zadania, i, j);
    }
    quick_sort(zadania, ki, n-1);
    for(a=n-1;a>=pivot;a--) printf("%c\n", zadania[a].c);
    return 0;
}
0

Docelowo wyznaczam k-ty element z algorytmu Hoara, po czym sortuję QuickSortem

Po co ci k-ty element z algorytmu Hoara? Nawet wiki mówi, że wystarczy tylko nieco zmodyfikować QuickSort

0

Algorytm Hoarea, o którym pisałem, to jest przecież zmodyfikowany quicksort w rzeczywistości. Opiera się na sprawdzaniu, czy indeks pivota po podziale na partycje jest indeksem k-tego elementu. Tak to przynajmniej rozumiem.

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