Ciekawe wykorzystanie szablonów

Chciałbym zwrócić Waszą uwagę na ciekawostkę w C++ związaną z szablonami. Najpierw pewien przykład:

Oto prosty program liczący silnię z dowolnej liczby. Załóżmy że mamy jakieś znane już podczas kompilacji dane, np. liczbę 10, dla której chcemy znać silnię.

#include <iostream.h>

int SilniaN(int X)
{
if(X==0) return 1;
if(X==1) return 1;
return X * SilniaN(X-1);
}

void main()
{
cout<<SilniaN(10);
}

Wynikiem będzie oczywiście silnia z 10 czyli 3628800
Teraz przedstawię inny sposób rozwiązania tego zadania:

#include <iostream.h>

template <int N>
struct SilniaT
{
enum{ X = N * SilniaT<N-1>::X };
};

template <> struct SilniaT<0> { enum{ X = 1}; };
template <> struct SilniaT<1> { enum{ X = 1}; };

#define SilniaS( A ) SilniaT< A >::X

void main()
{
cout<<SilniaS(10);
}

Wynik jest również 3628800. Więc po co tak komplikować?
Chodzi o szybkość wykonywania tych programów. Zmierzyłem czas dla 50000000 wykonanych operacji w trybie normalnym czyli dla funkcji SilniaN. Wynosił on na mojej maszynie ok. 16 sekund. Potem zmierzyłem czas dla takiej samej ilości operacji dla funkcji SilniaS. Czas wykonania wyniosł 0 sekund [!!!]

Jak to możliwe?
Otóż wszystkie obliczenia wykonały się zanim program został uruchomiony, jeszcze w kompilatorze. W rzeczywistości program ma na stałe wpisane gotowe wartości. Wydłużył się jedynie nieznacznie czas kompilacji.

• To wspaniale! - powiesz - Teraz mogę pisać programy, które wymiatają swoją szybkością, bo wszystkie obliczenia wykona kompilator!

Pamiętaj jednak, że DANE MUSZĄ BYĆ ZNANE JUŻ PRZY KOMPILACJI.
Prawdą jest, że ten sposób i tak jest bardzo pomocny, bo podczas kompilacji zawsze jakieś dane są już znane. Wtedy możemy wykorzystywać właśnie rozwiązanie szablonowe. Do tego jak to robić napisano nawet osobne książki.
Udowodniono nawet, że każdy algorytm można wpisać w szablon. Pisanie jednak takich dziwolongów nie jest już sprawą prostą więc pozostaje to (przynajmniej dla mnie) na razie tylko ciekawostką.

szablony to potężna broń szczegółnie przy programowaniu gier - w książce Perełki programownia gier jest o tym ładny artykuł :D

Mogę się mylić, ale wydaje mi się, że kompilator VC++ ma problemy z szablonami, bo MS nie rozwijał tego. Było tak zdaje się do wersji 6 (później nie wiem). Jeżeli źle mówię, to niech moderator to wytnie :)

// "niech" - jakie "niech"?! Mówi się "proszę" [green] - Q

Ehm, a ja znam jeszcze szybszy sposób, szczególnie w pisaniu... :>

cout << 3628800;

;-P

Brawo marcinEc [!!!]
Twój pomysł zrewolucjonizuje programowanie. Ta prostota, połączona z wydajnością i elegancją. Tylko pozazdrościć pomyślunku :D

skrzypol napisał(a)

Brawo marcinEc [!!!]
Twój pomysł zrewolucjonizuje programowanie. Ta prostota, połączona z wydajnością i elegancją. Tylko pozazdrościć pomyślunku :D

Tak misiu.. Do wartości 1 też można przejść od cos^2+sin2 poprzez całki i inne rzeczy :-P

skrzypol napisał(a)

Brawo marcinEc [!!!]
Twój pomysł zrewolucjonizuje programowanie. Ta prostota, połączona z wydajnością i elegancją. Tylko pozazdrościć pomyślunku :D

sie śmiej ale ja nie rozumiem tej rewolucji.... po co robić jakąś wymyślną konstrukcje programistyczna skoro i tak wynik zawsze MUSI być ten sam...
Równie dobrze można było zrobić tak jak mówi marcinEc

Wg mnie to wszystko zależy do czego ma być użyte. Weźmy pod uwagę tą silnię.
Możemy rozpatrzyć 3 przypadki ze względu na ilość użyć:

1. Kilka razy
2. Sporadycznie
3. Nagminnie

