SPOJ C++ sortowanie bąbelkowe przekroczono limit czasu

pytanie zadane 19 lipca 2018 w SPOJ przez paweljumper Obywatel (1,260 p.)
edycja 19 lipca 2018 przez paweljumper

Witam, próbuje zrobić zadanie na SPOJ w c++, konkretnie sortowanie bąbekowe, niestety według spoja przekraczam limit czasu. Nie za bardzo wiem jak mogę to poprawić, może ktoś nakieruje?
Kod: https://ideone.com/C31OfD
Zadanie: https://pl.spoj.com/problems/FR_01_09/

komentarz 19 lipca 2018 przez RafalS VIP (122,820 p.)

Wrzuc kod w bloczek, jesli nie wiesz jak to zerknij do faq

komentarz 19 lipca 2018 przez paweljumper Obywatel (1,260 p.)

Z tego co czytałem to zadania ze spoja maja byc ukryte zeby tylko ci ktorzy chca gotowe rozwiazanie mogli kliknac w link, a ci ktorzy chca podpowiedzi przegladaja temat
+ kompilowanie przez strone jest wygodniejsze niz uruchamianie ide na kompie I przekopiowanie kodu

4 odpowiedzi

odpowiedź 19 lipca 2018 przez criss Mędrzec (172,570 p.)

Spróbuj używać jednego vectora, a nie tworzyć nowy przy każdej iteracji - robi ci się niepotrzebny overhead wynikający z potrzeby nie zawsze koniecznego zwalniania i alokowania pamieci. Stwórz wektor bezpośrednio w scopie funkcji main, co iteracje używaj na nim reserve() (lepsze od resize bo nie ma konieczności inicjalizacji indeksów jakąś wartością), a do dodawania elementów używaj push_back().
Po każdej iteracji musisz też czyścić kontener, żeby zresetować indeks pod którym będą się pojawiać elementy po push_back(), więc używaj na vectorze clear() po każdej iteracji. Tutaj trzeba mieć nadzieje, że implementacja std::vector nie będzie zwalniała pamięci. Jeśli nie chcesz na tym polegać, to "ręcznie" nadpisuj indeksy o ile rozmiar vectora jest wystarczający (w przeciwnym wypadku push_back). Możesz sprawdzić czas dla metody z push_back i tej drugiej "ręcznej", bo możliwe że ify konieczne dla drugiej metody stworzą za duży overhead..

komentarz 19 lipca 2018 przez paweljumper Obywatel (1,260 p.)
edycja 19 lipca 2018 przez paweljumper

Niestety nie pomogło :(
BTW nie powinno być albo reserve ALBO push_back? Jeśli dam reserve a potem push_back vector powiekszy sie dwukrotnie o ile sie nie myle...

komentarz 19 lipca 2018 przez criss Mędrzec (172,570 p.)
edycja 19 lipca 2018 przez criss

Hm.. skoro zadanie polega tylko na wypisaniu liczby kroków, to może dałoby się tylko liczyć potrzebne swapy, ale ich nie wykonywać...

Co do pytania - mylisz reserve z resize.
reserve zwiększa ilość pamięci zaalokowanej przez vector, dzięki czemu nie musi realokować (i tutaj odbyłoby to powiększenie dwukrotne [chociaż tego czy to jest dwa razy czy inny stosunek standard nie definiuje]) przy push_back-ach których rezultatem byłoby wyjście poza aktualnie zaalokowany blok pamięci. W skrócie - dzięki reserve() możemy w ogóle pozbyć się realokacji jeśli dokładnie znamy docelową liczbe elementów.
resize() nie tylko zwiększa ilość zaalokowanej pamięci, ale też tworzy na niej elementy zatem cała zaalokowana pamięć jest wykorzystywana. I wtedy faktycznie w wypadku push_back kontener jest zmuszony realokować, bo już nie ma miejsca na nawet ten jeden dodatkowy element.

odpowiedź 19 lipca 2018 przez paweljumper Obywatel (1,260 p.)

odpowiedź 22 lipca 2018 przez paweljumper Obywatel (1,260 p.)

odpowiedź 22 lipca 2018 przez RafalS VIP (122,820 p.)

Spróbuj dodać sprawdzenie czy tablica nie jest posortowana. Najwydajniej można to osiągnąć flagą czyWystapilaZamiana w najbardziej wewnętrznej pętli. Jeśli po przejsciu calej petli nic nie zostało zamienione to znaczy ze tablica jest posortowana i nie ma sensu iterować dalej.

Daj znać czy pomogło :)

EDIT w tym konkretnym przypadku jeszcze szybsze powinno być sprawdzenie czy count sie zmienił po wyjsciu z pętli wewnętrznej.