Śrubowanie wyników, optymalizacja ekstremalna

Witam.
Borykałem się trochę do jakiego działu skierować ten tekst, i w końcu padło tutaj (nadal nie wiem czy dobrze :P), nie wiem też czy był taki temat bo nie wiem jak szukać :P

Do rzeczy:
Ostatnio próbowałem sobie pobić rekord własnych możliwości - trochę może z nudów, trochę z ciekawości :)
Konkretnie chodzi o ten "L I N K (zadanko z ACM/UVA)"
Z pozoru proste zadanie - odfiltrować znaki i sprawdzić czy jest to palindrom wyświetlając tekst.
Uporałem się z nim szybko z pomocą klasy cstring w c++ i otrzymałem czas rzędu 0.08s
Następnie wymodziłem kod od nowa w czystym C sprawdzając wszystko ręcznie z pomocą czystych tablic i ... też wyszło 0.08s.

Nie było by to może nic dziwnego, że naprawdę nie widzę niczego więcej do poprawy a jednak sporo osób ma czas 0.00s (a to zadanie było tylko przykładem jest dużo takich).

Jak myślicie na czym polega sekret tego, że ktoś ma w niektórych takich zadaniach 0s a ja nie mogę się nawet zbliżyć do tego czasu - w czym tkwi owy sekret ?:/

<font size="1">*Jeżeli będzie zainteresowanie mogę umieścić tu kod, może coś znajdziecie :)*jeżeli temat sie nie nadaje do działu to przepraszam</span>

#include <stdio.h>
#include <string.h>
const int roznica=('a'-'A');
inline int inrange(char *z)
{
    if (*z>='a' && *z<='z')
        return 1;
    if (*z>='A' && *z<='Z'){
        *z+=roznica;
        return 1;
    }
    return 0;

}
inline int spr(char *str,int dl)
{
    int i=0,j=dl-1;
    while (i<=j)
    {
        while (!inrange(&str[i]))
            if (++i>=j) return 1;
        while (!inrange(&str[j]))
            if (i>=--j) return 1;
       
        if (str[i]!=str[j])
            return 0;
        i++;j--;
    }
    return 1;
}
int main()
{
    char zdanie[1000];
   while(fgets(zdanie,999,stdin))
   {
       int len=strlen(zdanie);
       if (len==5)
            if (zdanie[0]=='D' && zdanie[1]=='O' && zdanie[2]=='N' && zdanie[3]=='E')
               return 0;
       fputs(spr(zdanie,len) ? "You won't be eaten!\n" : "Uh oh..\n",stdout);
   }

   return 0;
}

Dodam jeszcze np takie zadanie: Bardzo proste zadanie :)

i kod do niego:

#include <stdio.h>
int main()
{
   int v1,t1;
while ( scanf("%d %d",&v1,&t1) == 2 )
{
printf("%d\n",2*v1*t1);
} 
   
   return 0;
}

Niby nic skomplikowanego, a czas tego kodu to: 0.020
przy czym ktos ma 0.00s inni po 0.006 no i naprawdę zachodzę w głowę co oni tam mogli takiego dać, że jest aż taka różnica w tak prostym kodzie :)
</url>

może inna pętla XD?

Gelldur, malutka prośba, programujesz drugi dzień, nie ucz ludzi optymalizacji.

1. Moim zdaniem tracisz sporo czasu na tym warunku od DONE i to musiałbyś inaczej zrobić
2. Zamiast mnożenia przez 2 mozesz np. przesuwać bitowo w prawo.

... napisał(a)

Gelldur, malutka prośba, programujesz drugi dzień, nie ucz ludzi optymalizacji.
Jesteś żałosny w ogóle po co piszesz skoro nie na temat mama cie leje kablem przed tym kompem czy stary za mało tulił?

@Gelldur wyluzuj troche i posluchaj czasem jak ktoś mądrzejszy coś pisze.
Twoja rada była idiotyczna bo w kodzie wynikowym nie ma znaczenia czy używałes for() czy while() czy jeszcze czegoś innego, bo wygląda to po kompilacji z reguły tak samo i użycie takiej czy innej pętli nie wpływa na szybkośc wykonywania programu.

