Làm thế nào có thể thời gian biên dịch (theo cấp số nhân) nhanh hơn so với thời gian chạy?


0 Phiếu
Đã hỏi 24/5/2016 bởi looks_A (150 điểm)
Các bên dưới code tính toán số Fibonacci bằng một thuật toán theo cấp số nhân chậm : #include <cstdlib> #include <iostream> #define DEBUG(var) { std::cout << #var << ": " << (var) << std::endl; } constexpr auto fib(const size_t n) -> long long { return n < 2 ? 1: fib(n - 1) + fib(n - 2); } int main(int argc, char *argv[]) { const long long fib91 = fib(91); DEBUG( fib91 ); DEBUG( fib(45) ); return EXIT_SUCCESS; } và tôi đang tính số Fibonacci thứ 45 tại thời gian chạy, và một 91st compile thời gian. Một thực tế thú vị là rằng GCC 4.9 biên dịch code và tính fib91 trong một phần nhỏ của một giây, nhưng phải mất một thời gian để nhổ ra fib(45). Câu hỏi của tôi: nếu GCC là đủ thông minh để tối ưu hóa tính toán fib(91) và không có con đường chậm theo cấp số nhân, những gì dừng lại đó để làm tương tự cho fib(45)? Có nghĩa là GCC ở trên có sản xuất hai biên dịch Phiên bản của fib function nơi một là nhanh chóng và các khác theo cấp số nhân chậm? Câu hỏi là không làm thế nào compiler tối ưu hóa fib(91) tính toán (yeah! Nó sử dụng một loại memoization), nhưng nếu nó biết làm thế nào để tối ưu hóa chức năng fib, tại sao nó không làm tương tự cho fib(45)? Và, có hai album tổng hợp riêng biệt của các chức năng fib? Một trong những chậm, và nhanh chóng khác?

2 Câu trả lời

+1 Phiếu
Đã trả lời 04/6/2016 bởi ricotechn (640 điểm)
được bình chọn là câu trả lời hay nhất 06/6/2016 bởi Condition
 
Câu trả lời hay nhất
Tại thời điểm biên dịch compiler có thể memoize là kết quả của các chức năng. Điều này là an toàn, bởi vì function là một constexpr và do đó sẽ luôn quay trở lại cùng một kết quả của các đầu vào cùng một. Tại thời gian chạy nó có thể trong lý thuyết làm như vậy. Tuy nhiên, hầu hết các lập trình C++ sẽ nhăn tại optimization vượt qua kết quả đó trong cấp phát bộ nhớ ẩn.
Đã bình luận 06/6/2016 bởi Condition (200 điểm)
Về phần đầu tiên, ' const lâu fib91 = fib(91);' được tính vào thời gian compile , function toàn được thay thế bằng giá trị thực tế, không chắc chắn tại sao nó không làm điều đó cho fib45
Đã bình luận 06/6/2016 bởi Na_In (480 điểm)
Có lẽ '45' vượt quá giới hạn đệ quy. chơi với ' - fconstexpr - chiều sâu = Max_Recursion_Limit' để xem nếu giới hạn này vượt quá.
0 Phiếu
Đã trả lời 04/6/2016 bởi Vfound (480 điểm)
GCC có khả năng memoizing chức năng constexpr (cho phép một tính toán Θ(n) của fib(n)). Đó là an toàn cho compiler để làm bởi vì constexpr chức năng hoàn toàn chức năng. So sánh Θ(n) "biên dịch thuật toán" (sử dụng memoization) của bạn Θ (φ n ) chạy thời gian algorithm (trong đó φ là tỉ lệ vàng) và đột nhiên nó làm cho cảm giác hoàn hảo compiler là nhanh hơn rất nhiều. Từ constexpr trang trên cppreference (nhấn mạnh thêm vào):
constexpr specifier tuyên bố rằng nó có thể để đánh giá value của function hay variable compile thời gian.
constexpr specifier hiện không tuyên bố rằng đó là yêu cầu để đánh giá value của function hay variable compile thời gian. Vì vậy, một trong những chỉ có thể đoán những gì GCC chẩn đoán đang sử dụng để chọn để đánh giá tại thời điểm compile hoặc chạy thời gian khi một compile thời gian tính toán không bắt buộc theo các quy tắc ngôn ngữ. Nó có thể chọn một trong hai, trên cơ sở của trường hợp, và vẫn còn được chính xác. Nếu bạn muốn lực compiler để đánh giá của bạn function constexpr tại compile của thời gian, ở đây một thủ thuật đơn giản mà sẽ làm điều đó.
constexpr auto compute_fib(const size_t n) -> long long
{
    return n < 2 ? n : compute_fib(n - 1) + compute_fib(n - 2);
}
template <std::size_t N>
struct fib
{
    static_assert(N >= 0, "N must be nonnegative.");
    static const long long value = compute_fib(N);
};
trong phần còn lại của code của bạn bạn có thể sau đó access fib<45>::value hoặc fib<91>::value với đảm bảo rằng họ sẽ được đánh giá tại thời điểm compile .
Đã bình luận 04/6/2016 bởi n6856 (640 điểm)
câu hỏi này đòi hỏi phải biết ít lá cờ sử dụng để compile các chương trình

ToughDev Q&A là gì?

Trang web hỏi đáp cho các bạn đam mê lập trình, phát triển phần mềm và các vấn đề kỹ thuật khác. Với sự giúp đỡ của bạn, chúng tôi hy vọng sẽ xây dựng thành công một thư viện đầy đủ các câu hỏi và trả lời về tất cả các vấn đề có liên quan đến lập trình!







...