Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

C++ - Optymalizacja iteracji ?

Jakub_30 24 Paź 2016 19:57 1290 34
  • #1 24 Paź 2016 19:57
    Jakub_30
    Poziom 3  

    Witam Forumowiczów,

    nie mam pomysłu jak można zoptymalizować poniżysz kod:

    Kod: c
    Zaloguj się, aby zobaczyć kod

    Na myśl przychodzi mi rekurencja oraz wskaźniki.

    Bardzo proszę o pomoc.

    0 29
  • #2 24 Paź 2016 23:26
    michcior
    Poziom 30  

    Zoptymalizować w jakim kierunku? Szybkości, zajętości kodu, przejrzystość? Nie można tak po prosty optymalizować. Ktoś Ci dał zadanie i walisz na ślepo. Rekurencja jest dobra na danych o strykturze drzewa. A tu masz płasko. Poza tym nazywanie jednej zmiennej pętli S a drugiej s to jakiś masochizm i prośba o kłopoty, wyrwij z korzeniami takie nawyki.

    0
  • #3 25 Paź 2016 11:32
    Jakub_30
    Poziom 3  

    Nie walę na ślepo, to przeze mnie napisany kod. Napisałem że nie mam pomysłu na optymalizację szybkości np do postaci rekurencyjnej czy wskaźnikowej i proszę o pomoc (podpowiedzi, wskazówki). Dziękuję michcior za uwagę, będę pamiętał na przyszłość. Ps. piszesz, że jest płasko, a może da się tak przekształcić kod zeby było z górki przy iteracji rekurencyjnej.

    0
  • Pomocny post
    #4 25 Paź 2016 13:14
    kosmogon
    Poziom 13  

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Jedno sprawdzenie warunku mniej i bez break, którego w pętlach for nie powinno się używać. Uwaga o nazwach zmiennych jest słuszna, ale ja ich nie zmieniłem, żeby nie robić bałaganu - sam możesz to zrobić tak, jak chcesz :)

    0
  • #5 25 Paź 2016 13:52
    Jakub_30
    Poziom 3  

    Dziękuję kosmogon za poświęcony czas, będę testował Twój kod.

    Z tego, co mi wiadomo, to własnie instrukcję break stworzono z myślą o wyjściu z pętli, zatem o co chodzi ?

    0
  • Pomocny post
    #6 25 Paź 2016 16:23
    kosmogon
    Poziom 13  

    Niby tak, ale to nie jest tak zwana dobra praktyka programistyczna. Pętla for służy do wykonania określoną w warunku ilość razy. A w momencie użycia break przerywasz pętlę wcześniej. Jeżeli tak robisz, to lepiej używać while'a, jest to czytelniejsze. A break można też użyć w instrukcji switch i tam już jest niezastępowalny :)

    A gdzieś wykorzystujesz zmienną q? Nie widzę jej nigdzie poza deklaracją i miejscem, w którym przypisujesz do niej wartość s.

    0
  • Pomocny post
    #7 25 Paź 2016 16:36
    Krzysztof Gustaw
    Poziom 23  

    Witam!
    1) Można zamiast wersji tablicowej użyć wersji wskaźnikowej która "jest w ogólności szybsza" - (B.K, D.R Język C), chociaż współczesne kompilatory (a dokładniej ich optymalizatory) są o niebo lepsze niż te w czasach kiedy powstawał ten podręcznik, więc powyższe stwierdzenie może być niebyłe w przypadku zastosowania odpowiedniej optymalizacji ale to już zależy od możliwości użytego kompilatora.
    2) Nieco szybsza jest również preinkrementacja (++s) niż postinkrementacja (s++). Tak samo zamiast: B3[s]+=1 użyłbym: ++B3[s].
    3) Zmienne intensywnie używane proponuję zadeklarować jako rejestrowe. Deklaracje register informuje kompilator, że ta zmienna będzie intensywnie używana i dobrze by było umieścić ją (w miarę możliwości) nie w pamięci ale w szybkich rejestrach maszyny.
    Pozdrawiam
    KG
    PS
    post #4: Nie widzę definicji zmiennej s.

    0
  • #8 25 Paź 2016 18:56
    Jakub_30
    Poziom 3  

    No no, rozumiem kosmogon, zgadza się, przy cases w swich-u, break jest niezastąpiony.
    Przetestowałem kod kosmogona po drobnej modyfikacji i wykonuje się on w prawie tym samym czasie z tendencją na dłużej.
    Tak ,zmienną "q" wykorzystuje w dalszym kodzie ale jeżeli ma ona przeszkadzać w napisaniu efektywniejszego czasowo kodu, to proszę nie uwzględniać zmiennej "q"
    Preinkrementacja nie wpływa zauważalnie na szybkość wykonywania poniższego kodu, jednakże do uwagi się zastosowałem.
    Kod na starcie wykonuje się 550, przy drugiej iteracji i kolejnych 170 sek. ( na starcie duza cześć danych ulega redukcji)a moje oczekiwania to co najwyżej kilka sek. w odniesieniu do tych 170 sek.
    Tabela B1==B3 zawiera 200.000 komórek
    Funkcja iterowana jest 300.000 razy
    Podczas wykonywania proceduralnego kodu, ilość danych w komórkach się zmniejsza, także w czasie kod wykonuje się coraz szybciej.

    Kod: c
    Zaloguj się, aby zobaczyć kod

    0
  • Pomocny post
    #9 26 Paź 2016 21:21
    skierniak
    Poziom 14  

    Witam, od razu ostrzegam dawno nic w c nie pisałem. Można pozbyć się for:

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Jeszcze ewentualnie można by rozpatrywać funkcję abs i zastąpić ją kodem dopasowanym do rozkładu jaki mają przetwarzane dane. Mam tu na myśli coś takiego:

    Kod: c
    Zaloguj się, aby zobaczyć kod


    przy czym zaczynam od wynik > 0 bo wiem, że tak mam np w 80% przypadków itp.

    To tylko takie luźne pomysły. Oczywiście kod traci swoją elegancję, mogą pojawiać się powtórzenia, no ale w tym przypadku: "cel uświęca środki" :).

    Funkcja abs jest zadeklarowana jako inline, ale z tego co pamiętam - kompilator nie musi do tego podejść wg deklaracji więc może też lepiej się upewnić, że tak jest.

    No i jeszcze w związku z powyższym - upewnij się czy kompilujesz do relase z włączoną optymalizacją - wyniki mogą się różnić od wersji debug.

    0
  • #10 26 Paź 2016 21:38
    Jakub_30
    Poziom 3  

    Po testowaniu przedstawiam dwa void-y, wykonują się mniej więcej w tym samym czasie.
    Dziękuję skierniak za poświecony czas, wszyskie Twoje pomysły przetestuje.
    Tak, zgadza się, kilku innych forumowiczów również zwracało mi uwagę by zamienić abs() na if

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Poniższy kod wykonuje się o około 2 sek dłużej od powyższego.
    Kod: c
    Zaloguj się, aby zobaczyć kod

    0
  • Pomocny post
    #11 26 Paź 2016 22:52
    skierniak
    Poziom 14  

    Jakub_30 napisał:
    Po testowaniu przedstawiam dwa void-y, wykonują się mniej więcej w tym samym czasie.
    Dziękuję skierniak za poświecony czas, wszyskie Twoje pomysły przetestuje.
    Tak, zgadza się, kilku innych forumowiczów również zwracało mi uwagę by zamienić abs() na if
    Kod: c
    Zaloguj się, aby zobaczyć kod


    Poniższy kod wykonuje się o około 2 sek dłużej od powyższego.
    Kod: c
    Zaloguj się, aby zobaczyć kod

    ale w kodzie poniżej S=20 a wyżej masz S=14.
    Ile razy w kodzie wywołujesz tą funkcję? - mam tu na myśli czy te czasy, które podajesz to są czasy dla pojedynczego wywołania funkcji czy dla programu gdzie funkcja jest wywoływana x razy?

    Dodano po 8 [minuty]:

    I jeszcze tak sobie patrzę - gdzie mierzysz czasy? Jeśli te tablice są duże to może przekaż je przez referencję.

    Dodano po 21 [minuty]:

    Poprawiam się - chodzi mi o niekopiowanie tych tablic - więc w cpp to wskaźniki jak już pisali koledzy wcześniej :)

    0
  • #12 26 Paź 2016 23:31
    Jakub_30
    Poziom 3  

    Skierniak, nie istotna jest wartość S, może to byc dowolna liczba naturalna >0. W moim przypadku S=14 lub 19. oczywiście przy testowaniu S jest takie samo w różnych wersjach omawianych void.
    Pod uwagę biorę czas jednego wywołania funkcji, a cały kod proceduralny ma zadanie wywołać tę funkcję 300.000 razy pomnożone przez 27 sek(bo tyle czasu wywołuje sie omawiany void) to całe wykonanie kodu zajmie kilkanaście dni. Tablice są odczytywane przez referencje bez kopii.
    Wszystkie alternatywne voidy wykonują się w podobnym czasie, jednakże pierwotna wersja jednka działa najsprawniej.
    Przetestowałem zamianę abs() na if na wszystkich wersjach void i jest POSTĘP.. bo aż bagatela o około 7 sek. szybciej.
    Za nie długo przedstawię wszystkie voidy w wersji if zamiast abs()

    Dodano po 17 [minuty]:

    Czas jednego wykonania poniższej funkcji 20.6 sek

    Kod: c
    Zaloguj się, aby zobaczyć kod

    Czas jednego wykonania poniższej funkcji 20.9 sek
    Kod: c
    Zaloguj się, aby zobaczyć kod


    Mam problem jak w poniższym void zamienić abs() na if. Proszę o podpowiedź.
    Kod: c
    Zaloguj się, aby zobaczyć kod

    0
  • Pomocny post
    #13 26 Paź 2016 23:36
    skierniak
    Poziom 14  

    Jakub_30 napisał:
    Skierniak, nie istotna jest wartość S, może to byc dowolna liczba naturalna >0.

    rozumiem - pisałem to w kontekście pojedynczego pomiaru i tych 2s dłużej. Więcej do zrobienia to i dłużej.

    Biorąc pod uwagę ilość pracy to może logiczne byłoby podjęcie wysiłku w kierunku wykonywania obliczeń równolegle - mam tu na myśli coś jak taski i pararel w c# (wykorzystać wszystkie rdzenie - no chyba, że masz jeden :) ) lub w ogóle przetworzyć na kilku maszynach - zadanie samo w sobie wydaje się być takie, że ładnie można je podzielić (mało danych do przesłania a dużo obliczeń)- zarzucam tylko link w tym kierunku (to oczywiście tylko jedno z wielu rozwiązań, ale kiedyś sprawdzałem i po prostu bardzo szybko się to uruchamia i jest proste) - już nie zbaczam z tematu.

    0
  • #14 26 Paź 2016 23:45
    Jakub_30
    Poziom 3  

    Skierniak, no tak około 1,5 mln komórek w tablicy a biliony iteracji tym samym obliczeń.

    0
  • #15 26 Paź 2016 23:54
    skierniak
    Poziom 14  

    I mogę się mylić, ale na pierwszy rzut oka wygląda, że zależność jest między indeksami tablic a danymi nie - mam tu na myśli, że chyba można spokojnie te tablice podzielić na części i rozesłać parami do przeliczenia.

    0
  • #16 27 Paź 2016 00:20
    Jakub_30
    Poziom 3  

    Skierniak, masz rację, jest zależność jest między indeksami tablic a danymi nie, jednakże tablice po każdym wykonaniu przedmiotowego void są aktualizowane tzn. zmniejsza się ilość komórek do obliczeń, także wraz z kolejnymi wykonaniami void wykonuje się coraz szybciej. 1 wsze wykonanie void jest dużo dłuższe od drugiego (czasy podawałem dla drugiego wykonania) ponieważ po 1 wszym wykonaniu jest duża redukcja (około połowa) komórek które są brane pod uwagę. Z kolei następne wykonania void już odpowiednio po jednej komórce redukuje które są brane pod uwagę do obliczeń.

    0
  • #17 27 Paź 2016 18:11
    Jakub_30
    Poziom 3  

    Podsumowując, mamy 3 różne ciała tego samego voida. Tematu jeszcze nie zamykam, ponieważ czas wykonywania jest zbyt długi i wynosi dla wszystkich ciał voida +/- 20.5 sek. Proszę nadal o pomysł na alternatywne ciała voida, a w szczególności rekurencyjne. Poniżej kod voida.

    Kod: c
    Zaloguj się, aby zobaczyć kod

    0
  • #18 27 Paź 2016 20:07
    skierniak
    Poziom 14  

    Jakub_30 napisał:
    Tematu jeszcze nie zamykam, proszę nadal o pomysł na alternatywne ciała voida, a w szczególności rekurencyjne.


    Czy kod niezakomentowany jest obecnie 'naj'?

    Czy możesz w tym celu przybliżyć naturę argumentów funkcji - B3 - jakimi danymi jest zainicjowana podczas przekazywania do funkcji? Czy są to zera?

    Może jeszcze wywaliłbym deklaracje zmiennych poza funkcję :( - zawsze to coś tam odejdzie (w pojedynczym przebiegu pewnie dużo to nie zmieni, ale może podczas wielu wywołań coś tam zyskasz - zawsze ta pamięć musi być wyszukana, zarezerwowana)

    I jeszcze jedno pytanie - optymalizujesz to czysto akademicko i to ma to być ta funkcja i już? Nie można by operować na strukturze lub klasie (w końcu c++ :)) jako zbiorze powiązanych danych czyli np B1 i B2 i szukać s ( rekurencyjnie :)) od razu przy tworzeniu obiektu?

    I jeszcze q - co to jest? Potrzebujesz s z ostatniego przebiegu for a wcześniejsze cię nie interesują - tak ma być? Pytam bo po prostu tak wygląda dziwnie :).

    Dodano po 20 [minuty]:

    Kod: c
    Zaloguj się, aby zobaczyć kod

    0
  • #19 27 Paź 2016 20:52
    Jakub_30
    Poziom 3  

    Skierniak, trudno powiedzieć które ciało lepsze, pierwotne ciało wykonuje się najszybciej , ale jak dla mnie pomijalnie szybciej od pozostałych ciał. W momencie inicjowania funkcji tabela B3[] jest wyzerowana. Widzę, że główkujesz, za co jestem wdzięczny. Studia skonczylem dobrych kilka lat temu, q jako koncowy wynik bez przebiegu na petli for.
    Na 8 linii kodu wali błąd na "s=..."

    0
  • #20 27 Paź 2016 21:20
    skierniak
    Poziom 14  

    Jakub_30 napisał:
    q jako koncowy wynik bez przebiegu na petli for.

    Tak - pomyłka - miałem na myśli, że z ostatniego przebiegu do-while, a po drodze masz ich tyle ...

    Poprawiłem błędy w ostatnim kodzie, ale i tak mogą jakieś być bo piszę na sucho.

    0
  • #21 27 Paź 2016 21:22
    Jakub_30
    Poziom 3  

    Spokojnie , nie pali się :)

    0
  • #22 27 Paź 2016 21:47
    skierniak
    Poziom 14  

    Jakub_30 napisał:
    Spokojnie , nie pali się :)


    teraz nie ale za chwilę może ... :)

    Kod: c
    Zaloguj się, aby zobaczyć kod


    deklaracja przed main musi być.
    Logiczne błędy nadal mogą być.

    Teraz dla rozrywki mogę sobie w to popatrzeć, a jutro niekoniecznie :)

    Dodano po 4 [minuty]:

    Duże S w s = rabs(B1, B2[s!!!], 0); znak w if w if(a>!!!!0.000000001) return s;

    Dodano po 1 [minuty]:

    a i to q wywaliłem bo to już puściłem przez kompilator żeby błędy składni złapać

    Dodano po 2 [minuty]:

    no i return w rabs :) oj.

    Dodano po 7 [minuty]:

    Wklejam jeszcze raz bo coś tam pomieszałem mocno wyżej:

    Kod: c
    Zaloguj się, aby zobaczyć kod


    może już mniej błędów :).

    0
  • #23 27 Paź 2016 21:51
    Jakub_30
    Poziom 3  

    pomysł jest ciekawy , tylko ciekawe czy w ogóle odpali.
    Jak już dopracujesz kod, to daj znać, będę go testował, bo jak na razie to nie mogę połapać końca z początkiem i na odwrót,
    bo co chwilę robisz aktualizację :P

    0
  • #24 27 Paź 2016 22:02
    skierniak
    Poziom 14  

    Jakub_30 napisał:
    jdaj znać, będę go testował, bo jak na razie to nie mogę połapać końca z początkiem i na odwrót,
    bo co chwilę robisz aktualizację

    Daję znać.
    Nic nie poradzę, że wszystko widać dopiero po wciśnięciu 'Opublikuj'. Teraz raczej jest ok. Testuj - teraz ty musisz sprawdzić czy z 'logiki' nic się :) nie popsuło lub zgubiło.

    0
  • #25 27 Paź 2016 22:04
    Jakub_30
    Poziom 3  

    Własnie uruchomiłem kompilator, liczy, z tym że już widzę że w oczekiwanym czasie nie wyświetlają się wyniki w okienku. Nic z tego, po kilku min nie ma wyników wyświetlanych przez cout w dalszym kodzie a to znaczy ze kompilator grzęźnie w tym voidzie

    0
  • #26 27 Paź 2016 22:08
    skierniak
    Poziom 14  

    Przy rekurencji można wpaść w pętlę. Przekopiowałeś kod po ostatnim moim poście? Przyjrzyj się warunkowi w rabs.

    0
  • #27 27 Paź 2016 22:26
    Jakub_30
    Poziom 3  

    widzę, że zmieniłeś 0 na -1 ale nadal wygląda na to że grzęźnie w pętli, bo cout w dalszym kodzie nie wyświetla nic

    Dodano po 7 [minuty]:

    Na razie nie wiem o co chodzi, ale szczegółowo bede analizował ten kod, bo wygląda on obiecująco i jest całkiem możliwe że wymaga kosmetycznej modyfikacji.

    0
  • #28 27 Paź 2016 22:29
    skierniak
    Poziom 14  

    cout masz przed rabs? Wkleisz dane na jakich to można testować?

    0
  • #29 27 Paź 2016 22:35
    Jakub_30
    Poziom 3  

    dam Ci na privie materiał do testowania, ale zajmie mi trochę czasu, może jutro mi się uda. A cout jest za wywołaniem voida

    0
  • #30 27 Paź 2016 22:38
    skierniak
    Poziom 14  

    Wiesz co - weź jeszcze w rabs w if odwróć znak i daj znać.

    0