Tak szczerze powiedziawszy to wydaje mi się bardziej, że jest to po prostu błąd pomiarowy. Bo jak można zmierzyć wykonywanie czegoś tak małego jak w programie 2?

#include <stdio.h>
int main()
{
   int v1,t1;
while ( scanf("%d %d",&v1,&t1) == 2 )
{
//tu zaczynasz mierzyć czas
printf("%d\n",2*v1*t1);
//tu konczysz?
}
   
   return 0;
}

Aby sprawdzić efektywność jakiegoś algorytmu należy go wykonać tysiące razy bez ingerencji użytkownika. W przeciwnym wypadku zbyt dużą rolę odgrywa tutaj błąd pomiarowy. Dodatkowo wiele zależy od warunków testowania, obciążenia systemu, prędkości procesora etc. Jak program może wykonywać się 0.00 sekund?

dobrze ale ten idiota mnie wnerwia czepia się o byle co w każdym temacie

@.::. on chyba mówi o czasach które są podane w po wrzuceniu programu i przetestowaniu go przez jakiś system arbitrażowy. Gdzie teoretycznie każdy program jest testowany w identycznych warunkach.

Shalom napisał(a)

2. Zamiast mnożenia przez 2 mozesz np. przesuwać bitowo w prawo.

Nie. Po pierwsze to w lewo. Po drugie to nie przesunąć a dodać do siebie, dodawanie jest szybsze. Po trzecie - NIGDY takich rzeczy się nie robi jeżeli kod jest kompilowany z optymalizacją, tylko ją utrudniasz.

http://4programmers.net/Forum/viewtopic.php?id=114318 - tutaj jest calkiem sporo o optymalizacji :)

@...
faktycznie w lewo, mój błąd ;)
Jeśli jest ustawiona optymalizacja to oczywiście nie ma sensu tak kombinować, ale autor pytal jakie są możliwości modyfikacji jego kodu, więc zapropnowałem co można zmienić.

Shalom napisał(a)

1. Moim zdaniem tracisz sporo czasu na tym warunku od DONE i to musiałbyś inaczej zrobić
2. Zamiast mnożenia przez 2 mozesz np. przesuwać bitowo w prawo.

2. przesunięcie może i by coś dało bo wszak '2vt' może nie być zoptymalizowane, aczkolwiek chyba powinno.
3. Myślę, że to dobry sposób jednak bo najpierw sprawdzam czy długość pasuje (oddzielnie bo nie wiem nigdy od której strony sprawdza się połączone warunki :P), a samo sprawdzenie DONE chyba powinno się zakończyć na FALSE w momencie, gdy pierwsza litera sprawdzana będzie FALSE (po optymalizacji) ?

.::. napisał(a)

Aby sprawdzić efektywność jakiegoś algorytmu należy go wykonać tysiące razy bez ingerencji użytkownika. W przeciwnym wypadku zbyt dużą rolę odgrywa tutaj błąd pomiarowy. Dodatkowo wiele zależy od warunków testowania, obciążenia systemu, prędkości procesora etc. Jak program może wykonywać się 0.00 sekund?

pętla jest tak skonstruowana, że 'miele' pÓÓÓÓki nie napotka na EOF, a to co idzie na STDIN jest już przygotowane w tych ich systemie sprawdzającym - nie wiem ile, ale pewnie z ładnych kilka-kilkadziesiąt tysięcy przypadków :)

Ogólnie to się dziwie jak można takie wyniki uzyskać w tak prostych programach, zaczynam myśleć, że faktycznie może chodzi o to na którą 'godzine' (na jaki ruch na serwerze) się natknę podczas wysyłania programu :D

Kilka razy schodziłem już z czasami w dół krok po kroku z np 0.028s na 0.08s, ale niżej nie da rady :P

Chciałbym zajrzeć w kod kogoś kto ma 0.00s :P

Coś krencicie, wrzuciłem z ciekawości ten kod co był w drugim pości i dostałem czas " 0.008". Więc tak naprawde to nie jest zły kod, fakt że można go poprawić, przerobić...

