47 votes

Obtention des constantes de compilation à la métaprogrammation du modèle lors de l'exécution

Arrière-plan

Considérez les points suivants:

template <unsigned N>
struct Fibonacci
{
    enum
    {
    	value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
};

template <>
struct Fibonacci<1>
{
    enum
    {
    	value = 1
    };
};

template <>
struct Fibonacci<0>
{
    enum
    {
    	value = 0
    };
};

Il s'agit d'un exemple qui nous permet d'obtenir la valeur d'un nombre de Fibonacci comme une constante de compilation:

int main(void)
{
    std::cout << "Fibonacci(15) = ";
    std::cout << Fibonacci<15>::value;
    std::cout << std::endl;
}

Mais de toute évidence vous ne peut pas obtenir la valeur au moment de l'exécution:

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    // ensure the table exists up to a certain size
    // (even though the rest of the code won't work)
    static const unsigned fibbMax = 20;
    Fibonacci<fibbMax>::value;

    // get index into sequence
    unsigned fibb = std::rand() % fibbMax;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << Fibonacci<fibb>::value;
    std::cout << std::endl;
}

Parce que fibb n'est pas une constante de compilation.

Question

Donc ma question est:

Quel est le meilleur moyen pour avoir un aperçu de ce tableau au moment de l'exécution? La solution la plus évidente (et la "solution" doit être prise à la légère), est d'avoir une grande instruction switch:

unsigned fibonacci(unsigned index)
{
    switch (index)
    {
    case 0:
    	return Fibonacci<0>::value;
    case 1:
    	return Fibonacci<1>::value;
    case 2:
    	return Fibonacci<2>::value;
    .
    .
    .
    case 20:
    	return Fibonacci<20>::value;
    default:
    	return fibonacci(index - 1) + fibonacci(index - 2);
    }
}

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    static const unsigned fibbMax = 20;    

    // get index into sequence
    unsigned fibb = std::rand() % fibbMax;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << fibonacci(fibb);
    std::cout << std::endl;
}

Mais maintenant, la taille de la table est très codée en dur et il ne serait pas facile de l'étendre à-dire, 40.

Le seul que j'ai trouvé qui a une semblable méthode de requête est ceci:

template <int TableSize = 40>
class FibonacciTable
{
public:
    enum
    {
    	max = TableSize
    };

    static unsigned get(unsigned index)
    {
    	if (index == TableSize)
    	{
    		return Fibonacci<TableSize>::value;
    	}
    	else
    	{
    		// too far, pass downwards
    		return FibonacciTable<TableSize - 1>::get(index);
    	}
    }
};

template <>
class FibonacciTable<0>
{
public:
    enum
    {
    	max = 0
    };

    static unsigned get(unsigned)
    {
    	// doesn't matter, no where else to go.
    	// must be 0, or the original value was
    	// not in table
    	return 0;
    }
};

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    // get index into sequence
    unsigned fibb = std::rand() % FibonacciTable<>::max;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << FibonacciTable<>::get(fibb);
    std::cout << std::endl;
}

Qui semble fonctionner à merveille. Les deux seuls problèmes que je rencontre sont:

  • Potentiellement grande pile d'appel, puisque le calcul de Fibonacci<2> nécessite que l'on en passer par TableMax tout le chemin à 2, et:

  • Si la valeur est en dehors de la table, elle renvoie zéro plutôt que de calculer.

Donc, il y a quelque chose que je suis absent? Il semble qu'il devrait y avoir une meilleure façon de choisir ces valeurs lors de l'exécution.

Un modèle de la métaprogrammation version d'une instruction switch peut-être, qui génère une instruction switch jusqu'à un certain nombre?

Merci à l'avance.

30voto

rlbond Points 24215
template <unsigned long N>
struct Fibonacci
{
    enum
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<N-1>::add_values(v);
        v.push_back(value);
    }
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
    static void add_values(vector<unsigned long>& v)
    {
        v.push_back(value);
    }

};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<0>::add_values(v);
        v.push_back(value);
    }
};



int main()
{
    vector<unsigned long> fibonacci_seq;
    Fibonacci<45>::add_values(fibonacci_seq);
    for (int i = 0; i <= 45; ++i)
        cout << "F" << i << " is " << fibonacci_seq[i] << '\n';
}

Après beaucoup de réflexion sur le problème, je suis venu avec cette solution. Bien sûr, vous devez encore ajouter les valeurs dans un conteneur au moment de l'exécution, mais (surtout), ils ne sont pas calculés au moment de l'exécution.

Comme une note de côté, il est important de ne pas définir Fibonacci<1> - dessus Fibonacci<0>, ou de votre compilateur obtiendrez très confus quand il se résout à l'appel d' Fibonacci<0>::add_values, depuis Fibonacci<0>s'modèle de la spécialisation n'a pas été spécifié.

Bien sûr, TMP a ses limites: Vous avez besoin d'un précalculées maximum, et d'obtenir les valeurs au moment de l'exécution requiert la récursivité (puisque les modèles sont définis récursivement).

18voto

madoki Points 141

Je sais que cette question est ancienne, mais il m'a intrigué et j'ai dû avoir un aller à faire sans une dynamique récipient rempli au moment de l'exécution:

#ifndef _FIBONACCI_HPP
#define _FIBONACCI_HPP


template <unsigned long N>
struct Fibonacci
{
    static const unsigned long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value;

