可笑的優化

    這幾天沒事做的時候都會上projecteuler.net上面去做題，其中14題是這樣的：

he following iterative sequence is defined for the set of positive integers:

n

n/2 (n is even)

3n + 1 (n is odd)

using the rule above and starting with 13, we generate the following sequence:

13

40

20

10

5

16

8

4

2

1

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 "ace/thread_mutex.h"

#include "ace/synch.h"

#include "ace/thread_manager.h"

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_;

};

static threadsafemap counters;

ace_thr_func_return run_svc (void *arg)

    for(int i=500001;i<1000000;i++)

            if(counters.get(term)){

                sum+=counters.get(term);

            counters.put(i,sum);

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;

    for(int i=1;i<500000;i++)

    return ace_thread_manager::instance ()->wait ();

    将資料分成了兩半，利用兩個線程來計算，果然快了一點，快了多少呢？從13分鐘減少到9分鐘，cpu使用率也到了100%，記憶體占用也降低了一半，似乎成績不錯呀。正在沾沾自喜之際，突然想起，能不能簡單地暴力破解，咱不搞緩存，不搞多線程，看看效果怎麼樣。那麼第三個版本簡單實作如下：

  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也是一樣。什麼緩存、多線程，全抛到了九霄雲外。

     總結教訓，想當然的性能估計是愚不可及的，想當然的優化是愚不可及的，簡單直接才是美！

文章轉自莊周夢蝶  ，原文釋出時間 2009-01-23 <b></b>