Rozwiązanie zadania Sort 1 na serwisie SPOJ - Ocena mojego kodu

pytanie zadane 21 września 2019 w C i C++ przez Teslum_369 Gaduła (4,190 p.)

Witam,

Udało mi się rozwiązać zadanie na SPOJ'u z czego (chyba zawsze) się cieszę, gdy widzę już ten zielony prostokącik.

Chciałem poprosić was o ocenę mojego kodu, z perspektywy bardziej doświadczonych programistów. Jeżeli macie jakieś rady do mnie, co mógłbym poprawić / coś co mogło podnieść moją wydajność kodu w przyszłości to śmiało piszcie. Jestem otwarty na krytykę, a to tylko pozwoli mi się zbliżyć do lepszych nawyków pisania.

Link do zadania ze spoju:

https://pl.spoj.com/problems/PP0506A/

Link do mojego rozwiązania:

http://wklejto.pl/766267

Z góry dziękuję za odpowiedzi :)

komentarz 21 września 2019 przez tkz Nałogowiec (42,000 p.)

Przestrzeń nazw, nie wymyślaj koła na nowo, skorzystaj z stl, usuń zbędne nagłówki i to

return EXIT_SUCCESS;

komentarz 21 września 2019 przez Teslum_369 Gaduła (4,190 p.)

Masz rację z nagłówkami. Modyfikowałem kod przed wysłaniem go na spoja i zapomniałem wyrzucić algorithm i vector.

Dzięki za spostrzeżenie

1 odpowiedź

odpowiedź 21 września 2019 przez mokrowski Mędrzec (155,460 p.)
wybrane 22 września 2019 przez Teslum_369

Najlepsza

1. name to 1 znak a nie std::string

2. Współrzędne mieszczą się w zakresie short int.

3. Sortowanie bąbelkowe nie jest tu optymalne. Zerknij do <algorithm>.

4. Zbędne jest obliczanie pierwiastka bo możesz porównać wyłącznie sumy kwadratów.

5. W rozwiązaniu cieknie Ci pamięć. Robisz alokację dynamiczną a nie zwalniasz pamięci. Gdzie delete?

6. Wielkości tablic nie mogą być (poprawne) ujemne. Po co int jako wielkość?

7. Tak separatory jak i nowa linia to znak a nie string. Stosuj ' ' (apostrofy) a nie " (cudzysłowie).

8. Kwadrat odległości od początku układu współrzędnych możesz obliczyć już po wczytaniu danych aby nie liczyć go za każdym razem przy sortowaniu.

9. Wciągasz <vector> a później nie używasz?

Pokaż 6 poprzednich komentarzy

komentarz 21 września 2019 przez Teslum_369 Gaduła (4,190 p.)

Nie wiem czy szybciej, bo zarówno w moim jak i w twoim rozwiązaniu jest jest tabelka time: 0.00. Jedyna różnica, to taka, że mój program ma w tabelce MEM: 4.4MB, a twój 4.3MB, więc faktycznie jest lepszy. Dziena za pomoc i za rady / krytykę :)

komentarz 21 września 2019 przez mokrowski Mędrzec (155,460 p.)

Z całą pewnością szybciej. To wynika z gospodarki pamięcią typowego OS'a. Na stosie ma inne algorytmy alokowania i łatwiej trafia z cache w pamięć. Tylko program jest poniżej rejestrowanego czasu wykonania. A różnica 0.1MB także nie jest wiążąca (w granicach błędu). Za to program jest z całą pewnością prostszy. Jeśli to nie jest absolutnie niezbędne, unikaj alokacji dynamicznej w każdej postaci (tu nawet std::vector nie był potrzebny).

komentarz 22 września 2019 przez Teslum_369 Gaduła (4,190 p.)

Czyli na ogół nie używać dynamicznych tablic tak jak i std::vector? Ten kontener również z tego korzysta, także zalecasz używanie tablic statycznych?

komentarz 22 września 2019 przez mokrowski Mędrzec (155,460 p.)

Jeśli się da, to alokować na stosie i/lub statycznie. Takie alokacje są deterministyczne i dają większą kontrolę nad gospodarką zasobami. Alokacja na stercie, jest nideterministyczna ale daje możliwość alokowania większej pamięci. Stąd jeśli wiesz jakiej wielkości ma być np. kontener, po co vector jak może być std:;array lub zwykła tablica?

Poza tym ciągłe alokacje dynamiczne, fragmentują pamięć a to może być problem.

Pamiętaj że odpowiadam w kontekście spoj'a. Jeśli to np. aplikacja w Qt, nie optymalizuj na siłę: )