Quanto tempo può davvero richiedere la compilazione di template?

Question

La metaprogrammazione del modello può essere utilizzata per calcolare cose come fattoriali in fase di compilazione anziché durante il runtime. Ho sentito dire che alcuni concorsi di programmazione hanno introdotto limitazioni al tempo di compilazione esattamente come l'abuso di metaprogrammazione di template.

C'è qualche esempio innocente di utilizzo di modelli che richiede veramente molto tempo (come diverse ore) per compilare?

Answer 1

Ho sentito dire che l'International Olympiad in Informatics (uno di questi concorsi di programmazione) ha introdotto per la prima volta limiti di tempo di compilazione dopo che un concorrente ha creato un vettore di 7 dimensioni utilizzando una tecnica molto simile a this. Il suo codice doveva essere lasciato compilare durante la notte, era così brutto. Penso che sia accaduto un po 'di tempo alla fine degli anni '90.

Answer 2

Il meccanismo di modello è completo di Turing. Ciò significa che, almeno in teoria, qualsiasi computazione che può essere eseguita può essere eseguita in questo momento (in pratica è possibile imbattersi in limiti rigidi sulla profondità del template, ecc. Abbastanza velocemente, ma dipende dal compilatore).

Se si desidera o meno fare questa è una domanda a parte. Puoi banalmente abbinare il tuo criterio di "ore da compilare" usando un costoso algoritmo. Ma ci sono anche codici più pratici come this one implementing an FFT; danno che una grande quantità di dati sufficiente impostare e ci vorrà un po '...

Answer 3

Prova questo (io ho usato Visual Studio 2005)

template <int M, int N> 
struct Ack 
{ 
    enum { value = Ack<M - 1, Ack<M, N - 1>::value >::value }; 
}; 

template <int M> 
struct Ack<M, 0> 
{ 
    enum { value = Ack<M - 1, 0>::value }; 
}; 

template <> 
struct Ack<0, 0> 
{ 
    enum { value = 1 }; 
}; 

template <int N> 
struct Ack<0, N> 
{ 
    enum { value = N + 1 }; 
}; 

void main() 
{ 
    printf("Result: %d\n", Ack<150, 150>::value); 
} 

' forse Sembra horribble, ho solo cercato di scrivere un equivalente a questo carina la funzione lisp

(defun ack(m, n) 
cond ((= m 0) (+ n 1)) 
    ((= n 0) ack(- m 1) n) 
    (t (ack (- m 1) (ack m (-n 1)))) 
) 

nostro insegnante ha detto che è la funzione Ferma, ma non ne sono sicuro ...