在C++中查找文本行数的最快方法

27

在对文件进行某些操作之前,我需要读取文件中的行数。当我尝试读取文件并在每次迭代时将line_count变量增加直至到达EOF时,这在我的情况下并不快速。我同时使用了ifstreamfgets,它们都很慢。是否有一种hacky的方法来做到这一点,比如被BSD、Linux内核或Berkeley DB使用的位操作方法。

该文件中的行数为数百万行,并且不断增加,每行大约有40或50个字符。我正在使用Linux。

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

9个回答

20

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

1
我想补充一下,1MB的大小应该是1,048,576字节而不是1,000,000字节。更准确地说,它应该是存储文件的设备的“块大小”的倍数。根据我的经验,硬盘驱动器的块大小为512字节,CD / DVD驱动器的块大小为2048字节。不知道是否在某些规范中有所说明。 - Vilx-
此外,您不应一次读取一个块。每次读取操作都有固定的开销,因此一次读取更多的数据,您的处理速度将更快。然而,我也发现(对于HDD),如果您一次读取400个块或800个块,整体速度几乎没有什么区别。所以我想1,048,576字节足矣了。 - Vilx-
1
实际上,发布的代码有点有缺陷 - 大缓冲区被初始化为零(因为它是一个向量)。您可以使用 new char[SZ] 来消除启动时的负担。我的借口是这是我留下来的一些代码(带有一个更小的缓冲区),我只是快速复制和粘贴了它。 - anon
1
在某个点之上,使用更大的缓冲区实际上会导致性能变慢,因为RAM中较少的内容适合L2缓存。对于非常大的缓冲区,操作系统可能需要分页到磁盘以便提供所请求的RAM数量。 - j_random_hacker
1
你可以用std::count(buf.begin(), buf.end(), '\n')替换CountLines - utnapistim
显示剩余6条评论

11
不要使用C++ stl字符串和getline(或C的fgets),仅使用C风格的原始指针,并以页面大小块读取或mmap文件。然后,使用系统本机字大小(即uint32_tuint64_t)扫描块,使用其中一种“SIMD Within A Register(SWAR)Operations” magic algorithms测试单词中的字节。一个示例在这里; 循环中带有0x0a0a0a0a0a0a0a0aLL的代码扫描换行符。(该代码每个文件行上的输入字节匹配正则表达式约为5个周期)
如果文件只有几十兆字节或一百多兆字节,并且它不断增长(即某些内容不断写入它),那么很可能linux已经将其缓存在内存中,因此它不会受到磁盘IO限制,但会受到内存带宽限制。
如果文件仅被追加,您还可以记住行数和先前长度,并从那里开始。
已经有人指出你可以在C++ stl算法中使用mmap,然后创建一个函数对象传递给std::foreach。我建议你不要这样做,不是因为你不能用这种方式实现,而是写额外的代码没有任何好处。或者你可以使用boost的mmapped迭代器,它可以为你处理所有的事情;但是对于我提供链接的问题来说,这种方法非常慢,而且这个问题是关于速度而不是风格的。

1
你完全可以在C++中使用mmap或者读取块的方式,没有任何理由不允许这样做。 - anon
3
当然没有C++的“C子集”。仅仅因为你没有使用std容器或字符串并不意味着它在某种程度上“不是C ++”。 - anon
1
补充Neil所说的,标准算法在原始内存上使用指针作为迭代器完全正常。您可以轻松编写执行指定SIMD技巧的函数对象,并使用std :: for_each在文件数据上运行它。STL不仅仅是容器。 - jalf
1
@Neil 你非常清楚,C++ 中有一部分子集非常接近于惯用的 C。我之前发布过完全相同的回复,并因其更像 C 而受到批评;你无法取胜。 - Pete Kirkham
你可以编写自定义分配器,然后使用std::vector - user1804599
显示剩余3条评论

10

您写到 它不断增加

这听起来像是一个日志文件或类似的东西,新的行被追加但现有的行没有改变。如果是这种情况,您可以尝试一种增量方法

  • 解析到文件结尾。
  • 记住行数和 EOF 的偏移量。
  • 当文件增长时,使用 fseek 跳转到偏移量,解析到 EOF 并更新行数和偏移量。

是的,这就像一个日志文件(但不是一个日志文件:它是来自多个开发者的几个日志文件的统计数据),而且这个程序是由另一个人开发和维护的。但你需要一个可行的本地解决方案。但我只是想知道一个全局最优解,可以在没有关于文件的先验知识的情况下快速计算。这只是出于好奇 :)。 - systemsfault

