C 语言 clock， 函数，例：计算多项式值

/**
 * clock(): 捕捉从程序开始运行到 clock() 被调用时所耗费的时间。
 * 这个时间单位是 clock tick, 即“时钟打点”。
 * 常数 CLK_TCK: 机器时钟每秒所走的始终打点数。
 * In Macintosh or C99, CLK_TCK == CLOCKS_PER_SEC
 * http://www.cplusplus.com/reference/ctime/CLOCKS_PER_SEC/
 */

我把老师说的话都敲了一遍哈哈。为了测试两种算法，哪一种的效率更高，我们就需要有一个工具来记录这个算法做完这件事花费了多长时间。clock() 函数就是 C 语言所提供的工具，当然其他的语言也有，找找就能找到的。

\(x\) 处的值

\[f(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1} + a_nx^n \]

double f1(int n, double a[], double x)
{
    int i;
    double p = a[0];
    for (i = 1; i <= n; i++)
        p += (a[i] * pow(x, i));
    return p;
}

传入阶数 n，系数放在数组 a 里面，和要计算的 x。先从这个常数项 a[0] 开始，令 p 等于 a[0]，然后我们就做一个循环的累加求和的过程。每一次求和，就求和的是多项式里面的第 i 项，也就是 a[i] 乘以 x 的 i 次方。看上去这是一个特别简单的程序，但是呢，如果在正式的程序里面，你真的这么去实现这个功能的话，那会被专业的程序员严重鄙视的，我们不能这么写哈。

专业的程序员怎么处理这个问题呢？早在好几百年以前，我们有个老祖宗叫做秦九韶的，他就给出了一个非常聪明的算法。他是巧妙地利用了一下结合律，每一次把 x 当成一个公因子提出来，这样一层一层往里面提公因子。

\[f(x) = a_0 + x(a_1 + x(...(a_{n-1} + x(a_n))...)) \]

那我们在写程序计算的时候呢，这个程序是从里往外算的。这个是我们实现这个函数的标准程序

double f2(int n, double a[], double x)
{
    int i;
    double p = a[n];
    for (i = n; i > 0; i--)
        p = a[i-1] + x*p;
    return p;
}

令 p 从 a[n] 开始，然后每一次用 x 乘以这个括号里面已经算出来的这个 p，然后再加上前面那一项的系数 a[i-1]。

那，凭什么说第二个函数就比第一个函数实现得要好呢？凭什么第一个函数就要被鄙视呢？因为第一个函数慢好多。到底谁快谁慢呢？不服气的话，我们要来测一下

clock() 函数

那在 C 语言里头呢，提供了一个这样的工具。C 语言提供了一个函数，叫做 clock。这个函数可以捕捉从程序开始运行，一直到这个函数被调用那个时刻所耗费的时间，但是它这个时间的单位，是 clock tick，翻译成“时钟打点“。跟它配套的，我们还有一个常数，叫 CLOCKS_PER_SEC (在 C99 以前，叫 CLK_TCK,实际上就是 clock tick 的一个缩写)，给出的是这个机器时钟每秒钟走的时钟打点的数。那这个数到底等于多少呢？不同的机器可能都不一样。这两个东西配合在一起我们就可以算出来一个函数到底跑了多少秒钟。

#include <stdio.h>
#include <time.h>   /* for clock() */

clock_t start, stop;
/* clock_t 是 clock() 函数返回的变量类型 */
double duration;
/* 记录被测函数运行时间，以秒为单位 */

int main()
{
    /* 不在测试范围内的准备工作写在 clock() 调用之前 */
    start = clock();    /* 开始计时 */
    foo();              /* 把被测函数加在这里 */
    stop = clock();     /* 停止计时 */
    duration = ((double)(stop-start))/CLOCKS_PER_SEC;
    /* 其他不在测试范围的处理写在后面，例如输出 duration 的值 */
    return 0;
}

foo() 函数，就是你要测的函数。这里的命名呢涉及到历史遗留问题，在很多的例子代码中，有的变量或者函数的命名是 foo。foobar 是计算机程序领域里的术语，并无实际用途和参考意义。在计算机程序设计与计算机技术的相关文档中，术语 foobar 是一个常见的无名氏化名。

clock() 函数返回的是从这个程序开始运行，直到调用的那个时刻所耗费的时间。所以在函数开始之前调用 clock() 存到 start 这个变量里面,在函数执行结束之后，紧接着又调用一次 clock()，存到 stop 这个变量里边。那么 stop 里边存的是什么呢？就是 main() 函数开始执行，一直到这次 clock 被调用的时候，一共走了多少个 ticks。所以我们用 stop - start 就得到了 foo() 的执行过程中间一共经历了多少个 ticks，最后我们再除一下这个常数，就得到了以秒为单位的这个 duration。

下面我们就一个具体的多项式来看一下，计算 \(x\) = 1.1 处的值 \(f(1.1)\)

\[f(x) = \sum_{i=0}^{9}i \cdot x^i \]

它的系数呢，我们就让第 i 个系数就等于 i 好了。然后我们来跑一下，看看它们分别跑了多少时间。

#include <stdio.h>
#include <math.h>   /* for pow() */
#include <time.h>   /* for clock() */

#define MAXN 10     /* 多项式最大项数，即多项式阶数+1 */
int main()
{
    int i;
    double a[MAXN]; /* 存储多项式的系数 */
    for (i = 0; i < MAXN; i++)
        a[i] = i;

    start = clock();
    f1();
    stop = clock();
    duration = ((double)(stop-start))/CLOCKS_PER_SEC;
    printf("ticks1 = %f\n", (double)(stop-start));
    printf("duration1 = %f\n", duration);

    start = clock();
    stop = clock();
    duration = ((double)(stop-start))/CLOCKS_PER_SEC;
    printf("ticks2 = %f\n", (double)(stop-start));
    printf("duration2 = %f\n", duration);

    return 0;
}

当然你现在看起来呢，说这真是一个很傻的程序。因为没有一个很专业的程序员可以容忍说，我一段代码里头，居然有两个片段几乎是一模一样的。如果你看到这种情况，重复的情况，你应该怎么去做一个更好的处理呢？显然你应该会写一个函数去做这件事情。Anyway （无论如何），先跑一下。跑出来的结果有可能都是 0，这是因为这两个函数跑得实在是太快了，它们的运行时间都不到一个 tick，所以 clock() 函数根本捕捉不到它的区别。那这怎么办呢？如何测出不到1个tick的程序运行时间？重复

跑一次捕捉不到，跑 10 次、跑 100 次、跑 1000 次、跑 10000 次，积累一点运行时间，一直跑到间隔的时间能够被 clock() 捕捉到。最后计算单次时间的时候，你只要把总时间除以重复的次数，你就得到了这个函数一次运行的时间。

你将看到这两组数据的相对大小，应该都是差了一个数量级这个样子。所以我们就可以看到，为什么说第一个算法比较傻呢，它比第二个算法要慢了差不多一个数量级的样子。这个故事告诉我们，解决问题方法的效率，跟算法的巧妙程度有关。

再试一个多项式

给定另一个100阶多项式 \(f(x) = 1 + \sum_{i=1}^{100} \frac{x^i}{i}\)，用不同方法计算 \(f(1.1)\) 并且比较一下运行时间？