性能 - 使用字符串構造函數vs使用串聯

我對C++比較陌生。我正在練習一個編碼問題，這與將字符串轉換爲迴文有關。性能 - 使用字符串構造函數vs使用串聯

我被存儲在一個矢量中的字母計數和以後產生這樣的迴文 -

string palindrome_string; 
for (short i = 0; i < 26; ++i) { 
    alphabet_count[i] /= 2; 
    for (short j = 0; j < alphabet_count[i]; ++j) 
     palindrome_string += string(1, static_cast<char>('a' + i)); 
}

但是，對於一個特定的測試的情況下（含有2.10僅^ 5點e的輸入），則程序被超過內存限制爲256 MB。然後，我用這個語句替換了內部循環 -

palindrome_string += string(alphabet_count[i], static_cast<char>('a' + i));

並且程序運行良好，只使用了大約2.4 MB。

所以我想問一下，這是否與使用連接vs構造函數的性能有關，如果是，那麼可能的原因是什麼？

如果它的事項，我編譯MS VC++ 2010

程序如果有幫助，這裏有意見書（代碼） - the failed one（測試用例：10）和the successful one。

來源

2017-07-09 PalashV

當你這樣做時，你可能會在每次迭代中獲得新的分配。大概每次分配稍大一點的分片對於分配器來說都是不好的情況。然而，它很糟糕仍然令人驚訝。 – zch

@zch同意。字符串在構建時預先分配一些內存空間。 OP可以嘗試用一個簡單的char來替換字符串結構：palindrome_string + ='a'+ i; – texasbruce

構建臨時字符串實際上沒有意義。 'palindrome_string.append（static_cast （'a'+ i），alphabet_count [i]）'會做同樣的事情。 – VTT

std::string應該以達到攤銷的恆定時間的方式分配內存。正如here所述，每次需要更多空間時，簡單的實施將會增加2倍。

有可能每當你在內部循環中加入一些東西給palindrome_string時，該字符串會重新分配內存。但是，我不明白這是怎麼回事，這可怕的。我的意思是，即使上面提到的簡單實現在內部循環的迭代中加倍了內存，那麼在下一次迭代中就不需要重新分配空間了，對吧？

來源

2017-07-09 20:36:36 gsamaras

我最初認爲'char'是1個字節，因爲問題保證了最大值。 2.10^5個字符，我認爲它不應該超過〜200 KB，但顯然，它不能這樣工作，它是如何以MB爲單位的，這仍然讓我感到困惑。 – PalashV

我看到你回答了你的問題，好消息@PalashV〜 – gsamaras

謝謝。我無法在接下來的2-3天中弄清楚問題，而且問題沒有得到任何答覆，但有一天，它只是點擊了循環可能是錯誤的。我重新閱讀，這一直是我的錯。:( 感謝您的時間，但。:) – PalashV

問題不在於性能，而在於內部循環。 j的類型爲short，而alphabet_count[i]的類型爲long，這就是它發生的原因。

來源

2017-07-12 14:16:17 PalashV

性能 - 使用字符串構造函數vs使用串聯

回答

相關問題