获取斐波那契数列中每个数字的运行次

Question

#include <stdio.h>
#include <time.h>

void printFibonacci(int n) {    
    static int n1 = 0, n2 = 1, n3;    
    if (n > 0) {    
        n3 = n1 + n2;    
        n1 = n2;    
        n2 = n3;    
        printf("%d ", n3);    
        printFibonacci(n - 1);    
    }    
}

int main() {
    int n;
    struct timespec start, stop;
    double total_time;
    
    clock_gettime(CLOCK_REALTIME, &start);
    printf("Enter the number of elements: ");    
    scanf("%d", &n);    
    printf("Fibonacci Series: ");    
    printf("%d %d ", 0, 1);    
    printFibonacci(n - 2);
    
    clock_gettime(CLOCK_REALTIME, &stop);
    total_time = (stop.tv_sec - start.tv_sec) * 1e9;
    total_time = (total_time + (stop.tv_nsec - start.tv_nsec)) * 1e-9;
    printf("\nTime taken for each sequence: %lf", total_time);
    return 0; 
}

上面这个C程序让用户输入一个整数，然后程序会输出斐波那契数列。我想要做的是将斐波那契数列中每个数字的运行时间精确到纳秒。到目前为止，我的尝试是使用 clockgettime() 函数来获取 fibonacci 函数的开始和停止时间。但是，这只会输出函数花费的总时间，而不是每个单独序列花费的时间。我将如何修复此代码以便获取每个单独的序列时间？

例如，如果用户输入 12，我想要的输出将如下所示，其中显示每个序列时间：

Enter the number of elements: 12        
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89           
Time taken for each sequence: 0.1023, 0.2024, 0.3025, 0.7024, 0.9323, 0.12023, 0.78923, 0.6723, 0.12323, 0.9033, 0.34523, 0.123423

Answer 1

好像您在主程序上使用了时钟，这意味着它确实如您所说计算了函数的总运行时间。为了计算您完成一个序列所花费的时间，您应该考虑移动

clock_gettime(CLOCK_REALTIME, &start);

并且：

clock_gettime(CLOCK_REALTIME, &stop);
total_time = (stop.tv_sec - start.tv_sec) * 1e9;
total_time = (total_time + (stop.tv_nsec - start.tv_nsec)) * 1e-9;

对于 printFibonacci 的开始和结束，恭敬地，在这种情况下，在每次递归中，您将看到序列发生的确切时间。

Answer 2

按照问题中的编码，计算整个序列的时间，包括用户输入数字所花费的时间和 printf 输出值所花费的时间。这是没有意义的。

此外，您将秒数乘以 10⁹，然后将纳秒数也除以 10⁹：您应该做一个或另一个，但不能同时做。

如果你想为每个数字的计算计时，你应该在前 2 个数字相加之前检索时钟，并在 3 个赋值之后立即重新检索时钟。尝试对这样一个简单的操作计时是相当困难的：clock_gettime() 不是正确的工具，您更有可能只测量 clock_gettime 的开销，CLOCK_REALTIME 的不精确性，可能当您测量 CLOCK_REALTIME 而不是当前进程的运行时时，异步进程会中断您的程序。您可能应该改用 clock()，但测量值可能微不足道。中间时间应存储在 static 数组中，以便 main 打印它们。

这是修改后的版本：

#include <stdio.h>
#include <time.h>

#define MAX_TIMINGS 100
static double timings[MAX_TIMINGS];
static int timing_index = 2;

void printFibonacci(int n) {    
    static int n1 = 0, n2 = 1, n3;    
    if (n > 0) {  
        struct timespec start, stop;
        clock_gettime(CLOCK_REALTIME, &start);
        n3 = n1 + n2;    
        n1 = n2;    
        n2 = n3;    
        clock_gettime(CLOCK_REALTIME, &stop);
        if (timing_index < MAX_TIMINGS) {
            timings[n] = (stop.tv_sec - start.tv_sec) * 1e9 +
                         (stop.tv_nsec - start.tv_nsec);
        }
        printf("%d ", n3);
        printFibonacci(n - 1);
    }
}

int main() {
    int i, n;
    double total_time = 0;
    
    printf("Enter the number of elements: ");    
    scanf("%d", &n);    
    printf("Fibonacci Series: ");    
    printf("%d %d ", 0, 1);    
    printFibonacci(n - 2);
    printf("\n");
    printf("Time taken for each number:");
    for (i = 0; i <= n; i++) {
        printf(" %.0fns", timings[i]);
        total_time += timings[i];
    }
    printf("\n");
    printf("Total time: %.0fns\n", total_time);
    return 0; 
}

输出：

Enter the number of elements: 20
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Time taken for each number: 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns
Total time: 0ns

毫不奇怪，所有时间都是空的。测量顺序生成器的每个数字的时间是没有意义的。

相反，时间对于经典的递归实现很重要，其中涉及许多递归调用，即使是中等大的参数。

这里有一个比较经典的例子：

#include <stdio.h>
#include <time.h>

unsigned long long fib(int n) {
    if (n < 2)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

int main() {
    int i, n;
    double total_time = 0;

    printf("Enter the number of elements: ");
    if (scanf("%d", &n) != 1)
        return 1;
    double timings[n + 1];
    printf("Fibonacci Series:");
    for (i = 0; i <= n; i++) {
        struct timespec start, stop;
        unsigned long long res;
        clock_gettime(CLOCK_REALTIME, &start);
        res = fib(i);
        clock_gettime(CLOCK_REALTIME, &stop);
        timings[i] = ((stop.tv_sec - start.tv_sec) * 1e9 +
                      (stop.tv_nsec - start.tv_nsec));
        printf(" %llu", res);
    }
    printf("\n");
    printf("Time taken for each number:");
    for (i = 0; i <= n; i++) {
        printf(" %.0fns", timings[i]);
        total_time += timings[i];
    }
    printf("\n");
    printf("Total time: %.0fns\n", total_time);
    return 0;
}

输出：

Enter the number of elements: 20
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Time taken for each number: 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 1000ns 0ns 1000ns 1000ns 2000ns 5000ns 6000ns 10000ns 18000ns 38000ns 69000ns
Total time: 151000ns

获取斐波那契数列中每个数字的 运行 次

Get run-time of each number in a Fibonacci sequence

c

time

获取斐波那契数列中每个数字的运行次