无码人妻精品一区二区三区久久久,久久99精品国产麻豆宅宅,久久精品视频网

2007年8月25日

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

2007年8月13日

一道算法題引發(fā)的動(dòng)態(tài)內(nèi)存管理的思考

在做PKU2762時(shí)，需要建鄰接表。
于是按部就班寫(xiě)了下面一個(gè)插入邊到鄰接表中的函數(shù)：

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;

}

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

再對(duì)比別人的程序
Memory:296K Time:109MS

無(wú)論是時(shí)間還是空間都相差很大。
于是就考慮怎么優(yōu)化自己的程序。
第一個(gè)問(wèn)題：規(guī)模只有1000，為什么會(huì)用那么多內(nèi)存呢？
仔細(xì)一想數(shù)據(jù)是多case的，每次插入新節(jié)點(diǎn)時(shí)都要?jiǎng)討B(tài)創(chuàng)建一個(gè)節(jié)點(diǎn)。
一來(lái)動(dòng)態(tài)創(chuàng)建耗時(shí)間，二來(lái)每個(gè)case結(jié)束的鄰接表中的節(jié)點(diǎn)沒(méi)有釋放，故耗費(fèi)大量?jī)?nèi)存。
然后就想到了下面的算法，首先初始化一塊內(nèi)存Graph use[100*VMAX];這樣每次需要新節(jié)點(diǎn)時(shí)，
就從use中獲取。如果use使用完畢就再動(dòng)態(tài)創(chuàng)建。

依此算法優(yōu)化后，得到的結(jié)果比較滿意
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 閱讀(1544) | 評(píng)論 (0) | 編輯收藏

2007年7月23日

再談子集樹(shù)

發(fā)現(xiàn)用stl中的bitset求子集樹(shù)只要短短的幾行代碼

#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個(gè)元素有2^n個(gè)子集，
i從0到2^n - 1,
把它換算成二進(jìn)制就分別對(duì)應(yīng)一個(gè)子集。

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

2007年7月22日

位運(yùn)算求子集樹(shù)

以前求子集樹(shù)都是用回溯法，
今天在topcoder做SRM時(shí)學(xué)到一種求子集樹(shù)的新方法：位運(yùn)算。
第一重循環(huán)是枚舉所有子集，共2^n個(gè)，即1 << n個(gè)
第二重循環(huán)求集合所有j個(gè)元素的值，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);

}

//位運(yùn)算

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 閱讀(1756) | 評(píng)論 (0) | 編輯收藏

2007年5月18日

篩法求素?cái)?shù)

#include<iostream>

using namespace std;

const int MAXV = 10000; //素?cái)?shù)表范圍

bool flag[MAXV+1]; //標(biāo)志一個(gè)數(shù)是否為素?cái)?shù)

int prime[MAXV+1]; //素?cái)?shù)表,下標(biāo)從0開(kāi)始

int size; //素?cái)?shù)個(gè)數(shù)

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 閱讀(2656) | 評(píng)論 (2) | 編輯收藏

常用鏈接

留言簿(7)

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

隨筆檔案(62)

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

文章檔案(32)

友情鏈接

最新隨筆

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