skyli
C++之夢(mèng)

隨筆 - 62 文章 - 96 trackbacks - 0

2007年12月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

常用鏈接

留言簿(7)

隨筆分類(lèi)(66)

隨筆檔案(62)

文章分類(lèi)(31)

文章檔案(32)

友情鏈接

校內(nèi)網(wǎng)

積分與排名

積分 - 237698
排名 - 108

閱讀排行榜

評(píng)論排行榜

pow函數(shù)的性能測(cè)試

昨天在PKU上做了一題2187，限時(shí)3s。
算法主要耗時(shí)在多次求不同整數(shù)的平方。
當(dāng)用pow函數(shù)求時(shí)，超時(shí)；
而直接乘才232ms。
相差也太大了吧。
于是就寫(xiě)了一段代碼來(lái)測(cè)試pow的性能
首先產(chǎn)生10000個(gè)隨機(jī)整數(shù)，然后重復(fù)1000次求整數(shù)的平方

#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; //重復(fù)次數(shù)

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;

}

下面是測(cè)試結(jié)果：

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

所以下次遇到類(lèi)似情況不再用pow函數(shù)了……

posted on 2007-08-25 20:16 beyonlin 閱讀(5831) 評(píng)論(6) 編輯收藏引用所屬分類(lèi): acm之路

FeedBack:

# re: pow函數(shù)的性能測(cè)試 2007-09-01 20:06 Roland Lee

pow是函數(shù)，傳遞參數(shù)，調(diào)用函數(shù)的代價(jià)遠(yuǎn)大于直接相乘。
并且，調(diào)用函數(shù)破壞了cpu的分支預(yù)測(cè)和緩存優(yōu)化。回復(fù) 更多評(píng)論

# re: pow函數(shù)的性能測(cè)試[未登錄](méi) 2007-12-14 13:51 will

第一個(gè)循環(huán)只不過(guò)是兩個(gè) int型相乘而已。

那個(gè)pow()第一個(gè)參數(shù)沒(méi)有int，而第二個(gè)參數(shù)你指定2.0 默認(rèn)為double, 所以至少是兩個(gè) double相乘，這已經(jīng)慢很多了。回復(fù) 更多評(píng)論

# re: pow函數(shù)的性能測(cè)試 2008-05-25 01:28 正在開(kāi)發(fā)符點(diǎn)運(yùn)算庫(kù)

double類(lèi)型在內(nèi)存的存儲(chǔ)是64位，并且相當(dāng)科學(xué)計(jì)數(shù)法方式存儲(chǔ)。最高一位是位，得到示正負(fù)，接下來(lái)的11表示指數(shù)，指數(shù)的最高位表示指數(shù)的正負(fù)。再下的的52位表示小數(shù)。在double計(jì)算中，首先要判斷指數(shù)是否有意義，因?yàn)椴⒉皇敲恳粋€(gè)指數(shù)都有意義。有的指數(shù)表示無(wú)窮大，有的指數(shù)表示無(wú)窮小。

在pow（X,Y)計(jì)算中，X,Y作為double類(lèi)型計(jì)算，算法就復(fù)雜多了，這不能像整那樣循環(huán)或迭代來(lái)計(jì)算，因?yàn)橹笖?shù)有可能是小數(shù)。在運(yùn)算中要調(diào)用符點(diǎn)運(yùn)算的乘法，除法，log. 回復(fù) 更多評(píng)論

# re: pow函數(shù)的性能測(cè)試 2012-03-13 21:51 L_Squirrel.

既然這樣..
那什么時(shí)候能用到pow？
是不是就不用再用pow？回復(fù) 更多評(píng)論

# re: pow函數(shù)的性能測(cè)試 2012-03-19 15:34 beyonlin

求x的非整數(shù)次冪時(shí)會(huì)用到，比如求x的2.5次冪@L_Squirrel.@L_Squirrel. 回復(fù) 更多評(píng)論

# re: pow函數(shù)的性能測(cè)試 2014-02-22 22:02 YYX

Pow 函數(shù)要處理各種非整數(shù)次冪情況，比如0.5就等于開(kāi)根號(hào)了，0.2就等于開(kāi)5次方了。當(dāng)然比直接乘慢的多。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


相關(guān)文章: pow函數(shù)的性能測(cè)試一道算法題引發(fā)的動(dòng)態(tài)內(nèi)存管理的思考篩法求素?cái)?shù) 字符串hash函數(shù) 插入排序泛型算法最大匹配匈牙利算法最小生成樹(shù)Prim算法 itoa函數(shù) 歸并排序求逆序數(shù) 單源最短路徑Dijkstra算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(7)

隨筆分類(lèi)(66)

隨筆檔案(62)

文章分類(lèi)(31)

文章檔案(32)

友情鏈接

最新隨筆

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