如何快速parsingC ++中的空格分隔花车？

我有一个数百万行的文件，每行有3个浮动空格分隔。 读取文件需要很多时间，所以我试图用内存映射文件来读取它们，只是发现问题不在于IO的速度，而在于parsing的速度。

我目前的parsing是采取stream（称为文件），并执行以下操作

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

有人在堆栈溢出推荐使用Boost.Spirit，但我找不到任何简单的教程来解释如何使用它。

我试图find一个简单而有效的方法来parsing看起来像这样的一行：

 "134.32 3545.87 3425" 

我真的很感激一些帮助。 我想使用strtok来分割它，但我不知道如何将string转换为浮动，我不太确定这是最好的方法。

我不介意解决scheme是否会提升。 我不介意这是否是最有效的解决scheme，但我相信有可能将速度提高一倍。

提前致谢。

Answer 1

如果转换是瓶颈（这是很有可能的），你应该开始使用标准中的不同可能性。 从逻辑上讲，人们会期望他们非常接近，但实际上他们并不总是：

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

• 将内存映射数据转换为std::istringstream几乎肯定不是一个好的解决scheme; 你将首先创build一个string，它将复制所有的数据。

• 编写自己的streambuf直接从内存中读取，而不复制（或使用弃用的std::istrstream ）可能是一个解决scheme，但如果问题真的是转换…这仍然使用相同的转换例程。

• 你总是可以尝试fscanf ，或scanf你的内存映射stream。 根据实现，它们可能比各种istream实现更快。

• 比其中任何一个可能更快的是使用strtod 。 不需要为此标记： strtod跳过前导空格（包括'\n' ），并有一个out参数，它将第一个字符的地址不读取。 结束条件有点棘手，你的循环可能看起来有点像：

     char * begin;  //设置为指向mmap的数据...
                     //你还必须安排一个'\ 0'
                     //跟踪数据 这可能是
                     //最棘手的问题
     char * end;
     errno = 0;
     double tmp = strtod（begin，＆end）;
     while（errno == 0 && end！= begin）{
         //用tmp做任何事
         begin = end;
         tmp = strtod（开始，结束）;
     }

如果这些都不够快，你将不得不考虑实际的数据。 它可能有一些额外的约束，这意味着你可以写一个转换程序比更一般的更快; 例如strtod必须处理固定的和科学的，并且即使有17位有效数字也必须是100％准确的。 它也必须是地区特定的。 所有这些都增加了复杂性，这意味着要添加代码来执行。 但要小心：即使对于一组有限的input，编写一个高效和正确的转换例程也是非常重要的。 你真的必须知道你在做什么。

编辑：

出于好奇，我已经做了一些testing。 除了前面提到的解决scheme之外，我还写了一个简单的自定义转换器，它只处理固定点（不科学），小数点后最多五位数，小数点前的数值必须符合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; } 

（如果你真的使用了这个，你应该添加一些error handling，这只是为了实验的目的而快速打开，阅读我生成的testing文件，而不是其他的东西。

界面与strtod完全相同，以简化编码。

我在两个环境中运行基准testing（在不同的机器上，所以任何时候的绝对值都是不相关的）。 我得到了以下结果：

在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) 。

最显着的是Windows下fstream和fscan之间的巨大差异（以及fscan和strtod之间相对较小的差异）。 第二件事是简单的自定义转换函数在两个平台上获得多less。 必要的error handling会使其稍微减慢一点，但差异仍然很大。 我预计会有一些改进，因为它不能处理标准转换例程（比如科学格式，非常非常小的数字，Inf和NaN，i18n等等）的许多事情，但不是那么多。

Answer 2

UPDATE

由于Spirit X3可用于testing，我已经更新了基准。 同时，我使用Nonius来获得统计上合理的基准。

以下所有图表都可在线交互使用

基准CMake项目+ testdata使用在github上： https ： //github.com/sehe/bench_float_parsing

概要：

灵parsing器是最快的。 如果你可以使用C ++ 14考虑实验版本Spirit X3：

以上是使用内存映射文件的措施。 使用IOstream，它会比较慢，

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

---

以下是老旧答案中的部分内容

---

我实施了Spirit版本，并与其他build议的答案进行了比较。

这是我的结果，所有的testing运行在相同的input体（ input.txt 515Mb）。 请参阅下面的确切规格。

^{（以秒为单位的挂钟时间，2次运行的平均时间）}

令我惊讶的是，Boost Spirit变成了最快，最优雅的一种：

• 处理/报告错误
• 支持+/- Inf和NaN以及variables空格
• 没有任何问题检测input的结束（而不是其他的mmap答案）

• 看起来不错：

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

请注意， boost::spirit::istreambuf_iterator无法形容得慢得多（15s +）。 我希望这有帮助！

基准详细信息

所有的parsing完成到struct float3 { float x,y,z; } struct float3 { float x,y,z; } 。

使用生成input文件

 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-generic＃49 -Ubuntu SMP x86_64
• 英特尔（R）酷睿TM i7-3770K CPU @ 3.50GHz
• 32GiB RAM

完整的代码

