Posted on 2009-01-23 00:08
dennis 閱讀(617)
評論(3) 編輯 收藏
這幾天沒事做的時候都會上projecteuler.net上面去做題，其中14題是這樣的：
he following iterative sequence is defined for the set of positive integers:
n 
n/2 (n is even)
n 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
It can be seen that this sequence (starting at 13 and finishing at
1) contains 10 terms. Although it has not been proved yet (Collatz
Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
題目并不難理解，這個據說是著名的角谷猜想，現在要找到100萬以下的數字中展開這個鏈最長的數字是多少。如果我一開始就直接按照題意來解答，這個題目花不了幾分鐘，直接暴力法。然而我卻想的太多了，我猜想在計算這個鏈條長度的過程中會不會有很多數字會重復計算，如果加上緩存以前計算的結果是否能節約比較多的時間？那么第一次解答如下：
#include<iostream>
#include<map>
#include<windows.h>
using namespace std;
unsigned long produce_term(unsigned long n)
{
if(n&1)
return 3*n+1;
else
return n>>1;
}
int main()
{
map<unsigned long,int> counters;
int max_i=0;
int max_count=0;
DWORD tick1,tickPassed;
tick1 = GetTickCount();
for(int i=1;i<1000000;i++)
{
int sum=2;
unsigned long term=i;
while((term=produce_term(term))!=1)
{
if(counters[term]){
sum+=counters[term];
break;
}else
sum+=1;
}
if(sum>max_count)
{
max_i=i;
max_count=sum;
counters[i]=sum;
}
}
tickPassed = GetTickCount()-tick1;
cout<<tickPassed<<endl;
cout<<max_i<<endl<<max_count<<endl;
return 0;
}
遺憾的是，這個版本跑了快13分鐘，太讓人難以接受了。那么是否能優化下？怎么優化？我的機器是雙核的，跑這個單進程單線程的程序只利用了一半的CPU，那么能不能搞成
兩個線程來計算？緩存需要在兩個線程之間做同步，顯然讀的多，寫的少，應該采用
讀寫鎖。OK，第二個版本利用ACE的線程封裝實現如下：
#include<iostream>
#include<map>
#include "ace/Thread_mutex.h"
#include "ace/Synch.h"
#include "ace/Thread_Manager.h"
using namespace std;
class ThreadSafeMap
{
public:
ThreadSafeMap()
{
}
int get(unsigned long n)
{
ACE_READ_GUARD_RETURN(ACE_RW_Thread_Mutex,guard,mutex_,0);
return counters_[n];
}
int put(unsigned long key,int value)
{
ACE_WRITE_GUARD_RETURN(ACE_RW_Thread_Mutex,guard,mutex_,-1);
counters_[key]=value;
return 0;
}
private:
map<unsigned long,int> counters_;
ACE_RW_Thread_Mutex mutex_;
};
unsigned long produce_term(unsigned long n)
{
if(n&1)
return 3*n+1;
else
return n>>1;
}
static ThreadSafeMap counters;
ACE_THR_FUNC_RETURN run_svc (void *arg)
{
int max_i=0;
int max_count=0;
for(int i=500001;i<1000000;i++)
{
int sum=2;
unsigned long term=i;
while((term=produce_term(term))!=1)
{
if(counters.get(term)){
sum+=counters.get(term);
break;
}else
sum+=1;
}
if(sum>max_count)
{
max_i=i;
max_count=sum;
counters.put(i,sum);
}
}
cout<<max_i<<endl<<max_count<<endl;
return 0;
}
int main(int ac,char* argv[])
{
if (ACE_Thread_Manager::instance ()->spawn (
// Pointer to function entry point.
run_svc,
// <run_svc> parameter.
NULL,
THR_DETACHED | THR_SCOPE_SYSTEM) == -1)
return -1;
int max_i=0;
int max_count=0;
for(int i=1;i<500000;i++)
{
int sum=2;
unsigned long term=i;
while((term=produce_term(term))!=1)
{
if(counters.get(term)){
sum+=counters.get(term);
break;
}else
sum+=1;
}
if(sum>max_count)
{
max_i=i;
max_count=sum;
counters.put(i,sum);
}
}
cout<<max_i<<endl<<max_count<<endl;
return ACE_Thread_Manager::instance ()->wait ();
}
將數據分成了兩半，利用兩個線程來計算，果然快了一點，快了多少呢？從13分鐘減少到9分鐘，CPU利用率也到了100%，內存占用也降低了一半，似乎成績不錯呀。正在沾沾自喜之際，突然想起，能不能簡單地暴力破解，咱不搞緩存，不搞多線程，看看效果怎么樣。那么第三個版本簡單實現如下：
#include<iostream>
using namespace std;
unsigned long produce_term(unsigned long n)
{
if(n&1)
return 3*n+1;
else
return n>>1;
}
int main()
{
int max_i;
int max_count=0;
for(int i=1;i<1000000;i++)
{
int count=2;
unsigned long term=i;
while((term=produce_term(term))>1)
count+=1;
if(count>max_count){
max_i=i;
max_count=count;
}
}
cout<<max_i<<endl<<max_count<<endl;
system("pause");
return 0;
}
程序執行的結果讓我驚掉了下巴，竟然只執行了1秒多，換成java也是一樣。什么緩存、多線程，全拋到了九霄云外。
總結教訓，
想當然的性能估計是愚不可及的，想當然的優化是愚不可及的，簡單直接才是美！