Można te zadania potraktować automatami ze stosem ;)

W zadaniu z misiem automat jeśli litera na stosie byłaby inna niż wejściowa to byłaby odkładana na stos, w przeciwnym razie zdejmowana. Jeśli po wyjściu stos byłby pusty to znaczy, że mieliśmy palindrom. Dodatkowo stan po przeczytaniu 'DONE'.

W zadaniu z prędkościami podobnie. Tyle, że byłyby dwa automaciki - jeden wczytujący pierwszą liczbę i zatrzymujący się na spacji, a drugi wczytujący drugą liczbę i zatrzymujący się na enterze. Tego printfa też dałoby się ztablicować ;) (Np. mając tablicę na wyniki mnożeń początkowo niezainicjowaną i drugą tablicę z flagami mówiącą, czy wynik danego mnożenia był już policzony).

Zamiast gadać o trikach optymalizacyjnych to raczej trzeba było uspranić ten algorytm.

#include <stdio.h>
#include <string.h>
#include <ctype.h>

// skraca napis jedynie do liter, które zmienia na małe 
// zwraca wskaźnik na koniec napisu, żeby nie mierzyć ponownie długości napisu
char *compress(char *s)
{
     char *p = s;

     for(*s;++s) {
         if(isalpha(*s))
               *p++ = tolower(*s);
     }
     return p;
}

// sprawdza binarnie czy to jest palindrom
int isPalindrom(char *begin, char *end)
{
    while(begin!=end) {
        if(begin==--end)
             break;
        if(*begin++!=*end) {
             return 0;
        }
    }
    return 1;
}

int main()
{
    char zdanie[1000];
    while(fgets(zdanie,sizeof(zdanie), stdin))
    {
        if(strcmp(zdanie, "DONE") == 0){
             break;
        }
        fputs(isPalindrom(zdanie,compress(zdanie)) ? "You won't be eaten!\n" : "Uh oh..\n",stdout);
   }

   return 0;
}

MarekR22 napisał(a)

Zamiast gadać o trikach optymalizacyjnych to raczej trzeba było uspranić ten algorytm.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
...

Nie kompilował się :) poprawiłem warunek w pętli (brak srednika w s++)
sprawdziłem dla kajak,kajak i wysłałem do sprawdzenia :)
Czas 0.008s (tak jak ten przedstawiony przeze mnie), ale nie przeszedl wszystkich testow (nie wiem czy jak jest zla odp to zabijaja proces wiec mozliwe ze dzialal by dluzej).

Sprawdzę zaraz jak się sprawa ma ze wstawkami asemblera :P

Wstawki nic nie dadzą, poza tym asma się na konkursach nie używa. Pomyśl nad innym podejściem do problemu, bo rozwiązania i tak są z optymalizacją kompilowane - uważasz, że napiszesz kilkukrotnie wydajniejszy kod od wygenerowanego przez kompilator? Ja trzymając się tego samego algorytmu i setu instrukcji nie potrafię.

Poza tym większość konkursów nie zezwala w ogóle na wstawki asemblerowe w kodzie.

Nie chce mi się tam rejestrować, więc może opisz jak się wprowadza program do oceny.
Co należy wysłać sędziemu?

abc napisał(a)

..
Nie kompilował się :) poprawiłem warunek w pętli (brak srednika w s++)
sprawdziłem dla kajak,kajak i wysłałem do sprawdzenia :)
Czas 0.008s (tak jak ten przedstawiony przeze mnie), ale nie przeszedl wszystkich testow (nie wiem czy jak jest zla odp to zabijaja proces wiec mozliwe ze dzialal by dluzej).

Fakt mam tendencje do łykania znaków, ale chyba źle to poprawiłeś (wygląda na to, że dodałeś średnik w złym miejscu), miało być:

