SORU
11 Temmuz 2014, Cuma


Nasıl derleme zamanı (katlanarak) daha hızlı çalıştırma daha olabilir mi?

Kodu aşağıdaki ile Fibonacci sayıları hesaplarkatlanarak yavaşalgoritma:

#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;
}

Ve derleme zamanında-zamanında 45 Fibonacci sayısı ve 91 kişi hesaplıyorum.

Aslında ilginç GCC 4.9 kodu derler ve bir saniyeden daha kısa bir süre içinde fib91 hesaplar, ama bir süre fib(45) tükürmeyi gerektirir.

Sorum şu: eğer GCC fib(91) hesaplama optimize ve katlanarak yavaş yol almak için yeterince akıllı İse, ne oldu fib(45) aynı hakkı vermiyor?

Yukarıdaki GCC fib iki derlenmiş hallerinin hızlı olduğu fonksiyon ve diğer katlanarak yavaş üretir anlamına mı geliyor?

Sorudeğilderleyici fib(91) hesaplama optimize nasıl (Evet! Memoization bir tür kullanın), ama eğer fib fonksiyonu optimize etmek için nasıl bilir, neden fib(45) için aynı şeyi yapmaz? Ve, orada fib işlevi iki ayrı derleme. Biri yavaş, diğeri hızlı?

CEVAP
11 Temmuz 2014, Cuma


GCC constexpr fonksiyonlar (fib(n) (n) Θ bir hesaplama etkinleştirme) memoizing muhtemeldir. constexpr fonksiyonlar tamamen işlevsel olduğundan derleyici yapmak için güvenlidir.

Bu Θ(n) "algoritma" (memoization kullanarak) Θ(icinde . derleyici karşılaştırın ^sup>n) zaman algoritmayı çalıştırmak icinde altın oran olduğu) ve aniden derleyici çok daha mantıklı geliyor.

the constexpr page on cppreference (vurgu eklenmiştir):

Constexpr belirleyicisi olduğunu beyan edermümkünfonksiyon değerini değerlendirmek veya değişken zaman derlemek için.

constexpr belirleyicisi yokdeğilolduğunu beyan ederimgereklifonksiyon değerini değerlendirmek veya değişken zaman derlemek için. Sadece GCC derleme ya da derleme zamanı hesaplama dil kurallarına uygun değilse zamanında değerlendirmek isteyip istemediğinizi seçmek için kullanarak ne olduğunu tahmin edebilirsiniz. Ya da,-dava-davanın esasına seçin ve hala doğru olabilir.

İstersenizzorladerleme zamanında, constexpr fonksiyon burada değerlendirmek için derleyici bunu basit bir hile.

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);
};

Kodunuzun geri kalanı daha sonra derleme zamanında değerlendirilir olacaklarına dair garanti fib<45>::value fib<91>::value erişebilirsiniz.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Dirty Loops

    Dirty Loops

    21 Mayıs 2007
  • Jordie Jordan

    Jordie Jorda

    27 Ocak 2008
  • Ryan Ha

    Ryan Ha

    9 NİSAN 2006