    static unsigned long long get_value(unsigned long n)
    {
        switch (n) {
            case N:
                return value;
            default:
                return n < N    ? Fibonacci<N-1>::get_value(n)
                                : get_value(n-2) + get_value(n-1);
        }
    }
};

template <>
struct Fibonacci<0>
{
    static const unsigned long long value = 0;

    static unsigned long long get_value(unsigned long n)
    {
        return value;
    }
};

template <>
struct Fibonacci<1>
{
    static const unsigned long long value = 1;

    static unsigned long get_value(unsigned long n)
    {
        return value;
    }
};

#endif

Cela semble fonctionner, et lorsqu'il est compilé avec les optimisations (pas sûr si vous avez été va permettre), la pile d'appel n'a pas profonde, il est normal d'exécution de la récursivité sur la pile de cours pour les valeurs (arguments) n > N, où N est le Taille_table utilisés dans le modèle de l'instanciation. Cependant, une fois que vous allez au-dessous de la Taille_table le code généré substitue une constante calculée au moment de la compilation, ou, au pire, une valeur "calculée" par la chute par un saut de table (compilé avec gcc -c -g -Wa,-adhlns=main.s et vérifié la liste), le même que je pense de votre commutateur explicite déclaration entraînerait.

Lorsqu'il est utilisé comme ceci:

int main()
{
    std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << '\n';
    std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << '\n';
}

Il n'y a pas d'appel à un calcul dans le premier cas (valeur calculée au moment de la compilation), et dans le second cas, la pile des appels en profondeur est au pire:

fibtest.exe!Fibonacci<40>::get_value(unsigned long n=41)  Line 18 + 0xe bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=42)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=43)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=45)  Line 18 + 0xe bytes    C++
fibtest.exe!main()  Line 9 + 0x7 bytes    C++
fibtest.exe!__tmainCRTStartup()  Line 597 + 0x17 bytes    C

I. e. il se répète jusqu'à ce qu'il trouve une valeur dans la "Table". (vérifié par l'exécution pas à pas de Démontage dans le débogueur, ligne par ligne, également en remplaçant le test ints par un nombre aléatoire <= 45)

La partie récursive pourrait également être remplacé par le linéaire de la solution itérative:

static unsigned long long get_value(unsigned long n)
{
    switch (n) {
        case N:
            return value;    
        default:
            if (n < N) {
                return Fibonacci<N-1>::get_value(n);
            } else {
                // n > N
                unsigned long long i = Fibonacci<N-1>::value, j = value, t;
                for (unsigned long k = N; k < n; k++) {
                    t = i + j;
                    i = j;
                    j = t;
                }
                return j;
            }
    }
}

4voto

sigidagi Points 520

Si vous avez un compilateur C ++ qui prend en charge les modèles variadiques (norme C ++ 0x), vous pouvez enregistrer la séquence fibonacii dans un tuple au moment de la compilation. Au moment de l'exécution, vous pouvez accéder à n'importe quel élément de ce tuple en indexant.

 #include <tuple>   
#include <iostream>

template<int N>
struct Fib
{
    enum { value = Fib<N-1>::value + Fib<N-2>::value };
};

template<>
struct Fib<1>
{
    enum { value = 1 };
};

template<>
struct Fib<0>
{
    enum { value = 0 };
};

// ----------------------
template<int N, typename Tuple, typename ... Types>
struct make_fibtuple_impl;

template<int N, typename ... Types>
struct make_fibtuple_impl<N, std::tuple<Types...> >
{
    typedef typename make_fibtuple_impl<N-1, std::tuple<Fib<N>, Types... > >::type type;
};

template<typename ... Types>
struct make_fibtuple_impl<0, std::tuple<Types...> >
{
    typedef std::tuple<Fib<0>, Types... > type;
};

template<int N>
struct make_fibtuple : make_fibtuple_impl<N, std::tuple<> >
{};

int main()
{
   auto tup = typename make_fibtuple<25>::type();
   std::cout << std::get<20>(tup).value;  
   std::cout << std::endl; 

   return 0;
}
 

4voto

Jarod42 Points 15729

Avec C ++11: vous pouvez créer un std::array et un simple getter: https://ideone.com/F0b4D3

 namespace detail
{

template <std::size_t N>
struct Fibo :
    std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value>
{
    static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value,
                  "overflow");
};

template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {};
template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {};

template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
    return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>(
        std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n];
}

template <std::size_t N>
constexpr std::size_t fibo(std::size_t n)
{
    return n < N ? fibo(n, make_index_sequence<N>()) : throw std::runtime_error("out of bound");
}
} // namespace detail

constexpr std::size_t fibo(std::size_t n)
{
    // 48u is the highest
    return detail::fibo<48u>(n);
}
 

0voto

James Caccese Points 730

L'un des locataires de C (et pour la plupart, C++), c'est que vous ne payez pas pour ce que vous n'avez pas besoin.

La génération automatique de tableaux est pas juste quelque chose que le compilateur a besoin de faire pour vous. Même si vous avez besoin de cette fonctionnalité, pas tout le monde forcement ne.

Si vous voulez une table de recherche, écrire un programme pour en faire un. Ensuite utiliser ces données dans votre programme.

Ne pas utiliser un modèle metaprogram si vous voulez des valeurs calculées au moment de l'exécution, il suffit d'utiliser un programme régulier pour calculer les valeurs.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X