skyli
C++之夢

隨筆 - 62 文章 - 96 trackbacks - 0

2006年6月

>

日

一

二

三

四

五

六

28

29

30

31

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

1

2

3

4

5

6

7

8

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

校內網

積分與排名

積分 - 237777
排名 - 108

閱讀排行榜

評論排行榜

2007年8月25日

pow函數的性能測試

昨天在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 @ 2007-08-25 20:16 beyonlin 閱讀(5832) | 評論 (6) | 編輯收藏

2007年8月13日

一道算法題引發的動態內存管理的思考

在做PKU2762時，需要建鄰接表。
于是按部就班寫了下面一個插入邊到鄰接表中的函數：

const int VMAX = 1010;

typedef struct Graph

{

int vex;

Graph* next;

}Graph;

Graph ArcGraph[VMAX];

void insert(int u, int v)

{

Graph* t = new Graph;

Graph* p = ArcGraph[u].next;

t->vex = v;

t->next = p;

ArcGraph[u].next = t;

}

完成完整的程序提交上去，得到結果
Memory:25796K Time:375MS
Language:C++ Result:Accepted

再對比別人的程序
Memory:296K Time:109MS

無論是時間還是空間都相差很大。
于是就考慮怎么優化自己的程序。
第一個問題：規模只有1000，為什么會用那么多內存呢？
仔細一想數據是多case的，每次插入新節點時都要動態創建一個節點。
一來動態創建耗時間，二來每個case結束的鄰接表中的節點沒有釋放，故耗費大量內存。
然后就想到了下面的算法，首先初始化一塊內存Graph use[100*VMAX];這樣每次需要新節點時，
就從use中獲取。如果use使用完畢就再動態創建。

依此算法優化后，得到的結果比較滿意
Memory:1000K Time:218MS
Language:C++ Result:Accepted

const int VMAX = 1010;

typedef struct Graph

{

int vex;

Graph* next;

}Graph;

Graph ArcGraph[VMAX];

Graph use[100*VMAX];

int size = 0;

void insert(int u, int v)

{

Graph* t;

if(size < 100*VMAX)

{

t = &use[size];

size++;

}

else t = new Graph;

Graph* p = ArcGraph[u].next;

t->vex = v;

t->next = p;

ArcGraph[u].next = t;

}

posted @ 2007-08-13 00:29 beyonlin 閱讀(1580) | 評論 (0) | 編輯收藏

2007年7月23日

再談子集樹

發現用stl中的bitset求子集樹只要短短的幾行代碼

#include<iostream>

#include<bitset>

using namespace std;

const int n = 4;

int main()

{

for(int i = 0; i < (1 << n); i++)

{

bitset<n> bit(i);

for(int j = bit.size() - 1; j >= 0; j--)

cout<<bit[j];

cout<<endl;

}

return 0;

}

n個元素有2^n個子集，
i從0到2^n - 1,
把它換算成二進制就分別對應一個子集。

posted @ 2007-07-23 15:56 beyonlin 閱讀(1101) | 評論 (0) | 編輯收藏

2007年7月22日

位運算求子集樹

以前求子集樹都是用回溯法，
今天在topcoder做SRM時學到一種求子集樹的新方法：位運算。
第一重循環是枚舉所有子集，共2^n個，即1 << n個
第二重循環求集合所有j個元素的值，0或1。
求一下1 & (1 << j)的值就可以知道它的原理。

#include<iostream>

using namespace std;

const int n = 4;

int x[n];

//回溯法

void backtrack(int t)

{

if(t >= n)

{

for(int i = 0; i < n; i++)

cout<<x[i];

cout<<endl;

}

else

{

for(int i = 0; i <= 1; i++)

{

x[t] = i;

backtrack(t + 1);

}

//位運算

void bitOperate()

{

for(int i = 0; i < (1 << n); i++)

{

for(int j = 0; j < n; j++)

{

if( (i & (1 << j) ) == 0)

x[j] = 0;

else

x[j] = 1;

}

for(int j = 0; j < n; j++)

cout<<x[j];

cout<<endl;

}

int main()

{

backtrack(0);

cout<<endl;

bitOperate();

return 0;

}

posted @ 2007-07-22 02:59 beyonlin 閱讀(1780) | 評論 (0) | 編輯收藏

2007年5月18日

篩法求素數

#include<iostream>

using namespace std;

const int MAXV = 10000; //素數表范圍

bool flag[MAXV+1]; //標志一個數是否為素數

int prime[MAXV+1]; //素數表,下標從0開始

int size; //素數個數

void genPrime(int max)

{

memset(flag, true, sizeof(flag));

for(int i = 2; i <= max / 2; i++)

{

if(flag[i])

{

for(int j = i << 1 ; j <= max; j += i)

{

flag[j] = false;

}

for(int i = 2 ; i <= max; i++)

{

if(flag[i])

{

prime[size++] = i;

}

int main()

{

genPrime(MAXV);

return 0;

}

posted @ 2007-05-18 16:13 beyonlin 閱讀(2700) | 評論 (2) | 編輯收藏

僅列出標題下一頁

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

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

最新隨筆

積分與排名

最新評論

閱讀排行榜

評論排行榜