Фон
Рассмотрим следующее:
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
};
};
Это общий пример, и мы можем получить значение числа Фибоначчи как константу времени компиляции:
int main(void)
{
std::cout << "Fibonacci(15) = ";
std::cout << Fibonacci<15>::value;
std::cout << std::endl;
}
Но вы, очевидно, не можете получить значение во время выполнения:
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;
}
Поскольку fibb не является константой времени компиляции.
Вопрос
Итак, мой вопрос:
Каков наилучший способ заглянуть в эту таблицу во время выполнения? Наиболее очевидное решение (и "решение" следует воспринимать легкомысленно) заключается в том, чтобы иметь большой оператор 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;
}
Но теперь размер таблицы очень жестко закодирован, и было бы непросто расширить его, скажем, 40.
Единственный, с которым я столкнулся, имеет похожий метод запроса:
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;
}
Что, кажется, отлично работает. Единственные две проблемы, которые я вижу:
-
Потенциально большой стек вызовов, поскольку для вычисления Fibonacci < 2 требуется, чтобы мы проходили через TableMax до 2, и:
-
Если значение находится вне таблицы, оно возвращает ноль, а не вычисляет его.
Так что я чего-то не хватает? Кажется, должен быть лучший способ выбрать эти значения во время выполнения.
Возможно ли вариант метапрограммирования шаблона оператора switch, который генерирует оператор switch до определенного числа?
Спасибо заранее.