for(; *s; ++s) {

Podaj jakie testy fail'ują to zobaczę o co chodzi.

MarekR22 napisał(a)

...
Podaj jakie testy fail'ują to zobaczę o co chodzi.

Żeby to było widać to by nie było problemu z zadankami :D
Ale trochę inaczej to poprawiłem możliwe, że wszystko jest dobrze :P [ja sprawdzałem do '\n' i dzialalo dla kilku moich przykładów].

...
Co do asma to da się w jednym z zadań udało mi się już czas dwukrotnie poprawić :}
niestety g++ -O2 sprawia, że program się gubi w rejestrach (moze nie tylko) (zła optymalizacja - błędy) i trzeba poprawiać specjalnie pod kompilator :/ (bez -O2 śmiga, ale nie moge tego zmienic :D) - no i jeszcze pusha (not supported on x64) i pushl (tez jakis blad na x64) nie działają to niektórych rzeczy nie potrafię 'zasmowac' (nie chce mi sie bawic we wrzucanie rejestrow do tablicy, a pozniej odczytywanie i jeszcze ta optymalizacja :( )]

pusha wywalili z instruction setu, więc musisz ręcznie zachowywać rejestry. pushl za to nie ma prawa działać, bo w trybie 64bit trudno wrzucić na stos coś 32bit - może pushq?
Jak ci mówią, żebyś się skupił na algorytmie zamiast używać wstawek, to skup się na tym pieprzonym algorytmie, a wstawek używaj tam, gdzie są potrzebne - uzyskanie 1% szybszego kodu to zły powód.

Fanael napisał(a)

pusha wywalili z instruction setu, więc musisz ręcznie zachowywać rejestry. pushl za to nie ma prawa działać, bo w trybie 64bit trudno wrzucić na stos coś 32bit - może pushq?
Jak ci mówią, żebyś się skupił na algorytmie zamiast używać wstawek, to skup się na tym pieprzonym algorytmie, a wstawek używaj tam, gdzie są potrzebne - uzyskanie 1% szybszego kodu to zły powód.

jakos pushb i pushw działają, a zabraklo pushl :(

Naprawde nie wiem kto uklada te testy, ale co mozna wniesc do tego algorytmu?
--> i tak trzeba odfiltrować krzaczki
--> i tak trzeba cos zrobic z wielkoscia liter (moze tablicowac jakos gotowe porownania zeby martwic sie o to tylko raz? - i tak jest duuuza ilosc testow)
--> trzeba i tak kazda literke odwiedzic

Co do 1%:

Testy mają tak poukładane, że dużą różnice w czasie pokazuje już zastąpienie iostream na rzecz scanf, a juz w ogole o fgets nie wspomnę (analogicznie printf<fputs), tak samo udało mi sie przeglądając tablice i zamieniając wartości elementów poprzez wstawkę zyskać kolejne około 0.09s (inne zadanie).

Szkoda, że tak jest bo można było by naprawdę ocenić wartość danej implementacji i się czegoś dowiedzieć, a nie być pokrzywdzonym, że użyło się innej biblioteki (realizującej de facto to samo) :)

A z 'czasem walcze' ot tak, dla spojrzenia na kodowanie z drugiej strony :P

Jeden gościu dał taki kod i powiedział ze ma 0.000, to kod do Word Scramble. Wysłałem do jako swój i miałem 0.012. Więc wyniki niestety różnią się i to bardzo, w zależności nie wiadomo od czego. Prawdopodobnie od obciążenia serwera.

#include<iostream>
#include<cstdlib>
#include<stdio.h>

using namespace std;

int main(int argc, char *argv[])
{
    int index = 0, c = 0;
    char tmp, ar[250];
    while(tmp = getchar())
    {
        if(tmp == EOF)
        {
            for(int i = index-1; i>= 0; i--)
                cout << ar[i];
            break;
        }
        if(tmp == '\n')
        {
            for(int i = index-1; i>= 0; i--)
                cout << ar[i];
            cout << endl;
            index = 0;
        }
        else if(tmp == ' ')
        {
            c++;
            for(int i = index-1; i>= 0; i--)
                cout << ar[i];
            for(int i = 0; i < c; i++)
                cout << " ";
            index = 0;  c = 0;
        }
        else if(tmp != ' ')
        {
            ar[index++] = tmp;
        }
    }
    system("PAUSE");
    return EXIT_SUCCESS;
} 

abc napisał(a)

