c++ - 如何加快计算大文件中某个单词的出现次数？

Question

我需要计算字符串 "<page>" 的出现次数在一个 104gb 的文件中，用于获取给定维基百科转储中的文章数量。首先，我试过了。

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 绑定(bind)实现转变为 I/O 绑定(bind)实现。糟糕的实现可能仍然受 CPU 限制，但它应该会好很多。

无论如何，记得启用优化!