26

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

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

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

4

8 回答 8

17

找到行数的唯一方法是读取整个文件并计算行尾字符的数量。最快的方法是通过一次读取操作将整个文件读入一个大缓冲区，然后通过缓冲区计算 '\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;
}
于 2009-05-09T11:37:24.540 回答
11

不要使用 C++ stl 字符串和getline（或 C 的 fgets），只使用 C 样式的原始指针和块读取页面大小的块或 mmap 文件。

然后使用魔术算法“寄存器内的SIMD (SWAR) 操作”之一以系统的本机字大小扫描块（即，uint32_t或者） ，以测试字中的字节。一个例子是here；带有 的循环扫描换行符。（该代码达到每个输入字节大约 5 个周期，匹配文件每一行上的正则表达式）uint64_t0x0a0a0a0a0a0a0a0aLL

如果文件只有几十或一百多兆字节，并且它一直在增长（即不断向其写入内容），那么 linux 很可能已将其缓存在内存中，因此它不会受到磁盘 IO 限制，但内存带宽有限。

如果文件只是被附加到，您还可以记住行数和以前的长度，然后从那里开始。

有人指出，您可以将 mmap 与 C++ stl 算法一起使用，并创建一个函子以传递给 std::foreach。我建议你不应该这样做，不是因为你不能那样做，而是编写额外的代码这样做没有任何好处。或者你可以使用 boost 的 mmapped 迭代器，它会为你处理这一切；但是对于我链接到的代码是为此编写的问题要慢得多，而且问题是关于速度而不是风格。

于 2009-05-09T11:38:04.213 回答
9

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

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

于 2009-05-09T12:42:42.207 回答
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 FEED或U+000B LINE TABULATION（也称为垂直制表符）换行？

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

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

已接受答案中的代码受到大多数这些陷阱的影响。在快速完成之前先做好。

于 2009-05-09T15:18:55.067 回答
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.
}
于 2009-05-09T19:16:42.750 回答
3

不是因为你的算法慢，而是因为 IO 操作很慢。我想你正在使用一个简单的 O(n) 算法，它只是按顺序遍历文件。在这种情况下，没有更快的算法可以优化您的程序。

但是，我说没有更快的算法，但是有一种更快的机制，称为“内存映射文件”，映射文件有一些缺点，它可能不适合你的情况，所以你必须阅读它并自己弄清楚。

内存映射文件不会让您实现比 O(n) 更好的算法，但它可能会减少 IO 访问时间。

于 2009-05-09T11:37:23.403 回答
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. 要获取“文件”的行数，请wc -l在当前 x.log 上执行 a（相对较快）并将其添加到x_*.count文件中所有值的总和中。

于 2009-05-09T12:10:25.450 回答
1

需要时间的事情是将 40+ MB 加载到内存中。最快的方法是要么对其进行内存映射，要么将其加载到一个大缓冲区中。一旦你以一种或另一种方式将它放在内存中，遍历数据以查找\n字符的循环几乎是瞬时的，无论它是如何实现的。

所以说真的，最重要的技巧是尽可能快地将文件加载到内存中。最快的方法是将其作为单个操作进行。

否则，可能存在很多技巧来加速算法。如果只添加行，从不修改或删除行，并且重复读取文件，则可以缓存之前读取的行，下次必须读取文件时，仅读取新添加的行。

或者，也许您可​​以维护一个单独的索引文件，显示已知 '\n' 字符的位置，以便可以跳过文件的这些部分。

从硬盘读取大量数据很慢。没有办法解决这个问题。

于 2009-05-09T12:16:09.877 回答