随笔 - 62  文章 - 96  trackbacks - 0
<2007年3月>
25262728123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

  • 积分 - 207212
  • 排名 - 104

最新评论

阅读排行榜

评论排行榜

昨天在PKU上做了一题2187,限时3s。
算法主要耗时在多次求不同整数的平方。
当用pow函数求时,超时;
而直接乘才232ms。
相差也太大了吧。
于是就写了一段代码来测试pow的性能
首先产生10000个随机整数,然后重复1000次求整数的平方

#include <iostream>
#include 
<cmath>
#include 
<ctime>
using 
namespace std;
const int MAX = 10000;
int a[MAX];
int main()
{
    
int i, j, n = MAX;
    
int rep = 1000//重复次数
    clock_t beg, 
end;
    
for(i = 0; i < n; i++)
        a[i] 
= rand() % 20000 - 10000//-10000 <= a[i]< 10000

    cout
<<"test a[i]*a[i]"<<endl;
    beg 
= clock();
    
for(j = 0; j < rep; j++)
        
for(i = 0; i < n; i++)
            a[i] 
* a[i];
    
end = clock();
    cout
<<"time: "<<end - beg<<"ms"<<endl;
    
    cout
<<"test pow(a[i], 2.0)"<<endl;
    beg 
= clock();
    
for(j = 0; j < rep; j++)
        
for(i = 0; i < n; i++)
            pow(a[i], 
2.0);
    
end = clock();
    cout
<<"time: "<<end - beg<<"ms"<<endl;

    
return 0;
}

下面是测试结果:

test a[i]*a[i]
time: 31ms
test pow(a[i], 2.0)
time: 2828ms

所以下次遇到类似情况不再用pow函数了……
posted on 2007-08-25 20:16 beyonlin 阅读(4358) 评论(6)  编辑 收藏 引用 所属分类: acm之路

FeedBack:
# re: pow函数的性能测试 2007-09-01 20:06 Roland Lee
pow是函数,传递参数,调用函数的代价远大于直接相乘。
并且,调用函数破坏了cpu的分支预测和缓存优化。  回复  更多评论
  
# re: pow函数的性能测试[未登录] 2007-12-14 13:51 will
第一个循环只不过是两个 int型相乘而已。

那个pow()第一个参数没有int,而第二个参数你指定2.0 默认为double, 所以至少是两个 double相乘,这已经慢很多了。  回复  更多评论
  
# re: pow函数的性能测试 2008-05-25 01:28 正在开发符点运算库
double类型在内存的存储是64位,并且相当科学计数法方式存储。最高一位是位,得到示正负,接下来的11表示指数,指数的最高位表示指数的正负。再下的的52位表示小数。在double计算中,首先要判断指数是否有意义,因为并不是每一个指数都有意义。有的指数表示无穷大,有的指数表示无穷小。

在pow(X,Y)计算中,X,Y作为double类型计算,算法就复杂多了,这不能像整那样循环或迭代来计算,因为指数有可能是小数。在运算中要调用符点运算的乘法,除法,log.  回复  更多评论
  
# re: pow函数的性能测试 2012-03-13 21:51 L_Squirrel.
既然这样..
那什么时候能用到pow?
是不是就不用再用pow?  回复  更多评论
  
# re: pow函数的性能测试 2012-03-19 15:34 beyonlin
求x的非整数次幂时会用到,比如求x的2.5次幂@L_Squirrel.@L_Squirrel.  回复  更多评论
  
# re: pow函数的性能测试 2014-02-22 22:02 YYX
Pow 函数要处理各种非整数次幂情况,比如0.5就等于开根号了,0.2就等于开5次方了。当然比直接乘慢的多。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理