首页 » 读书笔记 » 编程珠玑II

性能监视工具

首先是一段求素数的代码:

#include <stdio.h>

int prime(int n)
{
    for(int i = 2; i < n; ++i) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int n = 1000;
    for(int i = 2; i <= n; ++i) {
        if(prime(i)) {
            printf("%d\n", i);
        }
    }

    return 0;
}

编译、运行,并查看性能分析:

$ gcc --std=c99 -pg -o prime prime.c
$ ./prime |wc -l
168
$ gprof ./prime gmon.out -b

为了减少prime()中的测试次数,我们这次只考虑对n测试不超过n的可能的整数因子:

#include <stdio.h>
#include <math.h>

int root(int n)
{
    return ((int)sqrt((float)n));
}

int prime(int n)
{
    int bound = root(n);
    for(int i = 2; i <= bound; ++i) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

再次编译测试:

$ gcc -Wall -lm --std=c99 -pg -o prime prime.c

接下来的改进包括:对2、3、5的特殊校验,把能被这些数整除的输入归入合数(这里要注意的是2、3、5本身是素数,因此如果输入等于这些数要返回true);其次是只考虑奇数作为可能的因子。

int prime(int n)
{
    if(n % 2 == 0) return (n == 2);
    if(n % 3 == 0) return (n == 3);
    if(n % 5 == 0) return (n == 5);

    int bound = root(n);
    for(int i = 7; i <= bound; i += 2) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

分享

0