Ad1. Jeżeli w programie zostanie ona użyta raz czy dwa to rzeczywiście nie ma sensu pisać tak skomplikowanego kodu w celu osiągnięcia wyniku. Tutaj można zastosować normalną funkcję, bądź wpisać wartość ręcznie (w celu nieznacznego przyspieszenia programu)

Ad2. Jeżeli w programie ma być ona użyta od czasu do czasu to najlepiej użyć normalnej funkcji z dwóch powodów:

1. Nie trzeba cały czas liczyć ile to ma być
2. Aby zaznaczyć co oznacza ta wartość.

Ad3. Jeżeli ma być użyta bardzo często (nie daj boże w jakichś pętlach) to można zastanowić się nad tym rozwiązaniem (zwłaszcza gdy wiemy, że komputer na którym będziemy uruchamiać program jest dużo słabszy niż ten na którym kompilujemy). Jednakże w/g mnie takie szablony, do tego zastosowania powinno się stosować tylko w przypadku, gdy wykonują one jakieś skomplikowane obliczenia pochłaniające moc obliczeniową procesora.

To tyle. Napisałem się jak głupi, a i tak nic odkrywczego nie przekazałem. Heh...

skrzypol napisał(a)

template <int N> 
struct SilniaT
{	
	enum{ X = N * SilniaT<N-1>::X }; 
};

template <> struct SilniaT<0> { enum{ X = 1}; };
template <> struct SilniaT<1> { enum{ X = 1}; };

#define SilniaS( A ) SilniaT< A >::X

Moze mi to ktos lopatologicznie ala Gębosz wytlumaczyc? :(

Oczywiście nikt takiej silni w programach nie pisze na szablonach (metaprogramowanie). Dałem ją po prostu jako przykład bo jest stosunkowo prosta ;P Ale np. widziałem przykłady (min. w Perełkach programowania gier) użycia szablonów do chociażby trygonometrii, gdzie otrzymywano funkcje sin, cos, tg z dowolną dokładnością nawet do 15 miejsc po przecinku, przekazywane do programu już jako liczby! Metaprogramowania używa się głównie po to by uprościć jakiś algorytm, który ma być wykonywany w czasie rzeczywistym. Np. przekształcanie macierzy w grach jest o kilkadziesiąt procent szybsze niż bez tej techniki. Niby to tylko kilkadziesiąt procent, ale np. w grach ma to znaczenie. Każdy algorytm, w którym chociaż część parametrów jest znana w trakcie kompilacji, zyska na wykorzystaniu w nim metaprogramowania opartego na szablonach.

A teraz wyjaśnienie programu, który dałem. Nie jestem żadnym specjalistą w C++ więc jak będę pisał jakieś herezje to mnie poprawcie:

Program wygląda tak:

#include <iostream.h>

template <int N>
struct SilniaT
{
enum{ X = N * SilniaT<N-1>::X };
};

template <> struct SilniaT<0> { enum{ X = 1}; };
template <> struct SilniaT<1> { enum{ X = 1}; };

#define SilniaS( A ) SilniaT< A >::X

void main()
{
cout<<SilniaS(10);
}

A więc po kolei:

template <int N>
struct SilniaT
{
enum{ X = ... };
};

Stworzono szablon struktury (można też zrobić klasy), który będzie tworzył struktury w zależności od parametru N (N musi być znane podczas kompilacji). W strukturze nie można napisać np. int X = cośtam, więc użyliśmy słowa enum, które w kompilatorze przypisuje pewnej nazwie określoną liczbę całkowitą. W ten sposób zmuszamy kompilator do obliczenia tego co znajduje się za X = czyli:

N * SilniaT<N-1>::X

Taki zapis jest rzadko spotykany, ale poprawny w składni C++. Tworzy on strukturę z parametrem N-1 i wyciąga z niej X, który znowu jest obliczany w ten sam sposób itd. Dzieje się tak aż do momętu gdy N będzie równy 0 lub 1.

template <> struct SilniaT<0> { enum{ X = 1}; };
template <> struct SilniaT<1> { enum{ X = 1}; };

W tych liniach stworzono już struktury dla wartości 0 i 1, więc kompilator nie musi ich ponownie tworzyć, a więc zawsze na nich przerwie pracę pętla rekurencyjna.

#define SilniaS( A ) SilniaT< A >::X

Użyliśmy po to, żeby szablon wyglądał tak jak funkcja - zabieg czysto kosmetyczny.

Bardzo dziekuje za szczagolowe wyjasnienie...
Musze sobie nabyc ta "perelki programowania gier" i Gebosza przeczytac do konca 2 tom, caly 3 z symfonii oraz obowiazkowo Pasja c++" ;-)

Dziekuje bardzo