Newsgroup: it.comp.lang.c++
Titolo: Template e code

Chiunque di voi abbia dimestichezza con i template saprà realizzare in 
poco tempo una semplice coda (di tipi), ma siete in grado di realizzarne 
una che inserisca ed estragga gli elementi in tempo (di compilazione) 
costante?
Kiuhnm

Kiuhnm wrote:

perdona la mia ignoranza, ma che vuol dire tempo di compilazione?
se e' il tempo che ci mette il compilatore a creare l'eseguibile... who
cares? l'importante e' che l'algoritmo abbia complessità O(1) in
esecuzione...
devo aver perso qualche passaggio...
-- 
Under construction

 cares?
Forse chi deve aspettare che la compilazione finisca?
Kiuhnm

Kiuhnm wrote:

a meno di casi eccezionali, non penso che nessun programma ci metta a
compilare più di mezza giornata, su piattaforme particolarmente poco
performanti.
piuttosto, anche come sviluppatore, cercherei di focalizzarmi su quanto
veloce (se serve, ovvio... se devo sviluppare un gestionale ho altre
priorità) il programma faccia il suo dovere, una volta compilato.
ma questo aspetto della programmazione dipende strettamente anche da aspetti
che con il linguaggio non c'entrano quasi niente.
Immagino, infatti, che ogni compilatore abbia qualche ottimizzazione
(interna e/o parametrica) per velocizzare le varie fasi della compilazione,
e che queste siano diverse sia a seconda del compilatore stesso, sia in
dipendenza dalla piattaforma su cui gira, includendo sistema operativo come
cpu...
quindi, anche volendo, non so neanche se si possa fare tale ottimizzazione,
a meno di non restringere la domanda su, ad esempio, su
gccVERSIONE1+slackwareVERSIONE2+athlon t-bird@TOTMh (piuttosto che
qualcosaltro, non è questo il punto)
dal fatto che comunque, sei "famoso" per queste domande, posso anche
presumere che tu abbia già trovato una risposta (magari anche indipendente
da os/cpu e persino compilatore), quindi, al limite, ti chiederei di
postarla.
-- 
Under construction

> Forse chi deve aspettare che la compilazione finisca?
[piccola aggiunta]
questa domanda, al limite, l'avrei potuta "capire" se il C++ fosse un
linguaggio implementato solo sotto forma di interpreti (o compilatori
just-in-time, se non abbastanza furbi), dove il "carico" del lavoro sarebbe
stato moltiplicato per ogni singola volta che l'applicazione sarebbe stata
usata.
-- 
Under construction


Per rendere il discorso più preciso, calcoliamo la complessità 
computazionale in termini di istanziazioni richieste.
Per es. il classico calcolo di n! (n fattoriale) tramite template ha 
complessità O(n) perché richiede a*n + b istanziazioni, con a e b costanti.
Kiuhnm

 Kiuhnm

 performanti.
Io credo che la domanda di Kiuhnm sia da intendersi in senso anche
teorico. Ovvero: il sistema di template di C++ č turing completo.
Volendo ha quindi chiedersi quale sia la complessitā di un algoritmo
scritto in tale sistema.
Mi viene anche da chiedermi se si riesce ( da un punto di vista teorico
direi di si ) a scrivere un programma la cui compilazione *non* termina.
Kiuhnm?
-- 
blog:  
http://www.akropolix.net/rik0/blogs
 | Uccidete i filosofi,
site:  
http://www.akropolix.net/rik0/
      | tenetevi riso e
forum: 
http://www.akropolix.net/forum/
     | bacchette per voi.

 Kiuhnm?
Certo. Per es. ti basta eliminare la specializzazione nell'esempio del 
fattoriale. In pratica ci sono dei limiti, perņ.
Kiuhnm

 dovrebbe fare e perché č stata scelta questa strategia ?
Vedi MPL, Loki, ecc...
Kiuhnm

 fattoriale.
