Zaawansowane CPP/Ćwiczenia 8: Metaprogramowanie: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
 
(Nie pokazano 41 wersji utworzonych przez 6 użytkowników)
Linia 1: Linia 1:
 +
{{cwiczenie|1||
  
''Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki''
+
Napisz szablon funkcji lub klasy wyliczający  
 
 
{Metaprogramowanie}
 
 
 
'''Zadanie 1 '''  Napisać szablon funkcji lub klasy wyliczający  
 
 
funkcję silnia:
 
funkcję silnia:
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
 
n!=n(n-1)(n-2)\cdots 1
 
n!=n(n-1)(n-2)\cdots 1
 +
</math></center>
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Rozwiązanie jest bezpośrednim zastosowaniem rekurencyjnej definicji funkcji silnia:
 +
<center><math>\displaystyle
 +
n!=n*(n-1)!,\quad 0!=1
 
</math></center>
 
</math></center>
  
'''Zadanie 2 ''' Zmodyfikować szablon <code><nowiki> Sqrt</nowiki></code> tak aby liczył
+
  template<size_t N> struct factorial {
całkowite przyliżenie logarytmu liczby <math>\displaystyle N</math> o dowolnej całkowitej
+
    enum {val=N*factorial<N-1>::val};
podstawie <code><nowiki> P<N</nowiki></code>.  Logarytm z liczby <math>\displaystyle N</math> przy podstawie <math>\displaystyle P</math>
+
};<br>
oznaczany <math>\displaystyle \log_P (N)</math> to rozwiązanie równania:
+
template<> struct factorial <0>{
 +
    enum {val=1};
 +
};
 +
 
 +
Patrz plik [[media:Factorial.h | factorial.h]].
 +
</div></div>
 +
 
 +
{{cwiczenie|2||
 +
 
 +
Zaimplementuj szablon <code><nowiki>Pow<N,M></nowiki></code> obliczający
 +
<math>\displaystyle N^M</math>. Np.:
 +
 
 +
Pow<3,4>::val;
 +
 
 +
powinno mieć wartość 81.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Implementujemy rekurencyjną definicję potęgi:
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
P^{\log_P(N)}=N
+
N^M=N*N^{M-1},\quad N^0=1
 
</math></center>
 
</math></center>
  
'''Wskażówka '''
+
template<size_t N,size_t M> struct pow {
Najpierw zaimplementuj szablon liczący dowolną (calkowitą)
+
    enum {val=N*pow<N,M-1>::val};
potęgę liczby całkowitej.
+
};<br>
 +
template<size_t N> struct pow<N,0> {
 +
    enum {val=1};
 +
};
  
'''Zadanie 3 ''' 
+
Dla przyspieszenia dodajemy dwie specjalizacje:
  
Wymyśl i zaimplementuj jako metaprogramszybszy algorytm funkcji <code><nowiki> pow(x)</nowiki></code>.
+
template<size_t M> struct pow<1,M>{
 +
    enum {val=1};
 +
  };<br>
 +
template<size_t M> struct pow<0,M>{
 +
    enum {val=0};
 +
};
  
'''Wskażówka '''  
+
Powyższa specjalizacja spowoduje, że konkretyzacja <tt>Pow<0,0></tt> będzie niejednoznaczna. Możemy to tak zostawić, bo <math>0^0</math> jest nieokreślone. Jeśli jednak zdecydujemy się na jakąś wartość, np. zero, to należy dodać jeszcze jedną specjalizację:
 +
 
 +
  template<> struct pow<0,0>{
 +
    enum {val=0};
 +
};
 +
 
 +
Patrz plik [[media:Pown.h | pown.h]].
 +
</div></div>
 +
 
 +
{{cwiczenie|3|| 
 +
 
 +
Wymyśl i zaimplementuj jako metaprogram szybszy algorytm funkcji <code><nowiki>pow(x)</nowiki></code>.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź</span><div class="mw-collapsible-content" style="display:none">
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
 
x^{(2 n)} = (x^2)^n,\quad x^{(2 n+1)} = x (x^2)^n
 
x^{(2 n)} = (x^2)^n,\quad x^{(2 n+1)} = x (x^2)^n
 
</math></center>
 
</math></center>
 +
</div></div>
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Do wzoru podanego w podpowiedzi dodajemy warunki brzegowe:
 +
<center><math>\displaystyle
 +
x^0=1,\quad x^1=x
 +
</math></center>
 +
 +
i implementujemy bezpośrednio:
  
'''Zadanie 4 '''
+
template<size_t N> double pow(double x) {
 +
    return ((N%2)?x:1)*pow<N/2>(x*x);
 +
}
 +
template<> double pow<1>(double x) {return x;};
 +
template<> double pow<0>(double x) {return 1.0;};
  
Napisz szablon generujący, pierwsze <code><nowiki> N</nowiki></code> wyrazów rozwinięcia funkcji
+
Patrz plik [[media:Powx.h | powx.h]].
<code><nowiki> sin(x)</nowiki></code>:
+
</div></div>
 +
 
 +
{{cwiczenie|4||
 +
 
 +
Napisz szablon generujący pierwsze <math>N</math> wyrazów rozwinięcia funkcji
 +
<math>sin(x)</math>:
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
\sin </math> <N> <math>\displaystyle  (x)=x-\frac{x^3}{3!}+\cdots +(-1)^{N+1}\frac{(x)^{2N-1}}{(2N-1)!}
+
sin<</math>N<math>> \displaystyle  (x)=x-\frac{x^3}{3!}+\cdots +(-1)^{N+1}\frac{(x)^{2N-1}}{(2N-1)!}
 
</math></center>
 
</math></center>
 +
Możesz skorzystać z rozwiązań wcześniejszych zadań.
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Jak zwykle najpierw piszemy definicję rekurencyjną:
 +
<center><math>\displaystyle
 +
sin<N> (x)=sin<N-1> (x)+(-1)^{N+1}\frac{x^{2N-1}}{(2N-1)!},
  
'''Zadanie 5 '''
+
\displaystyle sin<0> (x)=0
 +
</math></center>
  
Napisz szablon generujący funkcję implementującą iloczyn skalarny dwu wektorów.
+
i implementujemy ją korzystając z wcześniej zdefiniowanych szablonów:
Parametrem szablonu ma być dlugość możonych szablonów.  
+
 
 +
template<int N> double sin(double x) {
 +
    return sin<N-1>(x) + (N%2?1:-1)*pow<(2*N-1)>(x)/factorial<2*N-1>::val;
 +
}<br>
 +
template<> double sin<0>(double x) {
 +
    return 0;
 +
}<br>
 +
template<int N> double inner(double *a, double *b) {
 +
    return (*a)*(*b)+inner<N-1>(++a,++b);
 +
}<br>
 +
template<> double inner<1>(double *a, double *b) {
 +
    return (*a)*(*b);
 +
}
 +
 
 +
Patrz plik [[media:Inner.h | inner.h]].
 +
</div></div>
 +
 
 +
{{cwiczenie|5||
 +
 
 +
Napisz szablon generujący funkcję implementującą iloczyn skalarny dwu wektorów:
 +
 
 +
template<size_t N> double inner(double *x, double *y);
 +
 
 +
Parametrem szablonu ma być dlugość mnożonych wektorów.  
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
 
\operatorname{inner} </math> <N> <math>\displaystyle  (x,y)=x_1 y_1+\cdots y_N x_N
 
\operatorname{inner} </math> <N> <math>\displaystyle  (x,y)=x_1 y_1+\cdots y_N x_N
 
</math></center>
 
</math></center>
 +
}}
 +
{{cwiczenie|6||
 +
 +
Rozszerz powyższy szablon tak, aby również typ elementów wektora był parametrem szablonu:
 +
 +
template<size_t N, typename T> T dot(T *x, T *y);
 +
 +
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź</span><div class="mw-collapsible-content" style="display:none">
 +
Konieczne będzie użycie specjalizacji częściowej. W tym celu użyj pomocniczej klasy (specjalizacja częściowa jest niedozwolona dla funkcji).
 +
</div></div>
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Ponieważ warunek brzegowy <math>N=1</math> będzie wymagał specjalizacji częściowej, implementujemy iloczyn skalarny jako składową klasy:
 +
 +
template<size_t N,typename T = double > struct Inner {
 +
    static T dot(T *a,T *b) {
 +
        return (*a)*(*b)+Inner<N-1,T>::dot(++a,++b);
 +
    }
 +
}<br>
 +
template<typename T > struct Inner<1,T> {
 +
    static T dot(T *a,T *b) {
 +
        return (*a)*(*b);
 +
    }
 +
};
  
'''Zadanie 6 '''
+
a następnie dodajemy funkcję wywołującą tę metodę:
  
Napisz szablon generujący funkcję implementujący iloczyn macierzy
+
template<size_t N,typename T> T dot( T *a,T *b) {
<code><nowiki> NxM</nowiki></code> i wektora o <code><nowiki> M</nowiki></code> elementach:
+
    return Inner<N,T>::dot(a,b);
 +
};
  
<nowiki> void matrix_v<N>(double *A,double *v,double *u)
+
Patrz plik [[media:Inner.h | inner.h]].
</nowiki>
+
</div></div>
  
powoduje obliczenie:
+
{{cwiczenie|7||
  
<center><math>\displaystyle \aligned u_0&= A_{0,0} v_0+A_{0,1} v_1+\cdots+A_{0,M-1} v_{M-1}\\
+
Napisz szablon generujący funkcję implementującą iloczyn macierzy
 +
<math>NxM</math> i wektora o <math>M</math> elementach:
 +
 
 +
<nowiki> void matrix_v<N>(double *A,double *v,double *u)</nowiki>
 +
 
 +
<center><math>\displaystyle \begin{align} u_0&= A_{0,0} v_0+A_{0,1} v_1+\cdots+A_{0,M-1} v_{M-1}\\
 
u_1&= A_{1,0} v_0+A_{1,1} v_1+\cdots+A_{1,M-1} v_{M-1}\\
 
u_1&= A_{1,0} v_0+A_{1,1} v_1+\cdots+A_{1,M-1} v_{M-1}\\
 
&\vdots&\\
 
&\vdots&\\
 
u_{N-1}&= A_{N-1,0} v_0+A_{N-1,1} v_1+\cdots+A_{N-1,M-1} v_{M-1}\\
 
u_{N-1}&= A_{N-1,0} v_0+A_{N-1,1} v_1+\cdots+A_{N-1,M-1} v_{M-1}\\
\endaligned</math></center>
+
\end{align}</math></center>
 +
 
 +
Tablica <math>\displaystyle A</math> jest reprezentowana w pamięci zgodnie z konwencją <math>C</math>, tzn. wiersz po wierszu:
 +
elementowi <math>\displaystyle A_{i,j}</math> odpowiada <math>A[M*i+j]</math>.
 +
}}
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Najpierw definiujemy szablon, który wykonuje mnożenie <tt>I</tt>-tego wiersza macierzy <tt>A</tt> przez wektor <tt>v</tt>:
 +
 
 +
template<int M,size_t I> double row_vec(double *A, double *v) {
 +
    return inner<M>(A+I*M,v);
 +
}
 +
 
 +
Następnie implementujemy rekurencyjnie mnożenie kolejnych wierszy macierzy:
 +
 
 +
template<int N,int M> struct matrix_vec_c {
 +
    static void matrix_vec(double *A,double *v,double *u) {
 +
        u[N-1]=row_vec<M,N-1>(A,v);
 +
        matrix_vec_c<N-1,M>::matrix_vec(A,v,u);
 +
    }
 +
};<br>
 +
template<int M> struct matrix_vec_c<0,M> {
 +
    static void matrix_vec(double *A,double *v,double *u) {}
 +
};
 +
 
 +
Używamy szablonu klasy aby móc wykorzystać specjalizację częściową. Tak jak w poprzednim zadaniou opakowujemy wywołanie metody w szablon funkcji:
 +
 
 +
template<size_t N,size_t M>
 +
inline void matrix_vec(double *u,double *A,double *v) {
 +
    matrix_vec_c<N,M>::matrix_vec(A,v,u);
 +
}
  
Tablica <math>\displaystyle A</math> jest reprezentowana w pamięci zgodnie z konwencją <code><nowiki> C</nowiki></code>, tzn.
+
Całość kodu znajduje się w pliku [[media:Matrix.h | matrix.h]].
elementowi <math>\displaystyle A_{i,j}</math> odpowiada <code><nowiki> A[M*i+j]</nowiki></code>.
+
</div></div>

Aktualna wersja na dzień 12:42, 9 cze 2020

Ćwiczenie 1

Napisz szablon funkcji lub klasy wyliczający funkcję silnia:

Rozwiązanie

Ćwiczenie 2

Zaimplementuj szablon Pow<N,M> obliczający . Np.:

Pow<3,4>::val;

powinno mieć wartość 81.

Rozwiązanie

Ćwiczenie 3

Wymyśl i zaimplementuj jako metaprogram szybszy algorytm funkcji pow(x).

Podpowiedź
Rozwiązanie

Ćwiczenie 4

Napisz szablon generujący pierwsze wyrazów rozwinięcia funkcji :

N

Możesz skorzystać z rozwiązań wcześniejszych zadań.

Rozwiązanie

Ćwiczenie 5

Napisz szablon generujący funkcję implementującą iloczyn skalarny dwu wektorów:

template<size_t N> double inner(double *x, double *y);

Parametrem szablonu ma być dlugość mnożonych wektorów.

<N>

Ćwiczenie 6

Rozszerz powyższy szablon tak, aby również typ elementów wektora był parametrem szablonu:

template<size_t N, typename T> T dot(T *x, T *y);
Podpowiedź
Rozwiązanie

Ćwiczenie 7

Napisz szablon generujący funkcję implementującą iloczyn macierzy i wektora o elementach:

 void matrix_v<N>(double *A,double *v,double *u)

Tablica jest reprezentowana w pamięci zgodnie z konwencją , tzn. wiersz po wierszu: elementowi odpowiada .

Rozwiązanie