Na co zwrócić uwagę przy przyśpieszeniu programu

pytanie zadane 17 maja 2017 w C i C++ przez dkarski Obywatel (1,610 p.)

Cześć, na co zwrócilibyście uwagę, by pisane programy działały szybciej? Zacząłem rozwiązywać problem na SPOJ, ale mój kod okazuję się chyba zbyt długi, bo nie przechodzi testu.

Link do kodu: http://ideone.com/gQZOoO (błąd typu: SIGABRT)

2 odpowiedzi

odpowiedź 17 maja 2017 przez adrian17 Ekspert (344,860 p.)
wybrane 18 maja 2017 przez dkarski

Najlepsza

Tu nie ma żadnej kwestii szybkości, ten program po prostu nie działa. Nie czyta wejścia po pierwszej liczbie, po czym próbuje się odwołać do pierwszego elementu tablicy; co wywołuje SIGABRT.

(zakładając, że pierwszym wejściem programu jest liczba, a kolejne rzeczy są w kolejnych liniach. Nie pokazałeś tekstu zadania.)

Spróbuj zamienić cin.sync() na cin.ignore().

(a odpowiadając na tytułowe pytanie: przy optymalizowaniu, profiluj.)

Pokaż 6 poprzednich komentarzy

komentarz 18 maja 2017 przez dkarski Obywatel (1,610 p.)

Adrian,

dzięki za przyjrzenie się kodowi. Utworzyłem tablicę na 1000 elementów ze względu na warunek, które zadanie mi stawia.

W zadaniu mam zapisane.: "The input consists of N cases (equal to about 10000).".

komentarz 18 maja 2017 przez adrian17 Ekspert (344,860 p.)
edycja 18 maja 2017 przez adrian17

Ale wciąż to, że jest X przypadków na wejściu, nie oznacza że potrzebujesz jakąkolwiek tablicę na ich przetrzymywanie - patrz kod powyżej.

komentarz 20 maja 2017 przez dkarski Obywatel (1,610 p.)

Adrian,

ok rozumiem. Zastanawiam się zatem jak zebrać od klienta wejścia -> przetworzyć -> ( i ) wypisać. Jak bez tablicy wypisać przetworzone dane po zebraniu pierw w pierwszej kolejności wejścia. Rozumiem, tak jak SPOJ przedstawia w zadaniu, że pierw wpisujemy wszystkie inputy ( max 1000), później je odpowiednio wyświetlamy. Co myślisz Adrian? Twoje podejście wydaję mi się bardzo rozsądne, obawiam się tylko, że chyba nie pasuję akurat do tego przypadku. Może jestem w błędzie, więc chętnie spróbuję zrozumieć Twój tok myślenia :)

komentarz 20 maja 2017 przez adrian17 Ekspert (344,860 p.)

Dokładnie tak jak napisałem wyżej:

for(int i = 0; i < count; i++) {
    cin >> rzecz;
    // pracuj na rzeczy
    cout << wynik;
}

To jest typowy i poprawny sposób pisania kodu działającego na X niezależnych przypadków; Twoja metoda z tablicą jest tą przekombinowana, nie na odwrót ;)

komentarz 23 maja 2017 przez dkarski Obywatel (1,610 p.)

ok, działa. Rzeczywiście, przekombinowałem. Ach ta moja nadęta chęć wiedzenia lepiej. Dzięki Adrian :)

odpowiedź 17 maja 2017 przez Benek Szeryf (90,870 p.)

Cześć, na co zwrócilibyście uwagę, by pisane programy działały szybciej?

Napiszę ogólnie. Zwróciłbym uwagę na algorytm. Czasem sprawdzanie wszystkich warunków nie ma sensu, możne zrobić pre-selekcję. Przykładowo ostatnio pisałem dwa takie programy, które szukały blisko siebie położonych punktów na płaszczyźnie XY. Nie ma sensu sprawdzać odległości dla każdej z par punktów, bo zabiera to sporo czasu, zwłaszcza jeśli próbka posiada 50 000 punktów. Wystarczy zwrócić uwagę, że jeśli różnica w X (lub w Y) będzie większa niż pewna założona wartość, to od razu wiadomo, że punkty te są odległe. Czyli mamy tutaj taką korzyść, że liczymy tylko różnicę dwóch liczb (x1 - x2) i używamy operatora porównania, zamiast liczyć różnice dwóch współrzędnych, podnosić je do kwadratu, sumować, a potem pierwiastkować. Zastosowałem w swoim programie i mam wyraźne przyspieszenie programu.

Innym przykładem jest optymalizacja podczas sprawdzania warunków. Wracając do przykładu wyżej, jeśli obszar XY będzie prostokątem o znacznych dysproporcjach pomiędzy długościami boków, to sprawdzanie różnic we współrzędnych XY najlepiej rozpocząć od współrzędnych w których bok ma większą długość:

if (|x1 - x2| < d && |y1 - y2| < d) { ... }


    ------------------------
y  |                        | 
    ------------------------
                 x

W ten sposób pierwszy warunek będzie zachodził rzadziej, ponieważ rozrzut współrzędnej X jest większy niż Y. A jak wiemy, jeśli pierwszy warunek koniunkcji nie jest spełniony, to jej wartość jest 0 i komputer nie liczy drugiego warunku.

