Optymalizacje

[kt1117]

Witam, postanowiłem wrzucać tutaj różne kawałki kodów i jak koś znajdzie miejsce, gdzie można coś zooptymalizować to napisze i co kilka postów bedzie się robiło podsumowanie z różnymi sztuczkami typu ios_base::sync_with_stdio(0);.

To zarzucę pierwszym kodem:

#include <iostream>

using namespace std;

int a;
int B[1000000];

int main()
{
    ios_base::sync_with_stdio(0);
    cin>>a;
    int z;
    for(z=0;z<a;z++)
    {
        cin>>B[z];
    }
    bool ok=false;
    bool kupa=false;
    int y;

    for(z=0;z<a;z++)
    {
        y=0;
        ok=false;
        while(y<a and !ok)
        {
            if (B[y]==z+1)
            {
                ok=true;
            }
            y++;
        }
        if (!ok)
        {
            cout<<"NIE";
            return 0;
        }
    }

    cout<<"TAK";

    return 0;
}

 

Przy wiekszych liczbach program działa za wolno. Nie wiem jak to zooptymalizować, bo zmniejszyć rzędu funkcji się raczej nie da. Przynajmniej ja nie widzę takiej możliwości.

[Will]

Wybrałeś taki przykład gdzie nie bardzo jest co optymalizować. Pętle to pętle, wiadomo, że jak walniesz dostateczną ilość przejść to będą działać wolno i to żadna nowość.

[kt1117]

To jak znajdę jakiś inny kod, który można zooptymalizować to wrzucę. Ale dziwne, że nie da się nic zooptymalizować, bo system mi pokazuje, że da się go szybciej napisać.

[Will]

Zapewne w jakimś tam stopniu można ale zasada 80-20 wychodzi i takie optymalizowanie nie ma po prostu sensu bo zysk jest bliski zeru.

[kt1117]

Sęk w tym, żeby znaleść to 20. ;)

[Will]

W krótkich programach widać na oko, w większych prosty warstwowy profiler szybko pokaże co trzeba poprawić.

[kt1117]

Widzę, że jeszcze muszę się dużo nauczyć. Nie wiem jak zdąrzę sobie to wszystko wbić do głowy przed OIG, ale będę siedział po nocach, to w końcu się nauczę.

[Will]

W przypadku algorytmów wystarczy logiczne myślenie, podstawowa znajomość struktur danych i obeznanie z najpowszechniejszymi algorytmami. Tu nie tyle chodzi o wbicie do głowy miliona elementów tylko odpowiednie podejście. To jest po prostu problem, który trzeba rozwiązać:

a) dzieli się go na mniejsze części

b ) rozwiązuje poszczególne party, który "wyszły" z podziału

c) skleja w całość na jakimś pseudokodzie

d) przerzuca na kod c++/java/c# itd

 

Pierwsze 3 części nie mają nic wspólnego z kodem żadnego języka, po prostu trzeba znaleźć rozwiązanie, która "niszczy" dany problem w najmniejszej ilości kroków.

[kt1117]

Jeśli chodzi o liczby, to raczej daję radę. Za 3, czy 4 razem przeważnie mam dobry wynik, ale jest kwestia programu wywłaszczonego, który wyskakuje mi często, jest to spowodowane tym, że bardzo często używam 2 zagnieżdzonych pętli. Najłatwiej mi się w tym poruszać, chociaż nie wiem dlaczego. Najgorsze dla mnie są grafy, strasznie ciężko sobie je wyobrazić.

[Will]

Wszystko wydaje się ciężkie dopóki się tego nie pozna. Poznaj podstawową teorie grafów i zrób jakieś najprostsze testy. Jeśli to lubisz pobawisz się grafami kilka dni i zrozumiesz. Najlepsza metoda to książka albo wpisać w google teoria grafów(różne tego wariacje) i czytać wszystkie wprowadzenia. W końcu trafi się takie , które zrozumiesz.

[Platyna]

Jezu. Albo ja czegoś nie rozumiem, albo ten kod sprawdza czy w ciągu n liczb występują wszystkie liczby od 1 do n O.o

Jeśli się mylę to mnie popraw, a jeśli się nie mylę to puknij się mocno w łeb jeśli robisz coś takiego w złożoności kwadratowej. Wystarczy zastosować najzwyklejszego mergesort'a i już w posortowanym ciągu możesz na pytanie odpowiedzieć w czasie liniowym co łacznie daje złożoność n*log(n). A w tym problemie to nawet najzwyklejsze sortowanie przez zliczanie jest wystarczające i daje Ci czas liniowy.

 

Weź się, kurde, nie zajmuj zbędną optymalizacją to uruchom makówkę i algorytmiki się ucz.

 

A jak się do OIGa uczysz to wypadałoby żebyś już się nauczył używać cstdio zamiast strumieni. Może te drugie przy umiejętnym użyciu nie są wolniejsze, ale jeśli chodzi o wygodę to nieporównywalnie gorsze.

[Will]

Jezu. Albo ja czegoś nie rozumiem, albo ten kod sprawdza czy w ciągu n liczb występują wszystkie liczby od 1 do n O.o

Jeśli się mylę to mnie popraw, a jeśli się nie mylę to puknij się mocno w łeb jeśli robisz coś takiego w złożoności kwadratowej. Wystarczy zastosować najzwyklejszego mergesort'a i już w posortowanym ciągu możesz na pytanie odpowiedzieć w czasie liniowym co łacznie daje złożoność n*log(n). A w tym problemie to nawet najzwyklejsze sortowanie przez zliczanie jest wystarczające i daje Ci czas liniowy.

 

Dobra.. ale co w związku z tym? Najpierw to trzeba nauczyć się podstaw języka, potem rozwiązywać problemy a dopiero potem rozwiązywać problemy w optymalny sposób. Po co komu zejście z kwadratówki skoro na samej pamięci straci przykładowo na jedną alokacje(pokazał gdzieś wcześniej) 2 context-switch'e+całość na stringach jeszcze a o miss'ach nie wspominając. Ten tekst pasuje do kogoś kto już wie co piszę i jest na etapie gdzie problemem nie jest samo rozwiązanie tylko dostatecznie szybkie rozwiązanie, które zmieści się w czasie.

[kt1117]

Też myślałem o tym, żeby to posegregować, ale nie wiedziałem, czy to będzie szybsze. To zrobię to segregowaniem przez zliczanie, bo Merge jest dla mnie trochę dziwny narazie.