針對標準輸入的C++ IO優化和字符串處理

Question

我正在編寫使用C++使用「標準stdin程序」的競賽程序。取入的第一行表示從那時起預計有多少行（x）作爲輸入。這些輸入行可以是字符串，整數或這兩者的某種組合，每行只包含由空格分隔的兩個元素。

string initial; 
    getline (cin,initial); 
    istringstream stringStream (initial); 
    vector<string> parsedString; 
    vector<int> data; 
    char splitToken = ' '; 
    while (!stringStream.eof()) 
    { 
    string subString; 
    getline(stringStream, subString, splitToken); 
    parsedString.push_back(subString); 
    } 

    for (int i = 0; i <parsedString.size(); i++) 
    { 
    string temp = parsedString[i]; 
    int intTemp = atoi(temp.c_str()); 
    data.push_back(intTemp); 
    } 
    unsigned int n = data[0]; 
    unsigned int m = data[1]; 

在我知道傳入的數據將是這一特定情況：目前，我在同一時間服用每行一個類似這樣的方式（要求下一行之前處理的信息）兩個整數，但情況並非總是如此。我想知道是否有辦法讓我的代碼更快，或者通過改變我的方法（可能在知道有多少期望之後立即獲取所有輸入行），或者使用更好的內置C++函數來分割入口行將空間分解爲構成它們的兩個元素。

感謝

Answer 1

通常情況下，在C++中讀取輸入的成語是沿着這些線路更多：

std::ios_base::sync_with_stdio(false); //tell iostreams to be fast 
int number_of_lines; 
std::cin >> number_of_lines; 
if (!std::cin) *ERROR*; 

for(; number_of_lines>0; --number_of_lines) { 
    unsigned n, m; 
    std::cin >> n >> m; 
    if (!std::cin) *ERROR*; 
    //process n and m here 
} 

你說「輸入的這些線可以是字符串，整數，或兩者的組合「，但你怎麼知道哪個是哪個？上面的代碼假定一切都是一個數字，因爲如果你不知道類型，輸入是無用的。

Answer 2

在許多系統上（包括Linux上的GCC），C++ I/O流非常緩慢。如果速度是您最關心的問題，請使用<stdio.h>scanf()和（甚至更快:) getchar()，並做手工解析，如以下狀態機：

int c; 
int state = 0; 
while ((c = getchar()) >= 0) { 
    switch (c) { 
    case ' ': case '\t': 
    ...; 
    ... if (state == ...) { ...; state = ...; } 
    break; 
    case '\n': 
    ...; 
    break; 
    default: 
    ...; 
    } 
} 

複製數據，幾次越好。 （例如，在問題string temp = ...中做了一個不必要的副本，可以通過使用參考：string &temp = ...來消除該副本。）如果可能，請使用該狀態來計算下一個字符c的最終位置，然後將其放在那裏，然後請勿在將來複制或移動它。

Answer 3

好吧，如果你想談論其他的方法，這裏是另一個問題： 幾乎其作品重用繩子任何代碼的大（性能）的問題，有大量複製操作。初學者使用的方法是在從字符串或內存緩衝區中查找/解析/提取水印時創建大量臨時字符串...

替代方法（當源緩衝區的生存期允許時）從緩衝區查找，分析或提取數據，而不復制源字符串的任何特定部分。要這樣做，可以使用boost::range庫和boost::iterator_range類（與boost string_algo一起使用）。這樣可以執行通常的查找/解析任務並避免複製部分字符串。從我的經驗

一個例子： 前一段時間（性能測試）我的同事寫了3個版本的相同配置解析器（配置文件約爲幾兆字節）：使用使用std::string::find

• boost::tokenizer
• 和boost::iterator_range

結果令人吃驚：

• 用-O0優化std::string::find勝（約3以上boost::tokenizer次及以上iterator_range基於解析器約5倍）
• 但-O3一切都變了：boost::iterator_range是絕對的贏家！ （約12以上std::string::find倍！）

結果是相當明確：中boost::string_algo和朋友的高度模板化的代碼是高度inilined以及...

這就是爲什麼我本人來說喜歡用boost::iterator_range解析字符串...

---

，所以我建議你讀一切（就像你可以）進入一個std::string，std::vector<char>（更好的辯論，因爲它有記憶連續性的保證，所以你可能read() FR直接流入容器）或std::deque<char>，然後使用boost::string_algo和boost::iterator_range來解析它，試圖避免從源字符串到臨時位置的任何（無用）複製... 也嘗試使用boost::lexical_cast將數字（或您自己的範圍知道數字轉換器）

一個更多的建議：儘量避免內存（經常）分配 - 這是真正的沉重的操作。 使用rserve()成員的容器，當你有線索可能的數據大小想要存儲。最後，嘗試使用自定義（棘手）分配器而不是（通常是愚蠢的）默認分配器。

note在C++ 11 std::string有內存鄰接保證std::vector。