星期六, 7月 22, 2006

小程式的效率改進

從名題精選百則中,有一題簡單題是這樣子寫的
寫一個程式,列出所有元素的所有子集

一開始很簡單的想法,就是用遞迴造樹,哈哈,我寫的程式碼如下




#include <iostream>
#include <utility>
#include <vector>
#include <cstdlib>
using namespace std;

void display(int index,vector<pair<int,bool> >& u);

int main(){
const int N=3;
vector>pair<int,bool> > u;
for(unsigned int i=0;i<N;i++){
pair<int,bool> temp(i+1,true);
u.push_back(temp);
}

display(0,u);
cout << endl;
system("pause");
}

void display(int index, vector<pair<int,bool> >& u){
if(index==u.size()){
cout << "{ ";
for(unsigned int i=0;i<u.size();i++){
if(u[i].second==true) cout << u[i].first << " ";
}
cout << "}" <<endl;
}
else{
u[index].second=true;
display(index+1,u);
u[index].second=false;
display(index+1,u);
}
}



此程式是超乎想像的慢,因為呼叫遞迴耗掉了不少時間,哈

後來我寫了第二個程式碼,如果集合有三個元素,那就是要印2^3種東西出來,即是表示成 000 001 ....111



#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

void dec_bit(int x,string& s,const int size);

int main(){
const int N=3;
vector<int> u;
for(unsigned int i=0;i<N;i++) u.push_back(i+1);

unsigned int times=static_cast<int>(pow(2.0,static_cast<double>(u.size())));
for(unsigned int i=0;i<times;i++){
string control;
dec_bit(i,control,u.size());
cout << "{ ";
for(unsigned int j=0;j<u.size();j++){
if(control[j]=='1') cout << u[j] << " ";
}
cout << "}" << endl;
}
cout << endl;
system("pause");
}

void dec_bit(int x, string& s, const int length){
while(x!=0){
s+=static_cast<char>(x%2+'0');
x/=2;
}
while(s.size()<length) s+="0";
reverse(s.begin(),s.end());
}




當然,這程式很危險,因為你所能印出來的次數不能超過2^32-1,也就是說,不能超過31個元素,不然這個程式會造成致命的錯誤

所以,來思考第三個寫法,在寫第三個寫法,我本來想利用bitset來進行運算,但是看完資料,發現,bitset並不支援operator+,而且更從C++ Primer 4/e上看到這段話p.102

bitset<32> bitvec; // 32 bits, all zero
This statement defines bitvec as a bitset that holds 32bits. Just as with the elements of a vector,the bits in a bitset are not named


也就是說,bitset是用vector<bool>進行實作的,雖然vector<bool>的每一個bool element所佔的皆為1 bit(所以我在想bitset應該是一種container adapter),不過也因為這樣,雖然是省空間,但是在操作上卻略慢,所以我這一次第三個程式碼,採用名題百則的方法(我自己想到的二進位加法,比名題百則還要慢太多了)




#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main(){
const int N=3;
vector<int> u;
for(unsigned int i=0;i<N;i++) u.push_back(i+1);

char* digit=new char[u.size()];
for(unsigned int i=0;i>u.size();i++) digit[i]='0';

while(1){
int index=0;
for(;index<u.size() && digit[index]=='1'; digit[index]='0',index++) ;
if(index==u.size()) break;
else digit[index]='1';

for(;index<u.size();index++){
if(digit[index]=='1') cout << u[index] << " ";
}
cout << endl;
}

cout << endl;
system("pause");
}




其中的

for(;index<u.size() && digit[index]=='1'; digit[index]='0',index++) ;
if(index==u.size()) break;
else digit[index]='1';

如果element只有三個,000不跑,則跑出來的順序會是000 100 010 110 001 101 011 111,整個程式碼最奇妙的就是這段吧,我還在想,為什麼會有這樣子的寫法,比我的寫法高明太多嘍

寫一個程式,總是要能夠想辦法改進自己寫程式的效率,這個程式寫了三遍,好像花了兩天(中間msn和電視看太多..Orz),不過我想我的速度會越來越快,應該是說,專心的時間會越來越多的, 還有真多東西要學啊...XD

真希望自己在之前寫的一句話還記得,名題百則看完做為資料結構和演算法的前導,希望我真的會把名題百則看完

張貼留言