6
计算行数和计算换行符之间是存在差异的。以下是一些需要注意的常见问题,如果确保获得准确的行数很重要:
  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. 您必须考虑是否要将一些其他控制字符视为换行符。例如,U+000C FORM FEEDU+000B LINE TABULATION(也称为垂直制表符)应该被视为新起一行吗?

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

  6. 如果文件中存在超长行,则getline()方法可能会引发异常,导致简单的行计数器无法处理少量文件。(如果您在非Mac平台上读取旧版Mac文件,则特别如此,因为getline()将整个文件视为一个大行。)通过将块读入固定大小的缓冲区并使用状态机,您可以使其适用于所有文件。

被接受的答案中的代码存在大多数这些陷阱。先让程序正确运行,然后再考虑加速。


1
+1,很好的观点。#3吓到我了——第一次听说这个!<发抖> - j_random_hacker
@j_random_hacker 是啊,我也是! :O - Kounavi
值得注意的是关于第二点:如果一行没有以新行结束,根据POSIX标准,它从定义上来说不是一行,而是一行不完整,这是一个非常好的理由。一行是零个或多个以0x0a结尾的字节。文本文件应该以新行结束。有些人会极力去编写不以新行结束的代码文件。这些文件很可能会导致各种工具/链出现错误或中断。所以按照这个标准,“Hello, World!”是零行而不是一行 ;) - user3342816
1
@user3342816:Posix只是处理文本文件的系统子集。在互联网世界中,人们从各种系统共享文件(网络协议通常使用“\x0D\x0A”作为行分隔符),因此考虑到存在许多其他标准,这是明智之举。 - Adrian McCarthy
当然。但是我认为你可能误解了我的评论意图。在不知道文件的“格式/来源”的情况下,无法计算行数。 OP使用的是Linux,在那里文本文件通常由以0x0a结尾的行组成。如果在Linux上使用Windows文本文件,则通常首先将它们转换。至于网络协议,当然它们大多使用0x0d0a,但这并不是负载的原因。他们(大多数?)不处理,而是字节。我绝不是说这是一个糟糕的答案,但认为至少值得在评论中提到。 - user3342816
@user3342816 一些程序员花了很长时间才弄清楚如何将"\r","\n"或"\r\n"解析为一个行结束标记。现在大多数工具都能够理解其中的任何一个(终于)。老实说,这并不难,而且这样你就可以避免转换。现在,随着互联网的发展,文件可以从任何来源接收数据,包括旧版Mac、MS-Windows系统和Unix系统,这意味着你的文件中可能会出现不同的换行符。我认为Adrian在他的回答中试图解决这个问题。 - Alexis Wilke

4

请记住,所有的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.
}

我已经运行了您的代码,并与我发布的两个可能的实现进行了比较。您的代码与getline()版本的速度相同(即显式缓冲区的一半),但不幸的是,它也打印出了错误的行数 - 对于我在Windows格式下终止为CR/LF的百万行文本文件上发布的实现,它输出了1000001而不是1000000行。 - anon
PS 它似乎认为 test.last 包含零字节。 - anon
这是因为文件以文本模式打开。这会强制进行EOL转换,需要处理。如果文件以二进制模式打开,则没有EOL转换,速度会更快。是否需要EOL转换取决于您正在做什么。 - Martin York
@Neil:Windows格式以CR/LF结尾:此序列应由流自动转换为“\n”,因为它是EOL标记。如果您将文件从一个操作系统移动到另一个操作系统,则所有的赌注都会失效,您应该在使用之前转换文件。请参见dos2unix。 - Martin York

3
你的算法并不慢,而是由于IO操作缓慢。我猜你使用了一个简单的O(n)算法,只是按顺序遍历文件。在这种情况下,没有更快的算法可以优化你的程序。
然而,我说没有更快的算法,但有一种更快的机制称为“内存映射文件”。映射文件有一些缺点,可能不适用于你的情况,所以你需要自己阅读并找出解决方案。
内存映射文件不能让你实现比O(n)更好的算法,但它可能会减少IO访问时间。

3
这个问题是关于如何加快运行时间,而不是算法的可扩展性。一个每N个周期需要几个循环的O(n)算法比一个每个n需要一年的算法更快。 - Pete Kirkham

