如何快速解析C++中以空格分隔的浮点数？

Question

我有一个包含数百万行的文件,每行有3个以空格分隔的浮点数.读取文件需要花费大量时间,因此我尝试使用内存映射文件读取它们,但发现问题不在于IO的速度,而在于解析速度.

我当前的解析是获取流(称为文件)并执行以下操作

float x,y,z;
file >> x >> y >> z;

Stack Overflow中的某些人建议使用Boost.Spirit,但我找不到任何简单的教程来解释如何使用它.

我正在尝试找到一种简单有效的方法来解析看起来像这样的行:

"134.32 3545.87 3425"

我真的很感激一些帮助.我想用strtok来分割它,但我不知道如何将字符串转换为浮点数,我不太确定它是最好的方法.

我不介意解决方案是否会提升.我不介意它是不是有史以来最有效的解决方案,但我确信它可以加倍速度.

提前致谢.

Answer 1

UPDATE

由于Spirit X3可用于测试,我已经更新了基准测试.与此同时,我使用Nonius来获得统计上合理的基准.

以下所有图表均可在线互动

Benchmark CMake项目+使用的testdata在github上:https://github.com/sehe/bench_float_parsing

摘要:

精神解析器是最快的.如果您可以使用C++ 14,请考虑实验版Spirit X3:

以上是使用内存映射文件的措施.使用IOstreams,它会越来越慢,

但不像scanf使用C/POSIX FILE*函数调用那么慢:

以下是OLD答案中的部分内容

我实施了Spirit版本,并与其他建议的答案进行了比较.

这是我的结果,所有测试都在同一个输入体上运行(515Mb input.txt).请参阅下面的确切规格.

^{(挂钟时间以秒为单位,平均2次以上)}

令我惊讶的是,Boost Spirit最快,最优雅:

• 处理/报告错误
• 支持+/- Inf和NaN以及变量空格
• 检测到输入结束没有问题(与其他mmap答案相反)

• 看起来不错:

  bool ok = phrase_parse(f,l,               // source iterators
       (double_ > double_ > double_) % eol, // grammar
       blank,                               // skipper
       data);                               // output attribute
  

请注意,这boost::spirit::istreambuf_iterator是不可言喻的慢得多(15秒+).我希望这有帮助!

基准细节

所有解析都完成vector了struct float3 { float x,y,z; }.

使用生成输入文件

od -f -A none --width=12 /dev/urandom | head -n 11000000

这导致包含数据的515Mb文件

     -2627.0056   -1.967235e-12  -2.2784738e+33
  -1.0664798e-27  -4.6421956e-23   -6.917859e+20
  -1.1080849e+36   2.8909405e-33   1.7888695e-12
  -7.1663235e+33  -1.0840628e+36   1.5343362e-12
  -3.1773715e-17  -6.3655537e-22   -8.797282e+31
    9.781095e+19   1.7378472e-37        63825084
  -1.2139188e+09  -5.2464635e-05  -2.1235992e-38
   3.0109424e+08   5.3939846e+30  -6.6146894e-20

使用以下命令编译程序:

g++ -std=c++0x -g -O3 -isystem -march=native test.cpp -o test -lboost_filesystem -lboost_iostreams

使用测量挂钟时间

time ./test < input.txt 

环境:

• Linux桌面4.2.0-42-通用#49-Ubuntu SMP x86_64
• Intel(R)Core(TM)i7-3770K CPU @ 3.50GHz
• 32GiB RAM

完整代码

旧帖的完整代码在本文的编辑历史中,最新版本在github上

Answer 2

如果转换是瓶颈(这很可能),您应该首先使用标准中的不同可能性.从逻辑上讲,人们会期望它们非常接近,但实际上,它们并不总是:

• 你已经确定std::ifstream太慢了.

• 将内存映射数据转换为a std::istringstream 几乎肯定不是一个好的解决方案; 您首先必须创建一个字符串,它将复制所有数据.

• 编写自己streambuf的内容直接从内存中读取,无需复制(或使用已弃用的std::istrstream)可能是一种解决方案,但如果问题确实是转换......这仍然使用相同的转换例程.

