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

Question

在对该文件执行某些操作之前,我需要读取文件中的行数.当我尝试读取文件并在每次迭代时递增line_count变量,直到我达到eof.在我的情况下,这并不是那么快.我同时使用了ifstream和fgets.他们都很慢.有没有一种hacky方法可以做到这一点,例如BSD,Linux内核或berkeley db也可以使用它(可以使用按位运算).

正如我之前所说,该文件中有数百万行,并且它会不断变大,每行约有40或50个字符.我正在使用Linux.

注意:我确信会有人说可能会使用数据库白痴.但在我的情况下,我不能使用数据库.

Answer 1

找到行计数的唯一方法是读取整个文件并计算行尾字符的数量.tom执行此操作的最快方法可能是将整个文件读入一个具有一次读取操作的大缓冲区,然后通过缓冲区计算'\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;
}

Answer 2

不要使用C++ stl字符串和getline(或C的fgets),只使用C样式的原始指针,并在页面大小的块中块读取或mmap文件.

然后使用魔术算法 "SIMD IN A Register(SWAR)操作" 之一扫描系统本机字大小的块(即,uint32_t或者uint64_t),以测试字中的字节.一个例子是在这里 ; 带有in 的循环扫描换行符.(该代码在每个输入字节大约5个周期与文件的每一行上的正则表达式匹配)0x0a0a0a0a0a0a0a0aLL

如果文件只有几十或一百左右的兆字节,并且它不断增长(即有些东西不断写入),那么linux很可能将它缓存在内存中,因此它不会受到磁盘IO的限制,但内存带宽有限.

如果文件只是被附加到,你还可以记住行数和以前的长度,并从那里开始.

有人指出你可以使用mmap与C++ stl算法,并创建一个函子来传递给std :: foreach.我建议你不要这样做,不是因为你不能这样做,而是写这些额外的代码没有收获.或者你可以使用boost的mmapped迭代器,它可以为你处理它; 但是对于这个问题,我链接到的代码是为了这个而写得慢得多,问题是关于速度而不是风格.

Answer 3

你写道它会不断变大.这听起来像是一个日志文件或类似的东西,其中添加了新行但现有行不会更改.如果是这种情况,您可以尝试增量方法.

解析到文件末尾.记住行数和EOF的偏移量.当文件增长fseek到偏移量时,解析为EOF并更新行数和偏移量.

Answer 4

计数线和计数线分隔符之间存在差异.如果获得精确的行数,需要注意的一些常见问题很重要:

1. 什么是文件编码？逐字节解决方案适用于ASCII和UTF-8,但请注意,如果您使用UTF-16或某些多字节编码,并不能保证具有换行值的字节必须编码换行符.

2. 许多文本文件在最后一行的末尾没有行分隔符.因此,如果您的文件显示"Hello, World!",您最终可能会计数为0而不是1.而不是仅仅计算行分隔符,您需要一个简单的状态机来跟踪.

3. 一些非常模糊的文件使用Unicode U+2028 LINE SEPARATOR(或甚至U+2029 PARAGRAPH SEPARATOR)作为行分隔符,而不是更常见的回车和/或换行符.您可能还需要注意U+0085 NEXT LINE (NEL).

4. 您必须考虑是否要将其他控制字符计为断路器.例如,是否应将a U+000C FORM FEED或U+000B LINE TABULATION(也称为垂直制表符)视为新行？

5. 旧版Mac OS(OS X之前)中的文本文件使用回车符(U+000D)而不是换行符(U+000A)来分隔行.如果您正在将原始字节读入缓冲区(例如,您的流处于二进制模式)并扫描它们,那么您将在这些文件上计数为0.您不能同时计算回车和换行,因为PC文件通常以两者结束.同样,你需要一个简单的状态机.(或者,您可以在文本模式而不是二进制模式下读取文件.文本界面会将行分隔符规范化'\n'为符合平台上使用的约定的文件.如果您正在从其他平台读取文件,那么您将是使用状态机返回二进制模式.)

6. 如果文件中有超长行,则该getline()方法会抛出异常,导致简单行计数器在少量文件上失败.(如果您在非Mac平台上阅读旧的Mac文件,尤其如此,导致getline()将整个文件视为一条巨大的线路.)通过将块读取到固定大小的缓冲区并使用状态机,您可以使它成为防弹.

接受的答案中的代码会受到大多数陷阱的影响.在你快速完成之前做好.