查找文本行数的最快方法 (C)

Question

在对该文件执行某些操作之前，我需要读取文件中的行数。当我尝试读取文件并在每次迭代时增加 line_count 变量直到达到 EOF 。就我而言，它并没有那么快。我同时使用了 ifstream 和 fgets 。他们俩都很慢。是否有一种 hacky 方法可以做到这一点，例如 BSD、Linux 内核或 berkeley db（可能是通过使用按位运算）也使用这种方法。

该文件中的行数以百万计，并且不断变大，每行大约 40 或 50 个字符。我正在使用 Linux。

笔记：

我敢肯定会有人会说使用数据库白痴。但在我的情况下，我不能使用分贝。

原文由 systemsfault 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

找到行数的唯一方法是读取整个文件并计算行尾字符的数量。最快的方法可能是通过一次读取操作将整个文件读入一个大缓冲区，然后通过缓冲区计算 ‘\n’ 字符。

由于您当前的文件大小约为 60Mb，因此这不是一个有吸引力的选择。您可以通过不读取整个文件来获得一些速度，而是以块的形式读取它，例如大小为 1Mb。您还说数据库是不可能的，但它确实看起来是最好的长期解决方案。

编辑： 我刚刚对此进行了一个小型基准测试，使用缓冲方法（缓冲区大小 1024K）似乎比使用 getline() 一次读取一行的速度快两倍多。这是代码 - 我的测试是使用 g++ 使用 -O2 优化级别完成的：

 #include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
using namespace std;

unsigned int FileRead( istream & is, vector <char> & buff ) {
    is.read( &buff[0], buff.size() );
    return is.gcount();
}

unsigned int CountLines( const vector <char> & buff, int sz ) {
    int newlines = 0;
    const char * p = &buff[0];
    for ( int i = 0; i < sz; i++ ) {
        if ( p[i] == '\n' ) {
            newlines++;
        }
    }
    return newlines;
}

int main( int argc, char * argv[] ) {
    time_t now = time(0);
    if ( argc == 1  ) {
        cout << "lines\n";
        ifstream ifs( "lines.dat" );
        int n = 0;
        string s;
        while( getline( ifs, s ) ) {
            n++;
        }
        cout << n << endl;
    }
    else {
        cout << "buffer\n";
        const int SZ = 1024 * 1024;
        std::vector <char> buff( SZ );
        ifstream ifs( "lines.dat" );
        int n = 0;
        while( int cc = FileRead( ifs, buff ) ) {
            n += CountLines( buff, cc );
        }
        cout << n << endl;
    }
    cout << time(0) - now << endl;
}

原文由 anon 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

请记住，所有 fstream 都是缓冲的。因此，它们实际上确实以块的形式读取，因此您不必重新创建此功能。所以你需要做的就是扫描缓冲区。不要使用 getline() ，因为这会迫使你调整字符串的大小。所以我只会使用 STL std::count 和流迭代器。

 #include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>

struct TestEOL
{
    bool operator()(char c)
    {
        last    = c;
        return last == '\n';
    }
    char    last;
};

int main()
{
    std::fstream  file("Plop.txt");

    TestEOL       test;
    std::size_t   count   = std::count_if(std::istreambuf_iterator<char>(file),
                                          std::istreambuf_iterator<char>(),
                                          test);

    if (test.last != '\n')  // If the last character checked is not '\n'
    {                       // then the last line in the file has not been
        ++count;            // counted. So increement the count so we count
    }                       // the last line even if it is not '\n' terminated.
}

原文由 Martin York 发布，翻译遵循 CC BY-SA 3.0 许可协议