分享
 
 
 

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

王朝c/c++·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

考虑这样一个表达式语句:

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也是一例。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有