F90M Temat założony przez niniejszego użytkownika |
Szybkość działania programu » 2010-11-10 18:47:21 Ktoś może mi wytłumaczyć dlaczego ten kod #include <iostream>
#include <cstdlib>
#include <ctime>
#define _ILOSC 50000
int main()
{
srand( time( NULL ) );
int iTab[ _ILOSC ];
for( int a = 0; a < _ILOSC; ++a ) iTab[ a ] = rand() % 2000000;
int iWielkoscTab = 50000;
bool bZmieniono;
int temp;
do
{
bZmieniono = false;
for( int a = 0; a < iWielkoscTab - 1; ++a )
{
if( iTab[ a ] > iTab[ a + 1 ] )
{
temp = iTab[ a ];
iTab[ a ] = iTab[ a + 1 ];
iTab[ a + 1 ] = temp;
bZmieniono = true;
}
}
} while( bZmieniono );
}
Wykonuje się wolniej niż ten #include <iostream>
#include <cstdlib>
#include <ctime>
#define _ILOSC 50000
void Sortowanie( int *, int );
int main()
{
srand( time( NULL ) );
int iTab[ _ILOSC ];
for( int a = 0; a < _ILOSC; ++a ) iTab[ a ] = rand() % 2000000;
Sortowanie( iTab, _ILOSC );
}
void Sortowanie( int * iTab, int iWielkoscTab )
{
bool bZmieniono;
int temp;
do
{
bZmieniono = false;
for( int a = 0; a < iWielkoscTab - 1; ++a )
{
if( iTab[ a ] > iTab[ a + 1 ] )
{
temp = iTab[ a ];
iTab[ a ] = iTab[ a + 1 ];
iTab[ a + 1 ] = temp;
bZmieniono = true;
}
}
} while( bZmieniono );
}
Przy obydwu mam włączone optymalizacje -s i -O2. Pierwszy kod wykonuje się w czasie ok. 10.60sec, a drugi ok. 8.20sec. Dodatkowo, żeby było ciekawiej, po usunięciu z obu programów nagłówka iostream, którego i tak nie używam, pierwszy program zwalnia do 10.80sec, a drugi przyspiesza do 8.05sec (to akurat wydaje się logiczne). I kolejna ciekawa sprawa, jeśli w drugim kodzie, przy dodanym nagłówku iostream, zamiast "iWielkoscTab - 1", w warunku for, wpiszę na sztywno 49999 to program wykonuje się 8.65sec. Sprawdzałem te czasy po kilkanaście razy dla każdego z przypadków i nigdy nie różniły się o więcej jak 0.03-0.05 sekundy. |
|
DejaVu |
» 2010-11-10 19:12:32 Jak Ci może się kompilować program w którym nie ma definicji makra _ILOSC? |
|
F90M Temat założony przez niniejszego użytkownika |
» 2010-11-10 19:16:28 Przy wklejaniu kodu przypadkowo nie dodałem ;)
Już poprawiam. |
|
DejaVu |
» 2010-11-11 14:00:24 Algorytmy pracują dla różnych danych. Równie dobrze przy ogromnej ilości szczęścia może okazać się, że jeden wykona się w czasie liniowym, a drugi przy pechowym rozłożeniu liczb w czasie kwadratowym. |
|
F90M Temat założony przez niniejszego użytkownika |
» 2010-11-11 14:40:18 Aby test był bardziej miarodajny, tablice wypełniłem za każdym razem takimi samymi liczbami: for(int a = 0, b = _ILOSC; a < _ILOSC; ++a, --b) iTab[ a ] = b; . Co się okazuje, znika problem szybkości związany z brakiem nagłówka iostream, ale pozostałe wciąż są aktualne, tz. pierwszy program wykonuje się w czasie 8.45, drugi 6.75, a jeśli w drugim, tak jak wcześniej, w warunku for zamiast a < iWielkoscTab - 1 wstawię a < _ILOSC - 1 bądź a < 49999 to program wykonuje się w 6.97 sekundy. Naprawdę, sprawdzam to po kilkanaście razy i różnica nie przekracza 0.02-0.03 sekundy. |
|
DejaVu |
» 2010-11-11 15:17:21 const int iWielkoscTab = 50000;
Napisz powyższą linijkę w taki sposób i sprawdź szybkość działania. |
|
F90M Temat założony przez niniejszego użytkownika |
» 2010-11-11 16:19:49 Z ciekawości jakie cuda wynikną, w drugim przykładzie zrobiłem funkcje inline i to rozwiązanie okazało się wolniejsze (7.2sec). Pomyślałem więc że kompilator robi mnie w ****, wyłączyłem optymalizacje i teraz pierwszy program wykonuje się szybciej (25.7sec) niż drugi (33.2sec).
Zalatuje mi to lekką samowolką ze strony GCC. |
|
DejaVu |
» 2010-11-11 17:51:58 W zasadzie tu nie chodzi o samowolkę. Kompilator po prostu inny kod wygeneruje gdy wartość graniczna jest stała i inny kod gdy jest to zmienna. Zmienna może się zmienić wewnątrz pętli, natomiast stała nie. Stała jest umieszczona w instrukcji porównującej czy już koniec, natomiast w przypadku zmiennej to jest umieszczony jej adres i trzeba dodatkowo odczytać wartość z pamięci zanim dokona się porównania. Subtelna różnica, która wpływa na wydajność. |
|
| « 1 » 2 |