旧的基准testing的完整代码是在这篇文章的编辑历史 ，最新的版本是在github上

Answer 3

在开始之前，请validation这是应用程序的缓慢部分，并获得一个testing工具，以便您可以测量改进。

在我看来， 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; } 

Answer 4

我会看看这个相关的post使用ifstream来读取浮动或如何在C ++中标记string，特别是与C ++string工具包库相关的post。 我已经使用了C strtok，C ++stream，Boost标记器以及其中最好的方便和使用的是C ++ String Toolkit Library。

Answer 5

一个基本的解决scheme就是在问题上抛出更多的内核，产生多个线程。 如果瓶颈只是CPU，则可以通过产生两个线程（在多核CPU上）将运行时间减半，

一些其他的提示：

• 尽量避免从库，如提升和/或标准parsing函数。 他们臃肿的错误检查条件和大部分的处理时间都花在做这些检查。 只需要几次转换，它们都很好，但在处理数百万个值时却惨不忍睹。 如果您已经知道您的数据格式良好，则可以编写（或查找）一个自定义优化的C函数，该函数只进行数据转换

• 使用一个大的内存缓冲区（比方说10兆字节），其中你加载文件的块，并在那里做转换

• 除法：将问题分解为更简单的问题：对文件进行预处理，使其成为单行单浮点，将每行按“。”分隔。 字符和转换整数而不是浮点数，然后合并两个整数来创build浮点数

Answer 6

我相信string处理中最重要的规则是“一次只读一个字符”。 我认为，这总是更简单，更快，更可靠。

我做了一个简单的基准程序来展示它是多么的简单。 我的testing说这个代码运行速度比strtod版本快40％。

 #include <iostream> #include <sstream> #include <iomanip> #include <stdlib.h> #include <math.h> #include <time.h> #include <sys/time.h> using namespace std; string test_generate(size_t n) { srand((unsigned)time(0)); double sum = 0.0; ostringstream os; os << std::fixed; for (size_t i=0; i<n; ++i) { unsigned u = rand(); int w = 0; if (u > UINT_MAX/2) w = - (u - UINT_MAX/2); else w = + (u - UINT_MAX/2); double f = w / 1000.0; sum += f; os << f; os << " "; } printf("generated %f\n", sum); return os.str(); } void read_float_ss(const string& in) { double sum = 0.0; const char* begin = in.c_str(); char* end = NULL; errno = 0; double f = strtod( begin, &end ); sum += f; while ( errno == 0 && end != begin ) { begin = end; f = strtod( begin, &end ); sum += f; } printf("scanned %f\n", sum); } double scan_float(const char* str, size_t& off, size_t len) { static const double bases[13] = { 0.0, 10.0, 100.0, 1000.0, 10000.0, 100000.0, 1000000.0, 10000000.0, 100000000.0, 1000000000.0, 10000000000.0, 100000000000.0, 1000000000000.0, }; bool begin = false; bool fail = false; bool minus = false; int pfrac = 0; double dec = 0.0; double frac = 0.0; for (; !fail && off<len; ++off) { char c = str[off]; if (c == '+') { if (!begin) begin = true; else fail = true; } else if (c == '-') { if (!begin) begin = true; else fail = true; minus = true; } else if (c == '.') { if (!begin) begin = true; else if (pfrac) fail = true; pfrac = 1; } else if (c >= '0' && c <= '9') { if (!begin) begin = true; if (pfrac == 0) { dec *= 10; dec += c - '0'; } else if (pfrac < 13) { frac += (c - '0') / bases[pfrac]; ++pfrac; } } else { break; } } if (!fail) { double f = dec + frac; if (minus) f = -f; return f; } return 0.0; } void read_float_direct(const string& in) { double sum = 0.0; size_t len = in.length(); const char* str = in.c_str(); for (size_t i=0; i<len; ++i) { double f = scan_float(str, i, len); sum += f; } printf("scanned %f\n", sum); } int main() { const int n = 1000000; printf("count = %d\n", n); string in = test_generate(n); { struct timeval t1; gettimeofday(&t1, 0); printf("scan start\n"); read_float_ss(in); struct timeval t2; gettimeofday(&t2, 0); double elapsed = (t2.tv_sec - t1.tv_sec) * 1000000.0; elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0; printf("elapsed %.2fms\n", elapsed); } { struct timeval t1; gettimeofday(&t1, 0); printf("scan start\n"); read_float_direct(in); struct timeval t2; gettimeofday(&t2, 0); double elapsed = (t2.tv_sec - t1.tv_sec) * 1000000.0; elapsed += (t2.tv_usec - t1.tv_usec) / 1000.0; printf("elapsed %.2fms\n", elapsed); } return 0; } 

---

以下是i7 Mac Book Pro的控制台输出（在XCode 4.6中编译）。

 count = 1000000 generated -1073202156466.638184 scan start scanned -1073202156466.638184 elapsed 83.34ms scan start scanned -1073202156466.638184 elapsed 53.50ms 

Answer 7

使用C将是最快的解决scheme。 使用strtok拆分为令牌，然后转换为strtof浮动。 或者如果你知道确切的格式使用fscanf 。