• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Optymalizacja algorytmu min, maks

Object Storage Arubacloud
0 głosów
337 wizyt
pytanie zadane 14 lutego 2018 w C i C++ przez Kurczak Użytkownik (940 p.)

Cześć, 

Przerabiam sobie książkę o algorytmach i postanowiłem zoptymalizować szukanie wartości minimalnej i maksymalnej zbioru metodą divide & conquer. Zgodnie z książką, porównuję liczby parami, na indeksach parzystych ustawiam większą z liczb, na nieparzystych indeksach wrzucam mniejszą. Później tradycyjną metodą porównuję liczby z nowych podzbiorów.
Niestety gdzieś popełniłem błąd, bo czasy "zoptymalizowaną" metodą są o wiele większe od osiąganych tradycyjną.

KOD

1 odpowiedź

+5 głosów
odpowiedź 14 lutego 2018 przez monika90 Pasjonat (22,940 p.)
edycja 14 lutego 2018 przez monika90
Zoptymalizowana funkcja dwa razy przegląda całą tablicę, a przesłanie tych wszystkich danych z pamięci do procesora zabiera czas. Już na podstawie tego można by się spodziewać, że będzie dwa razy wolniejsza.

Twoja książka pewnie nie bierze pod uwagę takich zjawisk jak hierarchia pamięci czy potokowość i tego jak potokowości szkodzą nieprzewidywalne skoki warunkowe. W ogóle żeby rozumieć kwestie wydajności, to trzeba dobrze znać sprzęt i wiedzieć jaki kod kompilator wygenerował, sama teoria złożoności obliczeniowej nie wystarczy.

Do samego sposobu przeprowadzenia pomiaru też można się przyczepić. Mierzysz nie tylko czas algorytmu, ale też czas  operacji wejścia-wyjścia (wyświetlania wyniku). Druga funkcja działa na innych danych niż pierwsza, bo pierwsza te dane zmieniła. Funkcja clock to chyba nie jest najlepszy sposób pomiaru czasu. I najważniejsze, czy włączyłeś optymalizację (flaga -O2 albo -O3)?
komentarz 14 lutego 2018 przez jpacanowski VIP (101,940 p.)
-O3 lepiej nie używać.
1
komentarz 14 lutego 2018 przez draghan VIP (106,230 p.)

-O3 lepiej nie używać.

Jakieś argumenty? :)

1
komentarz 14 lutego 2018 przez mokrowski Mędrzec (156,220 p.)
Z mojej wiedzy, co do poprawności, owszem były błędy z -O3 ale gdzieś na etapie gcc ~ 2.9/3. Teraz już nie ma powodu bać się -O3 jeśli chodzi o poprawność kodu.

Co do wydajności, powody że może być kiepskie (-O3) to ew. trafienia w cache. Czasem -Os może dawać lepsze wyniki szczególnie na starszych procesorach. Niemniej jednak należy to zmierzyć :-)
komentarz 14 lutego 2018 przez Kurczak Użytkownik (940 p.)

@monika90,
Faktycznie, nie zwróciłem uwagi, że działamy na zmienionej tablicy, jednak nawet jeśli zamienię kolejność wykonywania się funkcji, to "zoptymalizowany" algorytm nadal działa wolniej. Prawdopodobnie nie włączyłem optymalizacji, przyznam szczerze, że pierwszy raz spotykam się z tym terminem.

komentarz 14 lutego 2018 przez jpacanowski VIP (101,940 p.)

Jakieś argumenty? :)

http://www.network-theory.co.uk/docs/gccintro/gccintro_49.html

[-O3] This option turns on more expensive optimizations, such as function inlining, in addition to all the optimizations of the lower levels -O2 and -O1. The -O3 optimization level may increase the speed of the resulting executable, but can also increase its size. Under some circumstances where these optimizations are not favorable, this option might actually make a program slower.

It is important to remember that the benefit of optimization at the highest levels must be weighed against the cost. The cost of optimization includes greater complexity in debugging, and increased time and memory requirements during compilation. For most purposes it is satisfactory to use -O0 for debugging, and -O2 for development and deployment.

komentarz 14 lutego 2018 przez draghan VIP (106,230 p.)

Jpacanowski - źródło pochodzi z 2004 2005 roku, z deczka stare. ;) Zgadzam się, że znajdą się corner-case'y, gdzie optymalizacja poprowadzi do gorszego wyniku, jednak w podręcznikowym sortowaniu, na platformę nie-mikrokontrolerową - nie sądzę.

Oczywiście mokrowski położył tutaj najważniejszą kartę - najpierw zmierzyć, potem podjąć decyzję, co podpowiada prosta inżynierska praktyka. :)

Podobne pytania

0 głosów
0 odpowiedzi 320 wizyt
pytanie zadane 12 stycznia 2018 w C i C++ przez marcin_kub Obywatel (1,420 p.)
0 głosów
1 odpowiedź 793 wizyt
pytanie zadane 2 grudnia 2017 w Python przez nastrand Nowicjusz (150 p.)
+1 głos
1 odpowiedź 322 wizyt

92,761 zapytań

141,685 odpowiedzi

320,483 komentarzy

62,105 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...