一,计算素数
第一个程序:如果整数n,从2开始到n-1都不能整除则为素数。注意,n=2时一定是素数的判断
第二个程序:只需要从2到sqrt(n)不能整除就可以
第三个程序:通过对被2、3和5整除的特殊检验,避免了近3/4的开方运算。语句计数表明,被2整除的性质大约把一半的输入归入合数,被3整除把剩余输入的1/3归入合数,被5整除再把剩下的这些数的1/5归入合数。其次,只考虑奇数作为可能的因子,在剩余的数中避免了大约一半的整除检验。它比程序P3大约快两倍,但是也比P3的错误更多。
以上程序,没有将素数:2,3,5检查出来
改进后程序如下:
第四个程序:将费时的开方运算替换为 乘法,将第三个程序稍加调整
关键代码:
二,性能检测工具
在linux系统下:
find . -name "*.c" |xargs wc -l
time — 执行命令并计时
time find . -name "*.c" |xargs wc -l // 统计执行命令时间
real 0m33.748s
user 0m0.772s
sys 0m1.044s
1)实际时间(real time): 从command命令行开始执行到运行终止的消逝时间;
2)用户CPU时间(user CPU time): 命令执行完成花费的用户CPU时间,即命令在用户态中执行时间总和;
3)系统CPU时间(system CPU time): 命令执行完成花费的系统CPU时间,即命令在核心态中执行时间总和。
其中,用户CPU时间和系统CPU时间之和为CPU时间,即命令占用CPU执行的时间总和。实际时间要大于CPU时间,因为Linux是多任务操作系统,往往在执行一条命令时,系统还要处理其它任务。
另一个需要注意的问题是即使每次执行相同命令,但所花费的时间也是不一样,其花费时间是与系统运行相关的。
代码的性能检测,统计每个函数调用次数。额可以检测哪个函数占用大量CPU时间,从而有效更改程序。
三,习题
2)实现简单的埃氏筛法(Sieve
of Eratosthenes)来计算所有小于n的素数。这个程序的主要数据结构是一个n比特的数组,初始值都为真。每发现一个素数时,数组中所有这个素数的倍数就设置为假。下一个素数就是数组中下一个为真的比特。
答案:下面的C程序实现了埃氏筛法来计算所有小于n的素数。其基本数据结构是n比特数组x,初始值全部为1。每发现一个素数,数组中所有它的倍数都设为0。下一个素数就是数组中的下一个取值为1的比特位。性能监视表明小于100000的素数有9592个,算法进行了大概2.57N次赋值。一般地,算法进行NloglogN次赋值;算法分析中涉及到答案1.1中的素数密度和调和数。下面是加上性能监视后的代码:
3) 一个简单的用于语句计数的性能监视工具每执行一个语句就增加一次计数。满足于更少的计数器可以同时减少监视程序的内存需求和运行时间。例如,可以给程序流图中的每个基本块关联一个计数器。也可以利用"基尔霍夫第一定律"进一步减少计数器的数量:如果你有一个if-then-else语句的计数器以及一个then分支语句的计数器,那么就不需要else分支语句的计数器了。
分享到:
相关推荐
编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充
《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...
编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本
编程珠玑 续,描述一些编程技巧,需要的可以下载看看。
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
编程珠玑+续
编程珠玑续(美)本特利(jb51.net).PDF。 编程技术,算法原理,代码修炼
本资源只是“编程珠玑之第二章questionC: 求变位词问题”的简单的测试数据。
Jon Bentley编著的《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容...
《编程珠玑(续)》,本书是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
编程珠玑编程珠玑
编程珠玑·续.pdf 带目录书签 高清版
编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式
a sister book of programming pearls ,and also a good book
[编程珠玑·续].(美)本特利.扫描版.PDF
编程珠玑(第二版)答案