欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解C++中StringBuilder類的實現(xiàn)及其性能優(yōu)化

 更新時間:2016年05月18日 14:49:03   作者:jimmyjmh, monkee  
在Java和C#中,StringBuilder可以創(chuàng)造可變字符序列來動態(tài)地擴充字符串,那么在C++中我們同樣也可以實現(xiàn)一個StringBuilder并且用來提升性能,下面就來詳解C++中StringBuilder類的實現(xiàn)及其性能優(yōu)化

介紹
經(jīng)常出現(xiàn)客戶端打電話抱怨說:你們的程序慢如蝸牛。你開始檢查可能的疑點:文件IO,數(shù)據(jù)庫訪問速度,甚至查看web服務(wù)。 但是這些可能的疑點都很正常,一點問題都沒有。
你使用最順手的性能分析工具分析,發(fā)現(xiàn)瓶頸在于一個小函數(shù),這個函數(shù)的作用是將一個長的字符串鏈表寫到一文件中。
你對這個函數(shù)做了如下優(yōu)化:將所有的小字符串連接成一個長的字符串,執(zhí)行一次文件寫入操作,避免成千上萬次的小字符串寫文件操作。
這個優(yōu)化只做對了一半。
你先測試大字符串寫文件的速度,發(fā)現(xiàn)快如閃電。然后你再測試所有字符串拼接的速度。
好幾年。
怎么回事?你會怎么克服這個問題呢?
你或許知道.net程序員可以使用StringBuilder來解決此問題。這也是本文的起點。

背景

如果google一下“C++ StringBuilder”,你會得到不少答案。有些會建議(你)使用std::accumulate,這可以完成幾乎所有你要實現(xiàn)的:

#include <iostream>// for std::cout, std::endl
#include <string> // for std::string
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
int main()
{
  using namespace std;
  vector<string> vec = { "hello", " ", "world" };
  string s = accumulate(vec.begin(), vec.end(), s);
  cout << s << endl; // prints 'hello world' to standard output.
  return 0;
}

目前為止一切都好:當(dāng)你有超過幾個字符串連接時,問題就出現(xiàn)了,并且內(nèi)存再分配也開始積累。
std::string在函數(shù)reserver()中為解決方案提供基礎(chǔ)。這也正是我們的意圖所在:一次分配,隨意連接。
字符串連接可能會因為繁重、遲鈍的工具而嚴(yán)重影響性能。由于上次存在的隱患,這個特殊的怪胎給我制造麻煩,我便放棄了Indigo(我想嘗試一些C++11里的令人耳目一新的特性),并寫了一個StringBuilder類的部分實現(xiàn):

// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx
template <typename chr>
class StringBuilder {
  typedef std::basic_string<chr> string_t;
  typedef std::list<string_t> container_t; // Reasons not to use vector below.
  typedef typename string_t::size_type size_type; // Reuse the size type in the string.
  container_t m_Data;
  size_type m_totalSize;
  void append(const string_t &src) {
    m_Data.push_back(src);
    m_totalSize += src.size();
  }
  // No copy constructor, no assignement.
  StringBuilder(const StringBuilder &);
  StringBuilder & operator = (const StringBuilder &);
public:
  StringBuilder(const string_t &src) {
    if (!src.empty()) {
      m_Data.push_back(src);
    }
    m_totalSize = src.size();
  }
  StringBuilder() {
    m_totalSize = 0;
  }
  // TODO: Constructor that takes an array of strings.
 
 
  StringBuilder & Append(const string_t &src) {
    append(src);
    return *this; // allow chaining.
  }
    // This one lets you add any STL container to the string builder.
  template<class inputIterator>
  StringBuilder & Add(const inputIterator &first, const inputIterator &afterLast) {
    // std::for_each and a lambda look like overkill here.
        // <b>Not</b> using std::copy, since we want to update m_totalSize too.
    for (inputIterator f = first; f != afterLast; ++f) {
      append(*f);
    }
    return *this; // allow chaining.
  }
  StringBuilder & AppendLine(const string_t &src) {
    static chr lineFeed[] { 10, 0 }; // C++ 11. Feel the love!
    m_Data.push_back(src + lineFeed);
    m_totalSize += 1 + src.size();
    return *this; // allow chaining.
  }
  StringBuilder & AppendLine() {
    static chr lineFeed[] { 10, 0 };
    m_Data.push_back(lineFeed);
    ++m_totalSize;
    return *this; // allow chaining.
  }
 