Kolejną optymalizacją może być obliczenie kolejnych wartości funkcji okresowych w sposób iteracyjny. Inny przykład, zamiast liczyć wiele wartości sinusa w wąskiej przeciwdziedzinie za każdym razem, można policzyć wartości na brzegach i interpolować je prostą. W przypadku badania zmian wielomianu wysokiego rzędu można operować na jego pochodnej, a więc zmniejszyć rząd o jeden.

komentarz 17 maja 2017 przez adrian17 Ekspert (344,860 p.)

(ale najlepiej najpierw profilować)

komentarz 17 maja 2017 przez dkarski Obywatel (1,610 p.)

Benek, dzięki za wiadomość. Rozumiem co chcesz przekazać.

komentarz 17 maja 2017 przez Pajdas Mądrala (5,930 p.)

Benek, to odejmowanie pozycji punktów też nie jest tak bardzo wydajne.
Przy 5 punktach (A,B,C,D,E) musisz wykonać operację odejmowania 10 razy

A-B,
A-C,
A-D,
A-E,
B-C,
B-D,
B-E,
C-D,
C-E,
D-E,

,ale przy 50'000 musisz wykonać 1'249'975'000, jak się nie mylę

P.S wynik moich obliczeń to wynik sprawdzania każdego obiektu z każdym, i został wyliczony wzorem:

n(n-3)/2 + n,

czyli liczba przekątnych wielokąta, oraz liczba kątów

Kolizję można sprawdzać bardziej sprytnymi metodami np. quadtree (w trójwymiarze octree)

komentarz 17 maja 2017 przez Benek Szeryf (90,870 p.)

Chodziło mi o pokazanie na palcach procesu optymalizacji. Oczywiście można to zrobić jeszcze lepiej. Na przykład na moje potrzeby odejmowanie jest zadowalające, wiem z jakimi danymi będę pracował (liczebność) i ułamki sekund, w czasie którym wykonuje się program, są dla mnie akceptowalne. Poświęcam energię na kolejne programy, zamiast optymalizować bez końca jedną aplikację.

komentarz 17 maja 2017 przez Pajdas Mądrala (5,930 p.)

zgadza się, ale ilość obliczeń potrzebnych do większej ilości punktów rośnie bardzo szybko. Zależy do czego to jest używane, ale nie jest to element, który można potraktować po macoszemu, szczególnie kiedy podałeś przykład 50000.

może rzeczywiście w tym przypadku nie jest to istotne, ale uważam, że jeżeli optymalizujesz kod w celu zmniejszenia liczby operacji ok. pięciokrotnie, to nie rozumiem dlaczego nie chcesz "poświęcić energii" na przyspieszenie go np. stukrotnie (czym więcej obiektów tym większy interwał ilości operacji będzie między twoją metodą a np. quadtree)

albo optymalizujemy dobrze (stukrotnie lepiej) albo wcale (a nie 5 krotnie), dlaczego?

ponieważ przy małej ilości operacji 5 krotne przyspieszenie nie będzie robić prawie żadnej różnicy, a przy dużej ilości operacji, owszem czas będzie 5 razy krótszy, ale między niezauważalną zmianą w szybkości przy mniejszych ilościach punktów, a kolosalnie szybko wydłużającym się czasem oczekiwania na wykonanie algorytmu jest bardzo cienka nić.

Optymalizujmy kiedy ma to sens, albo nie optymalizujmy wcale.

(nikogo nie krytykuję, mam takie zdanie i jeżeli ktoś się nie zgadza ze mną to proszę o poprawką, bo mogę się przecież mylić jak każdy z nas)

komentarz 17 maja 2017 przez Benek Szeryf (90,870 p.)

Optymalizujmy kiedy ma to sens, albo nie optymalizujmy wcale.

No właśnie miało to sens. Co prawda mamy nadal tyle samo par punktów do zbadania, ale wstępna pre-selekcja ograniczyła się do prostego odejmowania dwóch liczb zmiennoprzecinkowych. Pierwotnie robiłem to tak, że liczyłem odległości wg twierdzenia Pitagorasa. Czyli musiałem wykonać odejmowanie (tylko że już dwóch współrzędnych, nie jednej), znów dodawanie tych różnic, potem potęgowanie i na koniec operację pierwiastkowania dla każdej pary punktów. A te dwie ostatnie operacje po optymalizacji okazały się zbędne. Z tego co kojarzę, to czas wykonywania programu zmalał 1000-krotnie, bo zasoby były pożerane przez pierwiastkowanie i potęgowanie.

Podsumowując, ja nie zwiększyłem 5-krotnie wydajności programu, tylko 100 - 1000. Ale ostatnio używałem programu, który został zoptymalizowany tylko częściowo i zamiast 20 minut, wykonywał się w około 5. Dla mnie to i tak było dużo lepsze rozwiązanie, bo mogłem przebadać więcej obiektów.

Jeśli mówisz o takiej głębokiej optymalizacji to ona ma sens, gdy czas potrzebny do wykonania zadania jest naprawdę długi (rzędu dni) albo jak piszemy moduły do programów, np. projekt ATLAS lub moduły NumPy. Ale w takim wypadku najlepiej skorzystać z pomocy matematyków.