Dodam jeszcze np takie zadanie: Bardzo proste zadanie :)

i kod do niego:

#include <stdio.h>
int main()
{
   int v1,t1;
while ( scanf("%d %d",&v1,&t1) == 2 )
{
printf("%d\n",2*v1*t1);
} 
   
   return 0;
}

Niby nic skomplikowanego, a czas tego kodu to: 0.020
przy czym ktos ma 0.00s inni po 0.006 no i naprawdę zachodzę w głowę co oni tam mogli takiego dać, że jest aż taka różnica w tak prostym kodzie :)
</url>

Tutaj zdecydowanie najwięcej czasu zajmuje scanf i printf.
Przy każdym obrocie pętli musi być chociażby sparsowane "%d\n" i "%d %d".
Jeżeli chcesz to zrobić naprawdę wydajnie to:
-napisz procedurę wczytywania liczby
-utwórz tablicę 200x200 (v (-100 <= v <= 100) i t (0<=t<= 200)) wszystkich wyników. Może nawet wydajniej będzie trzymać napisy wynikowe, a nie liczby. Niektóre sprawdzaczki mają limit źródeł, ale tablicę ~10kB powinny jeszcze przepuścić.

-utwórz tablicę 200x200 (v (-100 <= v <= 100) i t (0<=t<= 200)) wszystkich wyników. Może nawet wydajniej będzie trzymać napisy wynikowe, a nie liczby. Niektóre sprawdzaczki mają limit źródeł, ale tablicę ~10kB powinny jeszcze przepuścić.

Ja kiedyś próbowałem taką optymalizację zrobić i maszynka pokazała mi jeszcze więcej niż bez takiego kombinowania. Minimalny czas jaki udało mi się kiedyś osiągnąć 0.02. D 0.00 to chyba trzeba mieć fart.

robiłem kiedyś z nudów zadania na SPOJ-u, i bład pomiarowy jest spory - w zadaniu z wyszukaniem liczb pierwszych z iluś tam tysięcy podanych na wejściu - ten sam kod zwracał mi rozrzut od 0.01 do 0.05.

Jak widać po wynikach często są to 0.00, czy 0.01 czyli de facto można założyć, że zbiór danych wejściowych jest często za mały do miarodajnego wyliczenia implementacji dobrych algorytmów. Z tego co zauważyłem u siebie, to podpowiedzieć mogę kilka rzeczy (zapewne dla wielu oczywistych):

1. nie używać nigdy zsynchronizowanego (czyli defaultowego) cin/cout
2. w przypadku pracy z liczbami nie używać nigdy scanf(...) - zastąpić to własnym fragmentem kodu - ascii na int-y można przetworzyć w ten sposób o wiele szybciej /u mnie poprawiło to wynik o kilkanaście setnych ms);
3. niczego nie mallocować - zazwyczaj spokojnie można zmieścić się w limitach pamięci deklarując tablice globalne.
4. samemu formatować text wyjściowy i..
5. ..jeśli to możliwe, batchować we własnej tablicy tekst wyjściowy i 'printować' go w 10 lub 100 partiach bez formatowania zamiast 10000-100000 razy z formatowaniem.

Niestety ze względu na takie sprawy, często jakość algorytmu i jego implementacji potrafi być zaciemniona przez standardową obsługę tekstowego I/O. Z drugiej strony, jak się już zrobi raz taki 'framework' do własnej, szybkiej obsługi I/O - można z niego korzystać w większości zadań.

Ogólnie to chyba nie warto w ogóle korzystać z cout i cin oraz z dobrodziejstw cpp.
C 0.020:

#include <stdio.h>

int main()
{
    int v,t; 
    while ( scanf("%d %d",&v,&t) != EOF )
    { 
        printf("%d\n",(v<<1)*t);
    }
    return 0;
}

C++ 0.120

#include <iostream>
using namespace std;

int main()
{
    int v,t;
    while ( cin >> v >> t )
    {
        cout <<(v<<1)*t <<endl;
    }
   return 0;
}

@.::.
http://www.cplusplus.com/reference/iostream/ios_base/sync_with_stdio/ - i teraz zrób testy.