Pytanie teoretyczne - czas działania programu

0

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.

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.

1

Jeżeli w main'ie miałeś np ++ZmiannaGlobalna; i przeniosłeś to do funkcji to spodziewam się 5-krotnego spowolnienia.
Skoro spowolnienie nie jest aż tak drastyczne to znaczy że w tej funkcji jest nieco więcej kodu le nadal bardzo mało.

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.

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

0

Z funkcją: 2,914 s
Z funkcją + inline: 2,980 s
Bez funkcji: 0,172 s

Znowu chyba czegoś nie rozumiem.

0

No widocznie kompilator zdecydował, że inline to zły pomysł. I jak widać nie ma racji. Pokaż kod oraz dowiedz się jaki kompilator jest używany i z jakimi opcjami, o ile to możliwe.

1

A moze do funkcji przekazujesz jakis ciężki parametr przez wartość? Wektor czy coś? Kopiowanie go moze trwać.

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);
}
1

Najprawdopodobniej winne jest kopiowanie vector.

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.

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 ;)

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ć.

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.

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 ;)

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?

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.

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