  // TODO: AppendFormat implementation. Not relevant for the article.
 
  // Like C# StringBuilder.ToString()
  // Note the use of reserve() to avoid reallocations.
  string_t ToString() const {
    string_t result;
    // The whole point of the exercise!
    // If the container has a lot of strings, reallocation (each time the result grows) will take a serious toll,
    // both in performance and chances of failure.
    // I measured (in code I cannot publish) fractions of a second using 'reserve', and almost two minutes using +=.
    result.reserve(m_totalSize + 1);
  // result = std::accumulate(m_Data.begin(), m_Data.end(), result); // This would lose the advantage of 'reserve'
    for (auto iter = m_Data.begin(); iter != m_Data.end(); ++iter) {
      result += *iter;
    }
    return result;
  }
 
  // like javascript Array.join()
  string_t Join(const string_t &delim) const {
    if (delim.empty()) {
      return ToString();
    }
    string_t result;
    if (m_Data.empty()) {
      return result;
    }
    // Hope we don't overflow the size type.
    size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1;
    result.reserve(st);
        // If you need reasons to love C++11, here is one.
    struct adder {
      string_t m_Joiner;
      adder(const string_t &s): m_Joiner(s) {
        // This constructor is NOT empty.
      }
            // This functor runs under accumulate() without reallocations, if 'l' has reserved enough memory.
      string_t operator()(string_t &l, const string_t &r) {
        l += m_Joiner;
        l += r;
        return l;
      }
    } adr(delim);
    auto iter = m_Data.begin();
        // Skip the delimiter before the first element in the container.
    result += *iter;
    return std::accumulate(++iter, m_Data.end(), result, adr);
  }
 
}; // class StringBuilder


函數(shù)ToString()使用std::string::reserve()來實現(xiàn)最小化再分配。下面你可以看到一個性能測試的結(jié)果。
函數(shù)join()使用std::accumulate(),和一個已經(jīng)為首個操作數(shù)預(yù)留內(nèi)存的自定義函數(shù)。
你可能會問,為什么StringBuilder::m_Data用std::list而不是std::vector?除非你有一個用其他容器的好理由,通常都是使用std::vector。
好吧,我(這樣做)有兩個原因:
1. 字符串總是會附加到一個容器的末尾。std::list允許在不需要內(nèi)存再分配的情況下這樣做;因為vector是使用一個連續(xù)的內(nèi)存塊實現(xiàn)的,每用一個就可能導(dǎo)致內(nèi)存再分配。
2. std::list對順序存取相當(dāng)有利,而且在m_Data上所做的唯一存取操作也是順序的。
你可以建議同時測試這兩種實現(xiàn)的性能和內(nèi)存占用情況,然后選擇其中一個。

性能評估

為了測試性能,我從Wikipedia獲取一個網(wǎng)頁,并將其中一部分內(nèi)容寫死到一個string的vector中。
隨后,我編寫兩個測試函數(shù),第一個在兩個循環(huán)中使用標(biāo)準(zhǔn)函數(shù)clock()并調(diào)用std::accumulate()和StringBuilder::ToString(),然后打印結(jié)果。

void TestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
  const int loops = 500;
  clock_t start = clock(); // Give up some accuracy in exchange for platform independence.
  for (int i = 0; i < loops; ++i) {
    std::wstring accumulator;
    std::accumulate(tested2.begin(), tested2.end(), accumulator);
  }
  double secsAccumulate = (double) (clock() - start) / CLOCKS_PER_SEC;
 
  start = clock();
  for (int i = 0; i < loops; ++i) {
    std::wstring result2 = tested.ToString();
  }
  double secsBuilder = (double) (clock() - start) / CLOCKS_PER_SEC;
  using std::cout;
  using std::endl;
  cout << "Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds."
      << " The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%"
      << endl;
}

第二個則使用更精確的Posix函數(shù)clock_gettime(),并測試StringBuilder::Join()。

#ifdef __USE_POSIX199309
 
