昨天在PKU上做了一題2187，限時3s。
算法主要耗時在多次求不同整數的平方。
當用pow函數求時，超時；
而直接乘才232ms。
相差也太大了吧。
于是就寫了一段代碼來測試pow的性能
首先產生10000個隨機整數，然后重復1000次求整數的平方
#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; //重復次數
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 閱讀(5759) |
評論 (6) |
編輯 收藏在做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 閱讀(1548) |
評論 (0) |
編輯 收藏
發現用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個元素有2^n個子集，
i從0到2^n - 1,
把它換算成二進制就分別對應一個子集。
posted @
2007-07-23 15:56 beyonlin 閱讀(1078) |
評論 (0) |
編輯 收藏
以前求子集樹都是用回溯法，
今天在topcoder做SRM時學到一種求子集樹的新方法：位運算。
第一重循環是枚舉所有子集，共2^n個，即1 << n個
第二重循環求集合所有j個元素的值，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);
}
}
}
//位運算
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 閱讀(1758) |
評論 (0) |
編輯 收藏#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 閱讀(2658) |
評論 (2) |
編輯 收藏