奇技淫巧C++之懶惰計算

2019-11-17 05:28:35

字體：大中小

來源：轉載

供稿：網友

　　考慮這樣一個表達式語句：

String result = str_you + “said: ” + str_he + “ said: @#$% ” + str_i + “said: over!”;
　　對于這樣一個語句，程序如何求值呢？假設str_you是一個典型std::string類型，這個語句需要做5 次Operator+運算，多個string臨時對象,還極有可能的，多次的內存分配操作。

　　假如你的team leader對你說了類似話，兄弟，他是對你的代碼性能不滿呢。當然，聰明如你，一定會在上司找到你之前就發現了這里是個性能瓶頸，并且告訴他你正著手解決它呢。

　　辦法是多種多樣的，最正確的辦法當然首先是看看設計上是否存在缺陷，并且可以修復以改善性能問題。假設，任何部分都很正確（我知道這不可能，一定有被你稱為菜鳥的同事干了蠢事，不是嗎？），責任只好落到你的肩上。打算怎么辦？

　　我不知道你會怎么做，也許你會換一個更快的string,或者簡單調整一下語句:

string result;
result.reserve(1000);
result += str_you; result += “said: ”;
result += str_he; result += “ said: @#$% ”;
result += str_i; result += “said: over!”;
　　假如只有一兩個性能熱點，我打賭，我會這樣先嘗試一下。我認為這是一個很好的開始，我們已經熟悉到導致瓶頸的原因并且試圖消除它。你也可以這么做。寫這篇文章，當然意味著還有別的方法，而且和懶惰計算有關。因為我們不能修改basic_string::的operator+,因此，先把表達式變形:

Acce() + str_you + “said: ” + str_he + “ said: @#$% ” + str_i + “said: over!”;

　　因為operator+從左向右結合，可以采用我們加速過的運算過程。先看最簡單的情況,和string相加。

template<typename Left, typename Right>
strUCt Accelerate{
　operator string () const;
　Left& left;
　Right& right;
};

template<typename Left, typename Right>
inline Accelerate< Accelerate< Left >, Right>

operator+(Accelerate< Left >& lsh, const Right& rsh)
{
　return Accelerate< Accelerate< Left >, Right>(lsh, rsh);
}
　　顯然，Accelerate是輕量級的，現在考慮怎么實現operator string () const呢？我的計劃是，首先計算出字符串的總長度，然后開一個足夠大的空間來復制字符串，避免反復分配內存:

operator string () const{
　string str;
　str.reserve(length(left) + length(right));
　append(str, left);
　append(str, right);
　return str;
};
　　第一步，看看怎么實現length:

struct Empty{};
template<typename T>

inline size_t length(const T& t){
　return t.size();
}

template<typename Left, typename Right>

inline size_t length(const Accelerate<Left, Right>& t){
　return length(t.left) + length(t.right);
}

template<>

inline size_t length(const Accelerate<Empty, Empty>& t){
　return 0;
}
　　第二步，看看怎么實現append:

Template<typename Left, typename Right>
inline append(string& str, const Accelerate& t ){
　append(str, t.left);
　append(str,t.right);
}

Template< >

inline append(string&, const Accelerate<Empty, Empty>& ){}

inline append(string& str, const string& rsh){
　copy(rsh.begin(), rsh.end(), back_inserter(str));
}
　　現在，我們整個計算的框架算是完成了，不過可真夠復雜的。注重觀察，實際上，Accelerate利用多重繼續，把表達式轉換成一個二叉樹，葉結點就是實際的字符串。對于Acce有如下定義:

typedef Accelerate<Empty, Empty> Acce;

　　上面的過程針對string,實際上可以推廣到其他的字符串形式，我們只需要重載特定的函數：length,append:

size_t length(const char* str)
{
　return strlen(str);
}

Template<int SIZE>

size_t length(const char[SIZE] str)
{
　return SIZE – 1; //注重，形如length(”text”)這樣的代碼，重載決議將使用這個重載版本。
}
　　至于append,也是類似的手法：

inline void append(string& str, const char* src){
　while(*src != ‘/0’) str.push_back(*src++);
}
　　性能分析：

string str;
str.reserve(length(left) + length(right));
　　這里，采用str是沒有必要的，在性能要害的場合，這里完全可以用內存塊取代，可以改善性能。另外,length的計算，對于string和char [SIZE]這兩種形式，都是常數時間，后一種更是可以在編譯期優化掉，無需計算。但是，對于char*這種形勢，strlen導致一次線性掃描。在 append的過程中，再一次線性掃描同一個數據來源，這是可以繼續優化的地方。但是在這里繼續剖析的話，就弱化了我們懶惰計算的主旨了。在這里，只是展示懶惰計算的威力。實際上，懶惰計算在ORM環境下也是經常用到的，當然也包括數據庫操作，和從文件加載對象這樣的操作。為了獲得某個數據，必須進行事先的若干處理才能獲得，假設事先處理的相對成本比較高，那么就可以考慮懶惰計算，在真正需要獲得數據的時候，才實施計算，另外可以在實施計算時，可以有更多的信息，從而實施各種優化手段。例如，ORM操作中，并不及時載入對象，當對象真正需要時，批量載入多個Lazy的對象，從而優化IO也是一例。

上一篇：C++的錯誤和異常處理分析

下一篇：JAVA與C++::關于JNI中文字符串操作問題總結