Biên soạn mẫu có thể mất bao lâu?

Question

Lập trình meta mẫu có thể được sử dụng để tính toán những thứ như giai thừa trong thời gian biên dịch thay vì trong thời gian chạy. Tôi đã nghe nói rằng một số cuộc thi lập trình đã giới thiệu những hạn chế về thời gian biên dịch chính xác để loại bỏ sự lạm dụng lập trình meta mẫu.

Có bất kỳ ví dụ tìm kiếm vô tội nào về việc sử dụng các mẫu có thời gian thực sự dài (như vài giờ) để biên dịch không?

Answer 1

Tôi nghe nói rằng Olympic quốc tế về Tin học (một cuộc thi lập trình) lần đầu tiên giới thiệu thời gian biên dịch sau khi một thí sinh tạo ra một vector 7 chiều sử dụng kỹ thuật giống như this. Mã của anh ta phải được biên soạn lại qua đêm nó rất tệ. Tôi nghĩ điều này đã xảy ra vào cuối những năm 90.

Answer 2

Cơ chế mẫu hoàn tất Turing. Điều này có nghĩa rằng trong lý thuyết ít nhất, bất kỳ tính toán có thể được thực hiện có thể được thực hiện tại thời gian biên dịch theo cách này (Trong thực tế, bạn có thể chạy vào giới hạn cứng về chiều sâu mẫu vv khá nhanh chóng nhưng điều này là trình biên dịch phụ thuộc).

Có hay không bạn muốn thực hiện việc này là một câu hỏi riêng. Bạn có thể trivially phù hợp với tiêu chí của bạn "giờ để biên dịch" bằng cách sử dụng một thuật toán đắt tiền. Nhưng cũng có nhiều mã thực tế hơn như this one implementing an FFT; cho rằng một dữ liệu đủ lớn đặt ra và nó sẽ mất một thời gian ...

Answer 3

Hãy thử điều này (i sử dụng 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); 
} 

Nó có lẽ dường như horribble, tôi chỉ cố gắng để viết một tương đương này dễ thương chức năng lisp

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

giáo viên của chúng tôi nói nó là Ferma chức năng, nhưng tôi không chắc chắn ...