Возможно, вы захотите повысить уровень оптимизации вашего компилятора Си.С gcc -O3, что имеет большое значение, снижение с 2,015 секунд до 0,766 секунд, сокращение примерно на 62%.
Помимо этого, вам необходимо убедиться, что вы тестировали правильно.Вы должны запустить каждую программу десять раз, удалить выбросы (самый быстрый и самый медленный), а затем усреднить остальные восемь.
Кроме того, убедитесь, что вы измеряете время процессора, а не время часов.
Что-то меньшее, чем я, я бы не стал рассматривать приличный статистический анализ, и он вполне может быть подвержен шуму, делая ваши результаты бесполезными.
Для чего стоит, эти тайминги C выше были для семи прогонов с выбросамиперед усреднением.
Фактически, этот вопрос показывает, насколько важен выбор алгоритма при достижении высокой производительности.Хотя рекурсивные решения, как правило, элегантны, из-за ошибки вы дублируете лот вычислений.Итеративная версия:
int fib(unsigned int n) {
int t, a, b;
if (n < 2) return 1;
a = b = 1;
while (n-- >= 2) {
t = a + b;
a = b;
b = t;
}
return b;
}
дополнительно уменьшает время, затрачиваемое с 0,766 секунды до 0,078 секунды, дальнейшее сокращение на 89% и колоссальное сокращение на 96% по сравнению с исходным кодом.
И, в качестве последней попытки, вы должны попробовать следующее, которое объединяет таблицу поиска с вычислениями за пределами определенной точки:
static int fib(unsigned int n) {
static int lookup[] = {
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229, 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
24157817, 39088169, 63245986, 102334155, 165580141 };
int t, a, b;
if (n < sizeof(lookup)/sizeof(*lookup))
return lookup[n];
a = lookup[sizeof(lookup)/sizeof(*lookup)-2];
b = lookup[sizeof(lookup)/sizeof(*lookup)-1];
while (n-- >= sizeof(lookup)/sizeof(*lookup)) {
t = a + b;
a = b;
b = t;
}
return b;
}
Это снова сокращает времяно я подозреваю, что мы достигли цели уменьшения прибыли здесь.