Czy ktoś jest w stanie mi wytłumaczyć, dlaczego napisane przeze mnie zadanie konkursowe (OI) z wywoływaniem funkcji dla pewnego testu działa 2,914 s, a jak wrzuciłem tę funkcje do maina (tzn nie wywołuje jej, jest wszystko w mainie) to mam czas dla tego samego testu 0,172 s? To normalne? Jeszcze cięzko mi w to uwierzyć.
Dodam, ze funkcje jest wywoływana bardzo wiele razy. Mam na myśli BARDZO wiele.
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
C++ edytowany 2x, ostatnio: pingwindyktator
- Rejestracja:około 22 lata
- Ostatnio:ponad rok
1
Czas wykonania ciała funkcji jest mniejszy, niż czas wejścia do niej i powrotu do miejsca wywołania.
Takie coś oznacza, że funkcja powinna zostać wstawiona w miejscu wywołania (inline expansion) ale kompilator z jakiegoś powodu tego nie zrobił. W tagach napisałeś C++ - nie wiem jakie optymalizacje są włączone w tym, co kompiluje na OI, ale dodaj do funkcji inline - może (podkreślam - może) pomoże.
edytowany 1x, ostatnio: Endrju
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
0
@zonkoo22 jest możliwe, patrz jw. Odpal to sobie z profilerem (np. gprof) i zobaczysz jak to wygląda. Dostaniesz tam rozpiskę ile razy jakaś funkcja sie woła, ile trwa jej działanie na jedno wywołanie i ile w sumie i zobaczysz co ci zjada czas. Ale zapewne faktycznie funkcja jest mała i jednocześnie nie jest inlinowana.
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
Optymalizacja kodu jest chyba na najwyzszym poziomie.
Była przenoszona zmienna globalna. Spowolnienie jest OGROMNE. Dla innego testu:
z funkcją: 48,137s
bez funkcji: 0,619s
A w funkcji była jedna linijka. Złożonosc samej funkcji to 2log2(n) + 1
edytowany 1x, ostatnio: pingwindyktator
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
Z funkcją: 2,914 s
Z funkcją + inline: 2,980 s
Bez funkcji: 0,172 s
Znowu chyba czegoś nie rozumiem.
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
A moze do funkcji przekazujesz jakis ciężki parametr przez wartość? Wektor czy coś? Kopiowanie go moze trwać.
ubiegłeś mnie :)
aż tak długo? Przecież rożnice są ogromne.
Nie widziałem ostatniego posta, nvm. Podejrzewałem, że masz tymczasową zmienną lokalną w funkcji dużych rozmiarów. każde wywołanie funkcji tworzy i zwalnia taki obszar.
No zaczynam powoli rozumieć te diametralne rożnice.
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
Kompilator to g++. Nie do końca wiem, z jakimi opcjami jest używany, ale komendy kompilujące to:
qmake [sciezka do projektu] -r -spec linux-g++ CONFIG+=debug CONFIG+=declarative_debug CONFIG+=qml_debug
make in [sciezka]
To komendy z Qt Creator - srodowiska na linuxie.
Moge wrzucić kod funkcji, całego programu nie bo chyba okazał się wzorcówką do zadania na OI.
typedef unsigned int ui;
inline ui rozmiar(ui a, ui b, vector<ui> tb, ui last)
{
if(b<tb[0]) return 0;
if(a>tb[last]) return 0;
return upper_bound(tb.begin(),tb.end(),b)-lower_bound(tb.begin(),tb.end(),a);
}
edytowany 1x, ostatnio: pingwindyktator
Zobacz pozostałe 2 komentarze
Nie jest. To dokładnie to samo a nie musisz przekazywać kolejnego parametru.
I tak tej funkcji już nie ma, bo tylko problemy sprawiała. Ale skoro to to samo to właściwie nie po to i tak liczyłem rozmiar kazdego wektora i wpisywalem do listy, zeby liczyć poźniej jeszcze raz xd
Co liczyłeś?
std::vector zna swój rozmiar i niczego nie trzeba liczyć.
Czyli moge ciągle odwoływać się do vec.size() i bedzie to tak szybkie jak na początku zliczenie długosci tych vectorów do jakiejs tablicy?
Zmierz. :-) (Tylko w miarę rzetelnie - wiele pomiarów i średnia)
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
Jak dodałem na początku funkcji return 0 (czyli funkcja od razu zwraca 0 - nie jest de facto wykonywana) to czas był o wiele, wiele lepszy. Wiec chyba faktyczne przenoszenie argumentów wszystko tutaj psuje.
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
Jak dałeś return 0 to pewnie kompilator w ogóle tą funkcję olał :P sprawdziłbym to potem w kodzie asemblera ;) Ale kopiowanie tego wektora zapewne zjada kupę czasu, szczególnie jak jest duży ;]
Dla testu: zamiast vector<ui> daj vector<ui>& i zobacz co się stanie ;)
- Rejestracja:ponad 20 lat
- Ostatnio:4 miesiące
0
zamienienie ui rozmiar(ui a, ui b, vector<ui> tb, ui last) na ui rozmiar(ui a, ui b, vector<ui>& tb, ui last) powinno załatwić sprawę - tzn. przyśpieszyć.
Ponieważ wektor nie jest modyfikowany powinno być
const std::vector<ui> &tb.
@Endrju const przespiesza algorytm?
Raczej nie, chociaż
const to może być okazja do dodatkowych optymalizacji. Bardziej chodzi o dobre praktyki.
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
A co to jest, niech ktos mi powie jeszcze ;p
Czasy:
bez funkcji: 0,619 s
z funkcją z &: 0,775 s
z funkcją: 48,783 s
Faktycznie - diametralna rożnica.
edytowany 3x, ostatnio: pingwindyktator
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
Jak masz po prostu vector<ui> to wykonujesz lokalną kopię tego wektora na potrzeby funkcji. Jak masz tam & to przekazujesz do funkcji referencje do tego vectora, czyli de factor oryginał. Jeśli go zmienisz wewnątrz funkcji to poza nią też się zmieni. Ale nie musisz go kopiować dzięki temu ;)
@Shalom dla kazdej zmiennej moge takie referencje zrobic? Bo mam "błąd:declaration of 'zmienna' as array of references" przy
void brut(const ui & zmienna[], ui poczatek, ui koniec)
- Rejestracja:ponad 12 lat
- Ostatnio:20 dni
- Lokalizacja:Kraków
- Postów:1055
0
Okej, już wszystko rozumiem. Nie spodziewałem się az takiego spowolnienia ;p
Ostatnie pytanie: comparsion between unsigned and signed integer jest groźne? Moge to zostawić, czy zmodyfikować lepiej?
edytowany 1x, ostatnio: pingwindyktator
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
Ostatnie pytanie: comparsion between unsigned and signed integer jest groźne? Moge to zostawić, czy zmodyfikować lepiej?
Zależy jak duże pętlę kręcisz ;) Ja bym jednak zamiast "int" w pętli dał "unsigned int"/size_t albo użył iteratora i będzie po kłopocie.
dla kazdej zmiennej moge takie referencje zrobic? Bo mam "błąd:declaration of 'zmienna' as array of references" przy void brut(const ui & zmienna[], ui poczatek, ui koniec)
Daj tam "ui* zmienna" po prostu.
Tak właściwie czym rożni się ui od ui*? Bo to jest chyba coś lekko innego niż ta & referencja.
A siądziesz ty do jakiego kursu czy będziesz pytał o wszystko? ui* to wskaźnik (czyli coś co przechowuje adres w pamięci komputera) pokazujący na unsigned inty. "Typ" tego wskaźnika mówi tyle że jak zrobisz ui[10] to komputer sobie policzy że 10 element unsigned int jest 40 bajtów dalej od adresu pokazywanego przez ui. Tablice w c/c++ są spójnymi fragmentami pamięci więc można sobie po nich tak skakać wskaźnikami. A tablicę w c/c++ można sobie legalnie zrzutować w związku z tym do wskaźnika na jej pierwszy element i potem tym wskaźnikiem sobie skakać.
inline?inline costam funkcja(cokolwiek bleble)