• 您可以随时尝试fscanf,或scanf在您的内存映射流上.根据实现,它们可能比各种istream实现更快.

• 可能比任何这些都要快strtod.无需为此进行标记:strtod跳过前导空格(包括'\n'),并且有一个out参数,用于放置未读取的第一个字符的地址.结束条件有点棘手,你的循环可能看起来有点像:

    char* begin;    //  Set to point to the mmap'ed data...
                    //  You'll also have to arrange for a '\0'
                    //  to follow the data.  This is probably
                    //  the most difficult issue.
    char* end;
    errno = 0;
    double tmp = strtod( begin, &end );
    while ( errno == 0 && end != begin ) {
        //  do whatever with tmp...
        begin = end;
        tmp = strtod( begin, &end );
    }

如果这些都不够快,您将不得不考虑实际数据.它可能有一些额外的约束,这意味着你可以编写一个比一般更快的转换例程; 例如strtod,必须处理固定和科学,即使有17位有效数字,它必须100%准确.它还必须是特定于语言环境的.所有这些都增加了复杂性,这意味着需要添加代码来执行.但要注意:编写一个有效且正确的转换例程,即使对于一组有限的输入,也是非常重要的; 你真的必须知道你在做什么.

编辑:

出于好奇,我进行了一些测试.除了前面提到的解决方案之外,我还编写了一个简单的自定义转换器,它只处理固定点(不科学),小数点后最多五位数,小数点前的值必须符合int:

double
convert( char const* source, char const** endPtr )
{
    char* end;
    int left = strtol( source, &end, 10 );
    double results = left;
    if ( *end == '.' ) {
        char* start = end + 1;
        int right = strtol( start, &end, 10 );
        static double const fracMult[] 
            = { 0.0, 0.1, 0.01, 0.001, 0.0001, 0.00001 };
        results += right * fracMult[ end - start ];
    }
    if ( endPtr != nullptr ) {
        *endPtr = end;
    }
    return results;
}

(如果你真的使用它,你肯定应该添加一些错误处理.这只是为了实验目的而迅速被淘汰,读取我生成的测试文件,没有 别的.)

接口正好是strtod简化编码的接口.

我在两个环境中运行基准测试(在不同的机器上,所以任何时候的绝对值都不相关).我得到了以下结果:

在Windows 7下,使用VC 11(/ O2)编译:

Testing Using fstream directly (5 iterations)...
    6.3528e+006 microseconds per iteration
Testing Using fscan directly (5 iterations)...
    685800 microseconds per iteration
Testing Using strtod (5 iterations)...
    597000 microseconds per iteration
Testing Using manual (5 iterations)...
    269600 microseconds per iteration

在Linux 2.6.18下,使用g ++ 4.4.2(-O2,IIRC)编译:

Testing Using fstream directly (5 iterations)...
    784000 microseconds per iteration
Testing Using fscanf directly (5 iterations)...
    526000 microseconds per iteration
Testing Using strtod (5 iterations)...
    382000 microseconds per iteration
Testing Using strtof (5 iterations)...
    360000 microseconds per iteration
Testing Using manual (5 iterations)...
    186000 microseconds per iteration

在所有情况下,我正在读取554000行,每行有3个随机生成的浮点数[0...10000).

最引人注目的是之间的巨大的差异 fstream和fscanWindows下(与之间的差异相对较小fscan和strtod).第二件事是两个平台上简单的自定义转换功能获得了多少.必要的错误处理会使其减慢一点,但差异仍然很大.我期待一些改进,因为它不能处理标准转换例程所做的很多事情(比如科学格式,非常非常小的数字,Inf和NaN,i18n等),但不是这么多.

Answer 3

在开始之前,请确认这是应用程序的慢速部分并获得测试工具,以便您可以衡量改进.

boost::spirit在我看来,这对你来说太过分了.尝试fscanf

FILE* f = fopen("yourfile");
if (NULL == f) {
   printf("Failed to open 'yourfile'");
   return;
}
float x,y,z;
int nItemsRead = fscanf(f,"%f %f %f\n", &x, &y, &z);
if (3 != nItemsRead) {
   printf("Oh dear, items aren't in the right format.\n");
   return;
}