带来一篇利用C++的StringBuilder提拔4350%的功能
在学习初期,你一定会遇到很多困难,或者说各种困难,所以你最好先将你linux中的重要内容备份,因为,在你学习的过程中,很可能将系统搞废(eg:源混乱等);先容
常常呈现客户端打德律风埋怨说:你们的程序慢如蜗牛。你入手下手反省大概的疑点:文件IO,数据库会见速率,乃至检察web服务。可是这些大概的疑点都很一般,一点成绩都没有。
你利用最随手的功能剖析工具剖析,发明瓶颈在于一个小函数,这个函数的感化是将一个长的字符串链表写到一文件中。
你对这个函数做了以下优化:将一切的小字符串联接成一个长的字符串,实行一次文件写进操纵,制止不计其数次的小字符串写文件操纵。
这个优化只做对了一半。
你先测试年夜字符串写文件的速率,发明快如闪电。然后你再测试一切字符串拼接的速率。
好几年。
怎样回事?你会怎样克制这个成绩呢?
你也许晓得.net程序员可使用StringBuilder来办理此成绩。这也是本文的出发点。
背景
假如google一下“C++StringBuilder”,你会失掉很多谜底。有些会倡议(你)利用std::accumulate,这能够完成几近一切你要完成的:
#include<iostream>//forstd::cout,std::endl#include<string>//forstd::string#include<vector>//forstd::vector#include<numeric>//forstd::accumulateintmain(){usingnamespacestd;vector<string>vec={"hello","","world"};strings=accumulate(vec.begin(),vec.end(),s);cout<<s<<endl;//printshelloworldtostandardoutput.return0;} 今朝为止统统都好:当你有凌驾几个字符串联接时,成绩就呈现了,而且内存再分派也入手下手堆集。
std::string在函数reserver()中为办理计划供应基本。这也恰是我们的企图地点:一次分派,随便毗连。
字符串联接大概会由于沉重、愚钝的工具而严峻影响功能。因为前次存在的隐患,这个特别的怪胎给我打造贫苦,我便保持了Indigo(我想实验一些C++11里的使人线人一新的特征),并写了一个StringBuilder类的部分完成:
//Subsetofhttp://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspxtemplate<typenamechr>classStringBuilder{typedefstd::basic_string<chr>string_t;typedefstd::list<string_t>container_t;//Reasonsnottousevectorbelow.typedeftypenamestring_t::size_typesize_type;//Reusethesizetypeinthestring.container_tm_Data;size_typem_totalSize;voidappend(conststring_t&src){m_Data.push_back(src);m_totalSize+=src.size();}//Nocopyconstructor,noassignement.StringBuilder(constStringBuilder&);StringBuilder&operator=(constStringBuilder&);public:StringBuilder(conststring_t&src){if(!src.empty()){m_Data.push_back(src);}m_totalSize=src.size();}StringBuilder(){m_totalSize=0;}//TODO:Constructorthattakesanarrayofstrings.StringBuilder&Append(conststring_t&src){append(src);return*this;//allowchaining.}//ThisoneletsyouaddanySTLcontainertothestringbuilder.template<classinputIterator>StringBuilder&Add(constinputIterator&first,constinputIterator&afterLast){//std::for_eachandalambdalooklikeoverkillhere.//<b>Not</b>usingstd::copy,sincewewanttoupdatem_totalSizetoo.for(inputIteratorf=first;f!=afterLast;++f){append(*f);}return*this;//allowchaining.}StringBuilder&AppendLine(conststring_t&src){staticchrlineFeed[]{10,0};//C++11.Feelthelove!m_Data.push_back(src+lineFeed);m_totalSize+=1+src.size();return*this;//allowchaining.}StringBuilder&AppendLine(){staticchrlineFeed[]{10,0};m_Data.push_back(lineFeed);++m_totalSize;return*this;//allowchaining.}//TODO:AppendFormatimplementation.Notrelevantforthearticle.//LikeC#StringBuilder.ToString()//Notetheuseofreserve()toavoidreallocations.string_tToString()const{string_tresult;//Thewholepointoftheexercise!//Ifthecontainerhasalotofstrings,reallocation(eachtimetheresultgrows)willtakeaserioustoll,//bothinperformanceandchancesoffailure.//Imeasured(incodeIcannotpublish)fractionsofasecondusingreserve,andalmosttwominutesusing+=.result.reserve(m_totalSize+1);// result=std::accumulate(m_Data.begin(),m_Data.end(),result);//Thiswouldlosetheadvantageofreservefor(autoiter=m_Data.begin();iter!=m_Data.end();++iter){result+=*iter;}returnresult;}//likejavascriptArray.join()string_tJoin(conststring_t&delim)const{if(delim.empty()){returnToString();}string_tresult;if(m_Data.empty()){returnresult;}//Hopewedontoverflowthesizetype.size_typest=(delim.size()*(m_Data.size()-1))+m_totalSize+1;result.reserve(st);//IfyouneedreasonstoloveC++11,hereisone.structadder{string_tm_Joiner;adder(conststring_t&s):m_Joiner(s){//ThisconstructorisNOTempty.}//Thisfunctorrunsunderaccumulate()withoutreallocations,iflhasreservedenoughmemory.string_toperator()(string_t&l,conststring_t&r){l+=m_Joiner;l+=r;returnl;}}adr(delim);autoiter=m_Data.begin();//Skipthedelimiterbeforethefirstelementinthecontainer.result+=*iter;returnstd::accumulate(++iter,m_Data.end(),result,adr);}};//classStringBuilder 风趣的部分
函数ToString()利用std::string::reserve()来完成最小化再分派。上面你能够看到一本性能测试的了局。
函数join()利用std::accumulate(),和一个已为首个操纵数预留内存的自界说函数。
你大概会问,为何StringBuilder::m_Data用std::list而不是std::vector?除非你有一个用其他容器的好来由,一般都是利用std::vector。
好吧,我(如许做)有两个缘故原由:
1.字符串老是会附加到一个容器的开端。std::list同意在不必要内存再分派的情形下如许做;由于vector是利用一个一连的内存块完成的,每用一个便可能招致内存再分派。
2.std::list对按次存取相称有益,并且在m_Data上所做的独一存取操纵也是按次的。
你能够倡议同时测试这两种完成的功能和内存占用情形,然后选择个中一个。
功能评价
为了测试功能,我从Wikipedia猎取一个网页,并将个中一部份内容写逝世到一个string的vector中。
随后,我编写两个测试函数,第一个在两个轮回中利用尺度函数clock()并挪用std::accumulate()和StringBuilder::ToString(),然后打印了局。
voidTestPerformance(constStringBuilder<wchar_t>&tested,conststd::vector<std::wstring>&tested2){constintloops=500;clock_tstart=clock();//Giveupsomeaccuracyinexchangeforplatformindependence.for(inti=0;i<loops;++i){std::wstringaccumulator;std::accumulate(tested2.begin(),tested2.end(),accumulator);}doublesecsAccumulate=(double)(clock()-start)/CLOCKS_PER_SEC;start=clock();for(inti=0;i<loops;++i){std::wstringresult2=tested.ToString();}doublesecsBuilder=(double)(clock()-start)/CLOCKS_PER_SEC;usingstd::cout;usingstd::endl;cout<<"Accumulatetook"<<secsAccumulate<<"seconds,andToString()took"<<secsBuilder<<"seconds."<<"Therelativespeedimprovementwas"<<((secsAccumulate/secsBuilder)-1)*100<<"%"<<endl;} 第二个则利用更准确的Posix函数clock_gettime(),并测试StringBuilder::Join()。
#ifdef__USE_POSIX199309//Thanksto<ahref="http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/">GuyRutenberg</a>.timespecdiff(timespecstart,timespecend){timespectemp;if((end.tv_nsec-start.tv_nsec)<0){temp.tv_sec=end.tv_sec-start.tv_sec-1;temp.tv_nsec=1000000000+end.tv_nsec-start.tv_nsec;}else{temp.tv_sec=end.tv_sec-start.tv_sec;temp.tv_nsec=end.tv_nsec-start.tv_nsec;}returntemp;}voidAccurateTestPerformance(constStringBuilder<wchar_t>&tested,conststd::vector<std::wstring>&tested2){constintloops=500;timespectime1,time2;//Dontforgettoadd-lrttotheg++linkercommandline.//////////////////Teststd::accumulate()////////////////clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time1);for(inti=0;i<loops;++i){std::wstringaccumulator;std::accumulate(tested2.begin(),tested2.end(),accumulator);}clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time2);usingstd::cout;usingstd::endl;timespectsAccumulate=diff(time1,time2);cout<<tsAccumulate.tv_sec<<":"<<tsAccumulate.tv_nsec<<endl;//////////////////TestToString()////////////////clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time1);for(inti=0;i<loops;++i){std::wstringresult2=tested.ToString();}clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time2);timespectsToString=diff(time1,time2);cout<<tsToString.tv_sec<<":"<<tsToString.tv_nsec<<endl;//////////////////Testjoin()////////////////clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time1);for(inti=0;i<loops;++i){std::wstringresult3=tested.Join(L",");}clock_gettime(CLOCK_THREAD_CPUTIME_ID,&time2);timespectsJoin=diff(time1,time2);cout<<tsJoin.tv_sec<<":"<<tsJoin.tv_nsec<<endl;//////////////////Showresults////////////////doublesecsAccumulate=tsAccumulate.tv_sec+tsAccumulate.tv_nsec/1000000000.0;doublesecsBuilder=tsToString.tv_sec+tsToString.tv_nsec/1000000000.0;doublesecsJoin=tsJoin.tv_sec+tsJoin.tv_nsec/1000000000.0;cout<<"Accurateperformancetest:"<<endl<<"Accumulatetook"<<secsAccumulate<<"seconds,andToString()took"<<secsBuilder<<"seconds."<<endl<<"Therelativespeedimprovementwas"<<((secsAccumulate/secsBuilder)-1)*100<<"%"<<endl<<"Jointook"<<secsJoin<<"seconds."<<endl;}#endif//def__USE_POSIX199309 最初,经由过程一个main函数挪用以上完成的两个函数,将了局显现在把持台,然后实行功能测试:一个用于调试设置。
另外一个用于刊行版本:
看到这百分比没?渣滓邮件的发送量都不克不及到达这个级别!
代码利用
在利用这段代码前,思索利用ostring流。正如你鄙人面看到Jeff师长教师批评的一样,它比这篇文章中的代码更快些。
你大概想利用这段代码,假如:
[*]你正在编写由具有C#履历的程序员保护的代码,而且你想供应一个他们所熟习接口的代码。
[*]你正在编写未来会转换成.net的、你想指出一个大概路径的代码。
[*]因为某些缘故原由,你不想包括<sstream>。几年以后,一些流的IO完成变得很烦琐,并且如今的代码仍旧不克不及完整挣脱他们的搅扰。
要利用这段代码,只要依照main函数完成的那样就能够了:创立一个StringBuilder的实例,用Append()、AppendLine()和Add()给它赋值,然后挪用ToString函数检索了局。
就像上面如许:
intmain(){//////////////////////////////////////8-bitcharacters(ANSI)////////////////////////////////////StringBuilder<char>ansi;ansi.Append("Hello").Append("").AppendLine("World");std::cout<<ansi.ToString();//////////////////////////////////////Widecharacters(Unicode)//////////////////////////////////////http://en.wikipedia.org/wiki/Cargo_cultstd::vector<std::wstring>cargoCult{L"A",L"cargo",L"cult",L"is",L"a",L"kind",L"of",L"Melanesian",L"millenarian",L"movement",//manymorelineshere...L"applied",L"retroactively",L"to",L"movements",L"in",L"a",L"much",L"earlier",L"era.
"};StringBuilder<wchar_t>wide;wide.Add(cargoCult.begin(),cargoCult.end()).AppendLine();//useToString(),justlike.netstd::wcout<<wide.ToString()<<std::endl;//javascript-likejoin.std::wcout<<wide.Join(L"_
")<<std::endl;//////////////////////////////////////Performancetests////////////////////////////////////TestPerformance(wide,cargoCult);#ifdef__USE_POSIX199309AccurateTestPerformance(wide,cargoCult);#endif//def__USE_POSIX199309return0;} 任何情形下,当毗连凌驾几个字符串时,小心std::accumulate函数。
如今稍等一下!
你大概会问:你是在试着压服我们提早优化吗?
不是的。我赞成提早优化是糟的。这类优化并非提早的:是实时的。这是基于履历的优化:我发明本人已往一向在和这类特别的怪胎奋斗。基于履历的优化(不在统一个中央跌倒两次)并非提早优化。
当我们优化功能时,“惯犯”会包含磁盘I-O操纵、收集会见(数据库、web服务)和内层轮回;关于这些,我们应当增加内存分派和功能糟的KeyserS 可以说是C++的核心,相对来说也比较难以理解,因为这些技术很多都是面向于写库的人,初学C++的人很难用得上。 但是这样的好处是很多的,用string和vector可以很早的写出很有用的程序,而不用考虑内存分配与指针问题。 问问自己: 这个软件如果是你下载来的.想用.那应该是怎么样的? 确实如此,你让一个使用惯C++的人看你在程序中夹杂些诸如 printf(),scanf(),这些原本就很简单的函数,实在有些过分,一个cout直接就很清晰的输出语句,被搞得又是变量类型,又是变量名称。 只有全面撑握了这些东西. 然后你学了语法..就要经常锻炼 . 写不好没关系. 哪怕再小的程序.. 你写写改改 虽然还不明确软件技术包含的具体内容,但从C++语言这门课程开始,已发现程序设计的乐趣,在学习C++语言的过程中也学到了许多计算机应用基础知识,对计算机的机体也有了一个大体的了解。 确实如此,你让一个使用惯C++的人看你在程序中夹杂些诸如 printf(),scanf(),这些原本就很简单的函数,实在有些过分,一个cout直接就很清晰的输出语句,被搞得又是变量类型,又是变量名称。
页:
[1]