// Thanks to <a >Guy Rutenberg</a>.
timespec diff(timespec start, timespec end)
{
  timespec temp;
  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;
  }
  return temp;
}
 
void AccurateTestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
  const int loops = 500;
  timespec time1, time2;
  // Don't forget to add -lrt to the g++ linker command line.
  ////////////////
  // Test std::accumulate()
  ////////////////
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  for (int i = 0; i < loops; ++i) {
    std::wstring accumulator;
    std::accumulate(tested2.begin(), tested2.end(), accumulator);
  }
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
  using std::cout;
  using std::endl;
  timespec tsAccumulate =diff(time1,time2);
  cout << tsAccumulate.tv_sec << ":" << tsAccumulate.tv_nsec << endl;
  ////////////////
  // Test ToString()
  ////////////////
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  for (int i = 0; i < loops; ++i) {
    std::wstring result2 = tested.ToString();
  }
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
  timespec tsToString =diff(time1,time2);
  cout << tsToString.tv_sec << ":" << tsToString.tv_nsec << endl;
  ////////////////
  // Test join()
  ////////////////
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  for (int i = 0; i < loops; ++i) {
    std::wstring result3 = tested.Join(L",");
  }
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
  timespec tsJoin =diff(time1,time2);
  cout << tsJoin.tv_sec << ":" << tsJoin.tv_nsec << endl;
 
  ////////////////
  // Show results
  ////////////////
  double secsAccumulate = tsAccumulate.tv_sec + tsAccumulate.tv_nsec / 1000000000.0;
  double secsBuilder = tsToString.tv_sec + tsToString.tv_nsec / 1000000000.0;
    double secsJoin = tsJoin.tv_sec + tsJoin.tv_nsec / 1000000000.0;
  cout << "Accurate performance test:" << endl << "  Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds." << endl
      << "  The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%" << endl <<
       "   Join took " << secsJoin << " seconds."
      << endl;
}
#endif // def __USE_POSIX199309

最后,通過一個main函數(shù)調(diào)用以上實現(xiàn)的兩個函數(shù),將結(jié)果顯示在控制臺,然后執(zhí)行性能測試:一個用于調(diào)試配置。

2016518144242901.png (598×488)

另一個用于發(fā)行版本:

2016518144305430.png (598×488)

看到這百分比沒?垃圾郵件的發(fā)送量都不能達到這個級別!

代碼使用

在使用這段代碼前, 考慮使用ostring流。正如你在下面看到Jeff先生評論的一樣,它比這篇文章中的代碼更快些。
你可能想使用這段代碼,如果:
你正在編寫由具有C#經(jīng)驗的程序員維護的代碼,并且你想提供一個他們所熟悉接口的代碼。
你正在編寫將來會轉(zhuǎn)換成.net的、你想指出一個可能路徑的代碼。
由于某些原因,你不想包含<sstream>。幾年之后,一些流的IO實現(xiàn)變得很繁瑣,而且現(xiàn)在的代碼仍然不能完全擺脫他們的干擾。
要使用這段代碼,只有按照main函數(shù)實現(xiàn)的那樣就可以了:創(chuàng)建一個StringBuilder的實例,用Append()、AppendLine()和Add()給它賦值,然后調(diào)用ToString函數(shù)檢索結(jié)果。
就像下面這樣:

int main() {
  ////////////////////////////////////
  // 8-bit characters (ANSI)
  ////////////////////////////////////
  StringBuilder<char> ansi;
  ansi.Append("Hello").Append(" ").AppendLine("World");
  std::cout << ansi.ToString();
 
  ////////////////////////////////////
  // Wide characters (Unicode)
  ////////////////////////////////////
  // http://en.wikipedia.org/wiki/Cargo_cult
  std::vector<std::wstring> cargoCult
  {
    L"A", L" cargo", L" cult", L" is", L" a", L" kind", L" of", L" Melanesian", L" millenarian", L" movement",
// many more lines here...
L" applied", L" retroactively", L" to", L" movements", L" in", L" a", L" much", L" earlier", L" era.\n"
  };
  StringBuilder<wchar_t> wide;
  wide.Add(cargoCult.begin(), cargoCult.end()).AppendLine();
    // use ToString(), just like .net
  std::wcout << wide.ToString() << std::endl;
  // javascript-like join.
  std::wcout << wide.Join(L" _\n") << std::endl;
 
  ////////////////////////////////////
  // Performance tests
  ////////////////////////////////////
  TestPerformance(wide, cargoCult);
#ifdef __USE_POSIX199309
  AccurateTestPerformance(wide, cargoCult);
#endif // def __USE_POSIX199309
  return 0;
}

