最快的方式找到一个文本(C ++)的行数

我需要做一些操作上的文件之前读取一个文件的行数。 当我尝试读取该文件并增加line_count变量在每次迭代,直到我到达EOF。 这不是在我的情况那么快。 我同时使用ifstream的和与fgets。 他们都是缓慢。 是有哈克方式做到这一点,这也用于通过例如BSD,Linux内核或伯克利分贝。(可以是通过使用按位操作)。

正如我之前说有几百万在该文件中的行,并不断变大,每行大约有40或50个字符。 我使用的是Linux操作系统。

注:我敢肯定会有的人谁可能会说使用DB白痴。 但是,简单地在我的情况下,我不能用分贝。

--------------解决方案-------------

找到行数的唯一方法是读取整个文件,并计算了行结束字符数。 最快的方式汤姆做到这一点可能是读取整个文件到一个大的缓冲区有一个读操作,然后再通过缓冲计数'\ 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;
}

不要使用C ++ STL字符串和getline或C的与fgets),不仅仅是C风格的原始指针,要么块读的页面大小的块或mmap的文件。

然后扫描模块在您的系统(即无论是原生字长uint32_tuint64_t使用神奇的算法“SIMD内的寄存器(SWAR)运营'之一字内测试字节)。 一个例子是在这里; 与环0x0a0a0a0a0a0a0a0aLL在它扫描换行。 (即代码到达每个输入大约5个周期字节匹配上的文件的每一行正则表达式)

如果该文件是只有几十或一百多兆,而且不断增加(即东西保持写入它),然后有一个很好的可能性,Linux有它在内存中缓存的,所以它不会是磁盘IO的限制,但存储器带宽的限制。

如果文件只有永远被附加到,也能记得线和以前长度的数目,并从那里开始。



有人指出,你可以使用mmap使用C ++ STL算法,并创建一个仿函数传递到std ::的foreach。 我建议你​​不应该这样做,不是因为你不能这样做的,但在编写额外的代码这样做就没有收获。 或者您可以使用Boost的mmapped迭代器,负责处理这一切你; 但对于我联系的代码为这个写的问题是非常非常慢,问题是关于速度没有风格。

你写它不断变大。 这听起来像是一个日志文件或类似的东西,其中新行追加,但已有的线都没有改变。 如果是这样的话,你可以尝试一种渐进的办法。

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

有计数线及数量行分隔之间的差。 一些常见的问题需要注意的,如果得到一个确切的行数是很重要的:

  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()来看到整个文件作为一个巨大的线。)通过读取数据块到一个固定大小的缓冲区,并使用状态机,你可以把它防弹。

在接受答案的代码遭受大多数的陷阱。 使它正确之前,你让它快。

因为你的算法,它不慢,这是因为缓慢的IO操作是缓慢的。 我想你使用的是简单的O(n)的算法,只是去在顺序文件。 在这种情况下没有更快的算法,可以优化程序。

不过,我说有没有更快的算法,但有一个更快的机制,所谓的“内存映射文件”,也有一些缺点的映射文件,它可能不是appropiate适合你的情况下,所以你必须要了解它并找出自己。

内存映射文件一定不会让您更好地实现一个算法,然后为O(n),但它可能会减少IO访问时间。

你只能得到一个明确的答案通过扫描整个文件找换行字符。 有周围没有办法。

然而,有一对夫妇的,你可能要考虑的可能性。

1 /如果你使用一个简单的循环,读一个字符时检查换行,不需要。 即使在I / O可以被缓冲,函数调用本身是昂贵的,时间方面。

更好的选择是要读取的文件(比如说500万)的大块入内存与单个I / O操作,然后再处理这一点。 你可能并不需要太担心特殊的汇编指令,因为C运行时库总要被优化-一个简单的strchr()应该这样做。

2 /如果你说的总路线长度为40-50个字符,你并不需要一个确切的行数,只要抓住了文件的大小,然后除以45(或者平均您认为使用)。

3 /如果这有点像一个日志文件,你不必保存在一个文件中(可能需要返工对系统的其他部分),可以考虑定期拆分文件。

例如,当它到达500万,移动(例如x.log以标有日期的文件名 ​​(如x_20090101_1022.log并计算出有多少行有在该点(将其存储在x_20090101_1022.count然后启动新x.log的日志文件。日志文件特性意味着创建永远都不会改变这一过时的部分,所以你将永远不会有重新计算的行数。

要处理日志“文件”,你只是cat x_*.log通过一些工艺管道,而不是cat x.log 要获得“文件”的行数,做一个wc -l对当前x.log(相对较快),并把它添加到所有值的总和,在x_*.count文件。

请记住,所有fstreams缓冲。 因此,他们出现的效果做实际读取的块,所以你不必重新创建此功能。 因此,所有你需要做的是扫描缓冲区。 不要使用函数getline()虽然,因为这将迫使你大小的字符串。 所以,我只想使用STL的std ::计数和流迭代​​器。

#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.
}

这需要时间的事情是装载超过40 MB的内存。 要做到这一点,最快的方法是要么memorymap它,或装入一个进入一个大的缓冲区。 一旦你拥有了它在内存中,这种或那种方式,一个循环遍历查找的数据\n人物几乎是瞬间的,不管它是如何实现的。

因此,其实,最重要的技巧就是将文件加载到内存中尽可能快。 而要做到这一点的最快方法是做它作为一个单一的操作。

否则,大量的招数可能存在加快算法。 如果行只加了,从来没有修改或删除,如果你多次读取文件,你可以缓存线之前看完了,接下来的时间,你必须要读取的文件,只能读取新添加的行。

或者你可以保持显示已知的'\ n'字符的位置,一个单独的索引文件,因此该文件的那些部分可以跳过。

读取大量的数据从硬盘缓慢。 有周围没有办法。

分类:C# 时间:2015-03-15 人气:0
本文关键词: C#,线数
分享到:

相关文章

Copyright (C) 55228885.com, All Rights Reserved.

55228885 版权所有 京ICP备15002868号

processed in 0.840 (s). 10 q(s)