如何加速計算大文件中單詞的出現次數？

Question

我需要計算104gb文件中字符串"<page>"的出現次數，以獲取給定Wikipedia轉儲中的文章數量。首先，我已經試過了。

grep -F '<page>' enwiki-20141208-pages-meta-current.xml | uniq -c 

但是，一段時間後，grep崩潰了。所以我寫了下面的程序。但是，它只處理我機器上20mb/s的輸入文件，這大約是我硬盤5％的工作量。我怎樣才能加快這個代碼？

#include <iostream> 
#include <fstream> 
#include <string> 

int main() 
{ 
    // Open up file 
    std::ifstream in("enwiki-20141208-pages-meta-current.xml"); 
    if (!in.is_open()) { 
     std::cout << "Could not open file." << std::endl; 
     return 0; 
    } 
    // Statistics counters 
    size_t chars = 0, pages = 0; 
    // Token to look for 
    const std::string token = "<page>"; 
    size_t token_length = token.length(); 
    // Read one char at a time 
    size_t matching = 0; 
    while (in.good()) { 
     // Read one char at a time 
     char current; 
     in.read(&current, 1); 
     if (in.eof()) 
      break; 
     chars++; 
     // Continue matching the token 
     if (current == token[matching]) { 
      matching++; 
      // Reached full token 
      if (matching == token_length) { 
       pages++; 
       matching = 0; 
       // Print progress 
       if (pages % 1000 == 0) { 
        std::cout << pages << " pages, "; 
        std::cout << (chars/1024/1024) << " mb" << std::endl; 
       } 
      } 
     } 
     // Start over again 
     else { 
      matching = 0; 
     } 
    } 
    // Print result 
    std::cout << "Overall pages: " << pages << std::endl; 
    // Cleanup 
    in.close(); 
    return 0; 
} 

Answer 1

假設沒有瘋狂大文件中的行使用類似

for (std::string line; std::getline(in, line); } { 
    // find the number of "<page>" strings in line 
} 

註定是很多更快！將每個字符讀成一個字符串是關於你可能做的最糟糕的事情。真的很難讓速度變慢。對於每一個角色，有流將做這樣的事情：

1. 檢查是否存在需要衝洗tie() ED流（不存在，即，這是毫無意義的）。
2. 檢查流是否處於良好狀態（除非已達到最終結果，但不能完全忽略此檢查）。
3. 在流的流緩衝區上調用xsgetn()。
4. 這個函數首先檢查緩衝區中是否有另一個字符（類似於eof檢查但不同;在任何情況下，只有在緩衝區爲空後執行eof檢查纔會刪除大量的eof檢查）
5. 將字符傳輸到讀緩衝區。
6. 讓流檢查是否達到全部（1）個字符並根據需要設置流標誌。

那裏有很多浪費！

我真的不能想象爲什麼grep會失敗，除了某些線路在預期的最大線路長度上大規模吹襲。儘管使用std::getline()和std::string()可能會有更大的上限，但處理大量行仍然無效。如果該文件可能包含大量的線，它可能是更合理地沿着這個線路使用的東西：

for (std::istreambuf_iterator<char> it(in), end; 
    (it = std::find(it, end, '<') != end;) { 
    // match "<page>" at the start of of the sequence [it, end) 
} 

對於壞的實現，仍然做得太多流。良好的實現將非常有效地調用std::find(...)，並且可能會在一個字符處檢查多個字符，僅爲每個第16次循環迭代之類的內容添加檢查和循環。我期望上面的代碼將你的CPU綁定實現變成一個I/O綁定實現。不好的實現可能仍然是CPU限制的，但它應該仍然好很多。

在任何情況下，請記住啓用優化！

Answer 2

我使用這個文件來測試有：http://dumps.wikimedia.org/enwiki/latest/enwiki-latest-pages-meta-current1.xml-p000000010p000010000.bz2

它使用你的代碼需要大約2.4秒與11.5。由於不包括換行符，因此總字符數有所不同，但我認爲這是可接受的，因爲它僅用於顯示進度。

void parseByLine() 
{ 
    // Open up file 
    std::ifstream in("enwiki-latest-pages-meta-current1.xml-p000000010p000010000"); 
    if(!in) 
    { 
     std::cout << "Could not open file." << std::endl; 
     return; 
    } 
    size_t chars = 0; 
    size_t pages = 0; 
    const std::string token = "<page>"; 

    std::string line; 
    while(std::getline(in, line)) 
    { 
     chars += line.size(); 
     size_t pos = 0; 
     for(;;) 
     { 
      pos = line.find(token, pos); 
      if(pos == std::string::npos) 
      { 
       break; 
      } 
      pos += token.size(); 
      if(++pages % 1000 == 0) 
      { 
       std::cout << pages << " pages, "; 
       std::cout << (chars/1024/1024) << " mb" << std::endl; 
      } 
     } 
    } 
    // Print result 
    std::cout << "Overall pages: " << pages << std::endl; 
} 

下面是一個將每行添加到緩衝區並在達到閾值時處理緩衝區的示例。它需要2秒，而從第一版本到2.4。我使用了幾個不同的緩衝區大小閾值，並且在固定數量（16,32,64,4096）行之後進行處理，只要有一些批處理進行，似乎都是一樣的。感謝Dietmar提出這個想法。

int processBuffer(const std::string& buffer) 
{ 
    static const std::string token = "<page>"; 

    int pages = 0; 
    size_t pos = 0; 
    for(;;) 
    { 
     pos = buffer.find(token, pos); 
     if(pos == std::string::npos) 
     { 
      break; 
     } 
     pos += token.size(); 
     ++pages; 
    } 
    return pages; 
} 

void parseByMB() 
{ 
    // Open up file 
    std::ifstream in("enwiki-latest-pages-meta-current1.xml-p000000010p000010000"); 
    if(!in) 
    { 
     std::cout << "Could not open file." << std::endl; 
     return; 
    } 
    const size_t BUFFER_THRESHOLD = 16 * 1024 * 1024; 
    std::string buffer; 
    buffer.reserve(BUFFER_THRESHOLD); 

    size_t pages = 0; 
    size_t chars = 0; 
    size_t progressCount = 0; 

    std::string line; 
    while(std::getline(in, line)) 
    { 
     buffer += line; 
     if(buffer.size() > BUFFER_THRESHOLD) 
     { 
      pages += processBuffer(buffer); 
      chars += buffer.size(); 
      buffer.clear(); 
     } 
     if((pages/1000) > progressCount) 
     { 
      ++progressCount; 
      std::cout << pages << " pages, "; 
      std::cout << (chars/1024/1024) << " mb" << std::endl; 
     } 
    } 
    if(!buffer.empty()) 
    { 
     pages += processBuffer(buffer); 
     chars += buffer.size(); 
     std::cout << pages << " pages, "; 
     std::cout << (chars/1024/1024) << " mb" << std::endl; 
    } 
}