me idiot. uff, porto la giustificazione, dopodomani ho un esame di
teoria dell'informazione :)
tra l'altro siamo credo una delle poche facoltà dove si fa anche teoria
dell'informazione algoritmica (basata sui lavori di Chaitin e Kolmogorov
etc). E pensa che ho scoperto ieri che è uscito un testo di Chaitin in
Italia di recente (ma chiaramente nella mia città non c'è, e per quando
abbia discrete doti di lettore "tecnico", buttare giù un libro di
matematica in tre giorni non rientra nelle mie facoltà).


 matematica in tre giorni non rientra nelle mie facoltà).
The Quest for Omega ?
Prima o poi lo leggerò.
Kiuhnm


Ti confesso che sono talmente stretto con i tempi che non ho manco
guardato di preciso di cosa sia traduzione, fatto č che gli appunti che
ho sono talmente presi male che mi sto facendo la teoria da solo.
Sperando di non cadere in errori. :(



Tanto per dare concretezza alla domanda, ecco un esempio di lista di tipi:
---------
#include <iostream>
using namespace std;
struct nil {};
// H = testa (elemento)
// T = coda (lista)
template <class H, class T = nil>
struct List
{
     typedef H h;
     typedef T t;
};
template <class H, class T>
struct PopBack_loop
{
     typedef List<H, typename PopBack_loop<typename T::h, typename 
T::t>::ret> ret;
};
template <class H>
struct PopBack_loop<H, nil>
{
     typedef nil ret;
};
// Rimuove l'ultimo elemento dalla lista L.
template <class L>
struct PopBack
{
     typedef typename PopBack_loop<typename L::h, typename L::t>::ret ret;
};
template <>
struct PopBack<nil>
{
     typedef nil ret;
};
int main()
{
     typedef List<int> L1;			// L1 = int
     typedef List<double, L1> L2;	// L2 = double, int
     typedef List<char, L2> L3;		// L3 = char, double, int
     cout << typeid(L3::h).name() << endl;			// char
     cout << typeid(L3::t::h).name() << endl;		// double
     cout << typeid(L3::t::t::h).name() << endl;		// int
     // Rimuoviamo l'ultimo elemento della lista.
     typedef PopBack<L3>::ret L4;
     cout << typeid(L3).name() << endl;			// char, double, int
     cout << typeid(L4).name() << endl;			// char, double
}
---------
Questa lista può benissimo essere usata come coda, infatti è possibile 
inserire un elemento con List<elem,L> e rimuovere l'elemento più vecchio 
con PopBack<L>.
La funzione PopBack percorre tutta la lista e rimuove l'ultimo elemento 
sostituendolo con un nil. Il suo tempo d'esecuzione è O(n).
Il tempo d'esecuzione di List è invece O(1) poiché non vi è alcuna 
chiamata ricorsiva.
E' possibile realizzare una PopBack che impieghi tempo O(1)?
Kiuhnm

 E' possibile realizzare una PopBack che impieghi tempo O(1)?
Rispondo per gli eventuali lurker interessati e perché non mi piace 
lasciare le cose a metà.
Rappresentiamo la coda tramite due liste L ed R:
Queue { L R }
Consideriamo la seguente coda rappresentata tramite una semplice lista:
[9 8 7 6 5 4 3 2 1]
Gli elementi vengono aggiunti a sinistra ed estratti da destra.
Immaginiamo di spezzare tale lista in due liste L ed R tali che:
L = [9 8 7 6 5]
R = [1 2 3 4]
La lista R contiene gli ultimi elementi della lista originale invertiti.
Push(x) aggiunge x in testa ad L, impiegando tempo O(1).
Pop() elimina un elemento dalla testa di R, impiegando tempo O(1).
Quindi Push(10) restituisce
L = [10 9 8 7 6 5]
R = [1 2 3 4]
mentre Pop()
L = [9 8 7 6 5]
R = [2 3 4]
Quando R non contiene più elementi, è necessario trasferire tutti gli 
elementi da L ad R, invertendoli:
Pop()
L = [9 8 7 6 5]
R = [2 3 4]
Pop()
L = [9 8 7 6 5]
R = [3 4]
Pop()
L = [9 8 7 6 5]
R = [4]
Pop()
L = []
R = [5 6 7 8 9]
Il trasferimento da L ad R richiede tempo lineare rispetto al numero di 
elementi in L, quindi questa coda è amortized O(1).
Per velocizzare la compilazione, questo è più che sufficiente.
Si può comunque rendere la coda O(1).
Partiamo dalla coda
L = [8 7 6 5]
R = [1 2 3 4]
Modifichiamo Push e Pop in modo che eseguano il trasferimento da L ad R 
ogniqualvolta |L| = |R|+1 (dove |X| indica la lunghezza della lista X).
Nell'esempio, Push(9) esegue due passi:
1) aggiunge l'elemento
L = [9 8 7 6 5]
R = [1 2 3 4]
2) trasferisce L in R
L = []
R = [1 2 3 4 5 6 7 8 9]
Questo metodo sembra in realtà portare ad un peggioramento, infatti il 
trasferimento necessita dello scorrimento di R per trovare l'ultimo 
elemento e dello scorrimento della lista L per invertirla.
Questo è il punto cruciale.
Ripartiamo dal punto 1:
L = [9 8 7 6 5]
R = [1 2 3 4]
Quanto tempo ci è concesso per eseguire il trasferimento da L ad R?
Aggiungiamo una nuova lista T (temp) alla coda:
L = []
R = [1 2 3 4]
T = [9 8 7 6 5]
Per il momento, ignoriamo T. Il trasferimento avviene solo quando |L| = 
|R|+1 quindi il prossimo trasferimento avverrà tra non meno di 5 passi.
Abbiamo tutto il tempo per gestire T.
Aggiungiamo una lista P (partial) alla coda:
L = []
R = [1 2 3 4]
T = [9 8 7 6 5]
P = []
Senza sprecare tempo, possiamo già inserire il primo elemento di T in P 
nella Push o Pop che attiva il trasferimento:
L = []
R = [1 2 3 4]
T = [8 7 6 5]
P = [9]
Grazie a P, possiamo invertire T in modo incrementale estraendo ad ogni 
passo un elemento da T ed inserendolo in P.
Aggiungiamo R2 alla coda:
L = []
R = [1 2 3 4]
R2= []
T = [8 7 6 5]
P = [9]
Per poter aggiungere un elemento in fondo ad R è necessario costruire 
un'altra lista R. Non si può aggiornare R stessa. Allora ricostruiremo R 
in R2. Quando finiremo di scorrere gli elementi di R, vorrà dire che 
potremo aggiungere l'intera P (ormai completa) come ultimo elemento di R2.
Cosa succede se nel frattempo vengono eseguite delle Pop che modificano 
R? La nostra R2 non sarà più valida. Per evitare ciò, introduciamo un 
"puntatore" R3 che punterà al primo elemento della lista R2 attuale. 
Ogniqualvolta verrà eseguita una Pop, R3 avanzerà in R2. La costruzione 
di R2 procederà indipendemente e, alla fine R3 punterà alla parte di R2 
valida.
Questo farà sì che la ricerca dell'ultimo elemento in R e l'inversione 
di L avvengano incrementalmente.
Ma ha senso parlare di costruzione incrementale nell'ambito dei 
template? Sì e no. Per mantenere un certo "ordine d'esecuzione" è 
necessario che L, R, R2, R3, T e P vengano passati come singoli 
argomenti al template e che la chiamata ricorsiva sia unica e coinvolga 
contemporaneamente tutti i parametri.
Comunque l'ultima parte non è fondamentale nell'ambito dei template in 
quanto poco importa il tempo di risposta. Quello che interessa è il 
tempo complessivo, quindi la versione amortized O(1) è caldamente 
raccomandata dato che è /molto/ più semplice e complessivamente più veloce.
Kiuhnm