traductores - variables y constantes en c++
Obtención de metaprogramación de constantes de tiempo de compilación en tiempo de ejecución (8)
Fondo
Considera lo siguiente:
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
};
};
Este es un ejemplo común y podemos obtener el valor de un número de Fibonacci como una constante de tiempo de compilación:
int main(void)
{
std::cout << "Fibonacci(15) = ";
std::cout << Fibonacci<15>::value;
std::cout << std::endl;
}
Pero obviamente no puedes obtener el valor en tiempo de ejecución:
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;
}
Porque fibb no es una constante en tiempo de compilación.
Pregunta
Entonces mi pregunta es:
¿Cuál es la mejor manera de echar un vistazo a esta tabla en tiempo de ejecución? La solución más obvia (y la "solución" debe tomarse a la ligera), es tener una declaración de conmutación grande:
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;
}
Pero ahora el tamaño de la tabla está muy codificado y no sería fácil expandirlo para decir, 40.
El único que se me ocurrió que tiene un método de consulta similar es este:
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;
}
Lo cual parece funcionar bien. Los únicos dos problemas que veo son:
Pila de llamadas potencialmente grande, ya que calcular Fibonacci <2> requiere pasar por TableMax hasta 2, y:
Si el valor está fuera de la tabla, devuelve cero en lugar de calcularlo.
Entonces, ¿hay algo que me falta? Parece que debería haber una mejor manera de elegir estos valores en tiempo de ejecución.
¿Una versión de metaprogramación de plantilla de una declaración de cambio quizás, que genera una instrucción de cambio hasta cierto número?
Gracias por adelantado.
Con C ++ 11: puedes crear un std::array y un getter simple: 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);
}
Esto debería funcionar...
template <int N> class EXPAND {
public:
static const string value;
};
template <> class EXPAND<0> {
public:
static const string value;
};
template <int N> const string EXPAND<N>::value = EXPAND<N-1>::value+"t";
const string EXPAND<0>::value = "t";
int main() {
cout << EXPAND<5>::value << endl;
}
Puede generar el interruptor o una matriz estática usando técnicas de metaprogramación de preprocesador. Es una buena decisión si la complejidad no excede las limitaciones de ese enfoque, y prefiere no ampliar su cadena de herramientas con pasos adicionales que generan código o datos.
Sé que esta pregunta es antigua, pero me intrigó y tuve que esforzarme sin un contenedor dinámico lleno en tiempo de ejecución:
#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
Esto parece funcionar, y cuando se compila con optimizaciones (no estoy seguro de si iba a permitir eso), la pila de llamadas no llega a la profundidad - hay una recursión de tiempo de ejecución normal en la pila, por supuesto, para valores (argumentos) n> N, donde N es el tamaño de tabla utilizado en la instanciación de la plantilla. Sin embargo, una vez que se pasa por debajo del tamaño de tabla, el código generado sustituye una constante calculada en tiempo de compilación o, en el peor, un valor "calculado" al pasar por una tabla de salto (compilada en gcc con -c -g -Wa, -adhlns = main. y revisó el listado), lo mismo que creo que resultaría en su declaración de cambio explícita.
Cuando se usa así:
int main()
{
std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << ''/n'';
std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << ''/n'';
}
No hay ninguna llamada a un cálculo en absoluto en el primer caso (valor calculado en tiempo de compilación), y en el segundo caso la profundidad de la pila de llamadas es en el peor de los casos:
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
Es decir, recurre hasta que encuentre un valor en la "Tabla". (verificado al pasar por Desmontaje en el depurador línea por línea, también reemplazando las entradas de prueba por un número aleatorio <= 45)
La parte recursiva también podría ser reemplazada por la solución iterativa lineal:
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;
}
}
}
Si tiene un compilador de C ++ que admite plantillas variadic (C ++ 0x estándar), puede guardar la secuencia fibonacii en una tupla en el momento de la compilación. En tiempo de ejecución, puede acceder a cualquier elemento de esa tupla indexando.
#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;
}
Uno de los tennants básicos de C (y en su mayor parte C ++) es que no pagas por lo que no necesitas.
La generación automática de tablas de búsqueda no es algo que el compilador deba hacer por usted. Incluso si necesita esa funcionalidad, no todos necesariamente lo hacen.
Si desea una tabla de búsqueda, escriba un programa para hacer una. Luego usa esa información en tu programa.
No utilice un metaprograma de plantilla si desea calcular los valores en tiempo de ejecución, solo use un programa regular para calcular los valores.
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'';
}
Después de pensar mucho en el problema, se me ocurrió esta solución. Por supuesto, todavía tiene que agregar los valores a un contenedor en tiempo de ejecución, pero (lo que es más importante) no se computan en tiempo de ejecución.
Como nota al margen, es importante no definir Fibonacci<1> encima de Fibonacci<0> , o su compilador se confundirá mucho cuando resuelva la llamada a Fibonacci<0>::add_values , ya que Fibonacci<0> especialización de plantillas de Fibonacci<0> no ha sido especificado.
Por supuesto, TMP tiene sus limitaciones: necesita un máximo precalculado, y obtener los valores en tiempo de ejecución requiere recurrencia (ya que las plantillas se definen recursivamente).
unsigned fibonacci(unsigned index)
{
switch (index)
{
case 0:
return Fibonacci<0>::value;
case 1:
return Fibonacci<1>::value;
default:
return fibonacci(index - 1) + fibonacci(index - 2);
}
}
¿Esto no soluciona tu problema? Quiero decir que esto es después de todo una secuencia de fibonacci. Por supuesto que no puedes listarlo. El propósito de este "ejercicio" (aunque sea estúpido :)) tiene que ser apuntar lo que se puede hacer con las plantillas y, en este caso, aplicarlo con un algoritmo recursivo para generar números de Fibonacci. ¿O me estoy perdiendo algo?