昨天在PKU上做了一題2187，限時(shí)3s。
算法主要耗時(shí)在多次求不同整數(shù)的平方。
當(dāng)用pow函數(shù)求時(shí)，超時(shí)；
而直接乘才232ms。
相差也太大了吧。
于是就寫了一段代碼來測(cè)試pow的性能
首先產(chǎn)生10000個(gè)隨機(jī)整數(shù)，然后重復(fù)1000次求整數(shù)的平方
#include <iostream>
#include <cmath>
#include <ctime>
using Namespace stdnamespace 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
所以下次遇到類似情況不再用pow函數(shù)了……
posted @
2007-08-25 20:16 beyonlin 閱讀(5829) |
評(píng)論 (6) |
編輯 收藏在做PKU2762時(shí)，需要建鄰接表。
于是按部就班寫了下面一個(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
無論是時(shí)間還是空間都相差很大。
于是就考慮怎么優(yōu)化自己的程序。
第一個(gè)問題：規(guī)模只有1000，為什么會(huì)用那么多內(nèi)存呢？
仔細(xì)一想數(shù)據(jù)是多case的，每次插入新節(jié)點(diǎn)時(shí)都要?jiǎng)討B(tài)創(chuàng)建一個(gè)節(jié)點(diǎn)。
一來動(dòng)態(tài)創(chuàng)建耗時(shí)間，二來每個(gè)case結(jié)束的鄰接表中的節(jié)點(diǎn)沒有釋放，故耗費(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 閱讀(1578) |
評(píng)論 (0) |
編輯 收藏
發(fā)現(xiàn)用stl中的bitset求子集樹只要短短的幾行代碼
#include<iostream>
#include<bitset>
using Namespace stdnamespace 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 閱讀(1101) |
評(píng)論 (0) |
編輯 收藏
以前求子集樹都是用回溯法，
今天在topcoder做SRM時(shí)學(xué)到一種求子集樹的新方法：位運(yùn)算。
第一重循環(huán)是枚舉所有子集，共2^n個(gè)，即1 << n個(gè)
第二重循環(huán)求集合所有j個(gè)元素的值，0或1。
求一下1 & (1 << j)的值就可以知道它的原理。
#include<iostream>
using Namespace stdnamespace 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 閱讀(1780) |
評(píng)論 (0) |
編輯 收藏#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開始
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 閱讀(2698) |
評(píng)論 (2) |
編輯 收藏