任何情況下,當(dāng)連接超過幾個字符串時,當(dāng)心std::accumulate函數(shù)。

現(xiàn)在稍等一下!

你可能會問:你是在試著說服我們提前優(yōu)化嗎?
不是的。我贊同提前優(yōu)化是糟糕的。這種優(yōu)化并不是提前的:是及時的。這是基于經(jīng)驗的優(yōu)化:我發(fā)現(xiàn)自己過去一直在和這種特殊的怪胎搏斗?;诮?jīng)驗的優(yōu)化(不在同一個地方摔倒兩次)并不是提前優(yōu)化。

相關(guān)文章

  • C/C++讀寫注冊表中二進制數(shù)據(jù)(代碼示例)

    C/C++讀寫注冊表中二進制數(shù)據(jù)(代碼示例)

    這篇文章主要介紹了使用Windows API 函數(shù)中的RegOpenKeyEx()函數(shù)和RegSetValueEx()函數(shù)來實現(xiàn)對注冊表某項寫入二進制鍵值,需要的朋友可以參考下
    2020-02-02
  • C語言八道筆試題精講帶你掌握指針

    C語言八道筆試題精講帶你掌握指針

    C語言這門課程在計算機的基礎(chǔ)教學(xué)中一直占有比較重要的地位,然而要想突破C語言的學(xué)習(xí),對指針的掌握是非常重要的,本文將具體針對指針的基礎(chǔ)做詳盡的介紹
    2022-07-07
  • C++STL教程之vector模板的使用

    C++STL教程之vector模板的使用

    模板類vector是一個動態(tài)數(shù)組,類似于string類,可存放任意類型,能夠末尾、中間增加數(shù)據(jù),基本上是是new創(chuàng)建動態(tài)數(shù)組的替代品,vector可以自動完成new和delete
    2022-08-08
  • 使用C語言編寫鋼琴小程序

    使用C語言編寫鋼琴小程序

    這篇文章主要為大家詳細(xì)介紹了使用C語言編寫鋼琴小程序,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-02-02
  • C++下標(biāo)運算符[]重載代碼示例

    C++下標(biāo)運算符[]重載代碼示例

    這篇文章主要給大家介紹了關(guān)于C++下標(biāo)運算符[]重載的相關(guān)資料,C++ 規(guī)定下標(biāo)運算符[]必須以成員函數(shù)的形式進行重載,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2024-01-01
  • 一篇文章帶你了解c++運算符重載

    一篇文章帶你了解c++運算符重載

    下面小編就為大家?guī)硪黄钊肜斫釩++運算符重載。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2021-08-08
  • C語言中g(shù)etch()函數(shù)詳解及簡單實例

    C語言中g(shù)etch()函數(shù)詳解及簡單實例

    這篇文章主要介紹了C語言中g(shù)etch()函數(shù)詳解及簡單實例的相關(guān)資料,需要的朋友可以參考下
    2017-03-03
  • 解析C語言中結(jié)構(gòu)體struct的對齊問題

    解析C語言中結(jié)構(gòu)體struct的對齊問題

    這篇文章主要介紹了C語言中結(jié)構(gòu)體struct的對齊問題,作者深入到內(nèi)存分配方面來進行解析,需要的朋友可以參考下
    2016-04-04
  • C++ string替換單個指定字符為其它字符問題

    C++ string替換單個指定字符為其它字符問題

    這篇文章主要介紹了C++ string替換單個指定字符為其它字符問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-06-06
  • 詳解散列表算法與其相關(guān)的C語言實現(xiàn)

    詳解散列表算法與其相關(guān)的C語言實現(xiàn)

    這篇文章主要介紹了詳解散列表算法與其相關(guān)的C語言實現(xiàn),平時經(jīng)常出現(xiàn)于各大考試競賽與程序員面試題目當(dāng)中,需要的朋友可以參考下
    2015-08-08

最新評論