3
你只能通过扫描整个文件寻找换行符来得出明确的答案。没有其他方法。
但是,有几种可能性需要考虑。
1/ 如果你使用简单的循环,每次读取一个字符并检查换行符,则不要这样做。尽管I/O可能会进行缓冲,但函数调用本身在时间上是昂贵的。
更好的选择是使用单个I/O操作将大块文件(例如5M)读入内存,然后进行处理。你可能不需要太担心特殊的汇编指令,因为C运行时库将被优化 - 一个简单的 strchr()应该就可以了。
2/ 如果你说通用行长度约为40-50个字符,并且你不需要精确的行数,请获取文件大小并将其除以45(或者你认为要使用的平均值)。
3/ 如果这类似于日志文件,并且你不必将其保留在一个文件中(可能需要重新设计系统的其他部分),请考虑定期拆分文件。
例如,当它达到5M时,将其移动(例如,x.log)到一个带日期的文件名(例如,x_20090101_1022.log),并计算此时有多少行(将其存储在x_20090101_1022.count中),然后开始一个新的x.log日志文件。日志文件的特性意味着创建的这个日期部分将永远不会更改,因此您永远不必重新计算行数。
要处理日志“文件”,你只需要通过一些进程管道cat x_*.log而不是cat x.log即可。要获取“文件”的行数,请在当前x.log上执行wc -l(相对较快),并将其添加到x_*.count文件中所有值的总和中。

1
加载40多MB到内存需要时间。最快的方法是将其映射到内存中,或者一次性加载到一个大缓冲区中。一旦你将它加载到内存中,无论如何实现,遍历数据查找\n字符的循环几乎是瞬间完成的。
因此,真正重要的技巧是尽快将文件加载到内存中。而最快的方法是作为单个操作完成。
否则,可能存在许多技巧来加速算法。如果只添加行,从不修改或删除,并且您反复读取文件,则可以缓存先前读取的行,下一次必须读取文件时,只需读取新添加的行。
或者,您可以维护一个单独的索引文件,显示已知'\n'字符的位置,以便可以跳过文件的这些部分。
从硬盘读取大量数据很慢。没有办法避免这一点。

在某个点之上,使用更大的缓冲区实际上会导致更慢的性能,因为RAM中适合L2缓存的部分会减少。对于非常大的缓冲区,操作系统可能需要将页面换出到磁盘,以便为您提供所请求的RAM数量。 - j_random_hacker

0

如果您的文件只会增长,那么如果您无法控制作者,Ludwig Weinzierl是最好的解决方案。否则,您可以使其更快:每次写入文件时,将计数器加一。如果多个作者可能同时尝试写入文件,请确保使用锁定。锁定现有文件就足够了。计数器可以是4或8字节的二进制文件,写在/run/<your-prog-name>/counter下(这是RAM,速度非常快)。

Ludwig算法

  • 将偏移量初始化为0
  • 从偏移量到EOF读取文件,并计算'\n'的数量(如其他人所提到的,请确保使用缓冲I/O并在该缓冲区内计算'\n'
  • 使用EOF处的位置更新偏移量
  • 将计数器和偏移量保存到文件中,或者如果您只需要在软件中使用它,则保存在变量中
  • 在更改时重复从"读取文件..."开始

实际上,这就是各种处理日志文件的软件功能的方式(例如,我想到了fail2ban)。

第一次,它必须处理一个巨大的文件。之后,它非常小,因此速度非常快。

主动算法

创建文件时,将计数器重置为0。

然后每次收到要添加到文件中的新行:

  • 锁定文件
  • 写入一行
  • 加载计数器
  • 将计数器加1
  • 保存计数器
  • 解锁文件

这非常接近数据库系统所做的事情,因此对于具有数百万行的表的SELECT COUNT(*) FROM table会立即返回结果。数据库也会针对每个索引执行此操作。因此,如果您添加与特定索引匹配的WHERE子句,则还可以立即获得总数。与上述原理相同。


个人笔记:我看到了大量的互联网软件都是落后的。在软件环境中,看门狗对于各种事情都有意义。然而,在大多数情况下,当发生重要事件时,您应该立即发送消息,而不是使用检查日志来检测刚刚发生的不良事件的落后概念。
例如,您检测到用户尝试访问网站并连续5次输入错误密码。您想发送即时消息给管理员,以确保没有第6次成功尝试,黑客现在可以看到您所有用户的数据...如果使用日志,则“即时消息”将会晚几秒甚至几分钟。
不要倒退处理。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接