奇技淫巧C++之懒惰计较

副标题#e#

思量这样一个表达式语句：

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

#p#副标题#e#

第二步，看看怎么实现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 != ‘’) str.push_back(*src++);
}

机能阐明：

string str;
str.reserve(length(left) + length(right));

这里，回收str是没有须要的，在机能要害的场所，这里完全可以用内存块代替，可以改进机能。别的,length的计较，对付string和char [SIZE]这两种形式，都是常数时间，后一种更是可以在编译期优化掉，无需计较。可是，对付char*这种形势，strlen导致一次线性扫描。在 append的进程中，再一次线性扫描同一个数据来历，这是可以继承优化的处所。可是在这里继承分解的话，就弱化了我们懒惰计较的主旨了。在这里，只是展 示懒惰计较的威力。实际上，懒惰计较在ORM情况下也是经常用到的，虽然也包罗数据库操纵，和从文件加载工具这样的操纵。 为 了得到某个数据，必需举办事先的若干处理惩罚才气得到，假设事先处理惩罚的相对本钱较量高，那么就可以思量懒惰计较，在真正需要得到数据的时候，才实施计较，别的 可以在实施计较时，可以有更多的信息，从而实施各类优化手段。譬喻，ORM操纵中，并不实时载入工具，当工具真正需要时，批量载入多个Lazy的工具，从 而优化IO也是一例。