37

我有一个包含数百万行的文件,每行有 3 个浮点数,以空格分隔。读取文件需要很多时间,所以我尝试使用内存映射文件读取它们,结果发现问题不在于 IO 的速度,而在于解析的速度。

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

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

Stack Overflow 中有人推荐使用 Boost.Spirit,但我找不到任何简单的教程来解释如何使用它。

我正在尝试找到一种简单有效的方法来解析如下所示的行:

"134.32 3545.87 3425"

我将非常感谢一些帮助。我想用 strtok 来拆分它,但我不知道如何将字符串转换为浮点数,我不太确定这是最好的方法。

我不介意解决方案是否是 Boost。我不介意它是否不是有史以来最有效的解决方案,但我确信它可以将速度提高一倍。

提前致谢。

4

8 回答 8

45

更新

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

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

使用的基准 CMake 项目 + 测试数据在 github 上:https ://github.com/sehe/bench_float_parsing

在此处输入图像描述

概括:

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

在此处输入图像描述

以上是使用内存映射文件的措施。使用 IOstreams,它会更慢,

在此处输入图像描述

但不如scanf使用 C/POSIXFILE*函数调用慢:

在此处输入图像描述


以下是旧答案的部分内容


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

这是我的结果,所有测试都在相同的输入主体(515Mb of 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这慢得多(15s+)。我希望这有帮助!

基准详情

所有解析完成到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-generic #49-Ubuntu SMP x86_64
  • Intel(R) Core(TM) i7-3770K CPU @ 3.50GHz
  • 32GiB 内存

完整代码

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

于 2013-07-05T00:49:59.243 回答
18

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

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

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

  • 编写自己的streambuf直接从内存中读取,而不复制(或使用不推荐使用的std::istrstream)可能是一个解决方案,尽管如果问题真的是转换......这仍然使用相同的转换例程。

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

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

    char* 开始;// 设置为指向 mmap'ed 数据...
                    // 你还必须安排一个 '\0'
                    // 跟随数据。这大概是
                    // 最困难的问题。
    字符*结束;
    错误号 = 0;
    双 tmp = strtod(开始,&结束);
    while ( errno == 0 && end != begin ) {
        // 用 tmp 做任何事情...
        开始=结束;
        tmp = strtod(开始,&结束);
    }

如果这些都不够快,您将不得不考虑实际数据。它可能有某种额外的约束,这意味着您可能会编写一个比更通用的转换例程更快的转换例程;例如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 行,每行在 range 中有 3 个随机生成的浮点[0...10000)

fstream最引人注目的是 Windows和Windows 下的巨大差异 (以及和fscan之间的相对较小的差异)。第二件事是简单的自定义转换功能在两个平台上获得了多少收益。必要的错误处理会稍微减慢它的速度,但差异仍然很大。我预计会有一些改进,因为它不能处理标准转换例程所做的很多事情(比如科学格式、非常非常小的数字、Inf 和 NaN、i18n 等),但不是那么多。fscanstrtod

于 2013-07-04T08:45:37.390 回答
13

在开始之前,请确认这是您的应用程序的缓慢部分,并围绕它获取测试工具,以便您可以衡量改进。

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;
}
于 2013-07-04T08:12:38.917 回答
2

我会查看这篇相关文章Using ifstream to read floatsHow do I tokenize a string in C++特别是与 C++ String Toolkit Library 相关的文章。我使用过 C strtok、C++ 流、Boost 分词器,其中最好的是 C++ String Toolkit Library。

于 2016-07-07T19:49:35.247 回答
1

编辑:对于那些担心 crack_atof 没有以任何方式验证的人,请参阅底部关于Ryu的评论。

这是一个更完整的(虽然不是任何标准的“官方”)高速字符串到双重例程,因为好的 C++17from_chars()解决方案仅适用于 MSVC(不是 clang 或 gcc)。

见面crack_atof

https://gist.github.com/oschonrock/a410d4bec6ec1ccc5a3009f0907b3d15

不是我的工作,我只是稍微重构了一下。并更改了签名。代码很容易理解,很明显为什么它很快。而且它非常非常快,请在此处查看基准:

https://www.codeproject.com/Articles/1130262/Cplusplus-string-view-Conversion-to-Integral-Types

我用 11,000,000 行 3 个浮点数运行它(csv 中的 15 位精度,这很重要!)。在我老旧的第二代酷睿 i7 2600 上,它的运行时间为 1.327 秒。Kubuntu 19.04 上的编译器 clang V8.0.0 -O2。

完整代码如下。我正在使用 mmap,因为 str->float 不再是唯一的瓶颈,这要归功于crack_atof。我已经将 mmap 的东西包装到一个类中,以确保地图的 RAII 版本。


#include <iomanip>
#include <iostream>

// for mmap:
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>

class MemoryMappedFile {
public:
  MemoryMappedFile(const char* filename) {
    int fd = open(filename, O_RDONLY);
    if (fd == -1) throw std::logic_error("MemoryMappedFile: couldn't open file.");

    // obtain file size
    struct stat sb;
    if (fstat(fd, &sb) == -1) throw std::logic_error("MemoryMappedFile: cannot stat file size");
    m_filesize = sb.st_size;

    m_map = static_cast<const char*>(mmap(NULL, m_filesize, PROT_READ, MAP_PRIVATE, fd, 0u));
    if (m_map == MAP_FAILED) throw std::logic_error("MemoryMappedFile: cannot map file");
  }

  ~MemoryMappedFile() {
    if (munmap(static_cast<void*>(const_cast<char*>(m_map)), m_filesize) == -1)
      std::cerr << "Warnng: MemoryMappedFile: error in destructor during `munmap()`\n";
  }

  const char* start() const { return m_map; }
  const char* end() const { return m_map + m_filesize; }

private:
  size_t m_filesize = 0;
  const char* m_map = nullptr;
};

// high speed str -> double parser
double pow10(int n) {
  double ret = 1.0;
  double r   = 10.0;
  if (n < 0) {
    n = -n;
    r = 0.1;
  }

  while (n) {
    if (n & 1) {
      ret *= r;
    }
    r *= r;
    n >>= 1;
  }
  return ret;
}

double crack_atof(const char* start, const char* const end) {
  if (!start || !end || end <= start) {
    return 0;
  }

  int sign         = 1;
  double int_part  = 0.0;
  double frac_part = 0.0;
  bool has_frac    = false;
  bool has_exp     = false;

  // +/- sign
  if (*start == '-') {
    ++start;
    sign = -1;
  } else if (*start == '+') {
    ++start;
  }

  while (start != end) {
    if (*start >= '0' && *start <= '9') {
      int_part = int_part * 10 + (*start - '0');
    } else if (*start == '.') {
      has_frac = true;
      ++start;
      break;
    } else if (*start == 'e') {
      has_exp = true;
      ++start;
      break;
    } else {
      return sign * int_part;
    }
    ++start;
  }

  if (has_frac) {
    double frac_exp = 0.1;

    while (start != end) {
      if (*start >= '0' && *start <= '9') {
        frac_part += frac_exp * (*start - '0');
        frac_exp *= 0.1;
      } else if (*start == 'e') {
        has_exp = true;
        ++start;
        break;
      } else {
        return sign * (int_part + frac_part);
      }
      ++start;
    }
  }

  // parsing exponent part
  double exp_part = 1.0;
  if (start != end && has_exp) {
    int exp_sign = 1;
    if (*start == '-') {
      exp_sign = -1;
      ++start;
    } else if (*start == '+') {
      ++start;
    }

    int e = 0;
    while (start != end && *start >= '0' && *start <= '9') {
      e = e * 10 + *start - '0';
      ++start;
    }

    exp_part = pow10(exp_sign * e);
  }

  return sign * (int_part + frac_part) * exp_part;
}

int main() {
  MemoryMappedFile map  = MemoryMappedFile("FloatDataset.csv");
  const char* curr      = map.start();
  const char* start     = map.start();
  const char* const end = map.end();

  uintmax_t lines_n = 0;
  int cnt              = 0;
  double sum           = 0.0;
  while (curr && curr != end) {
    if (*curr == ',' || *curr == '\n') {
      // std::string fieldstr(start, curr);
      // double field = std::stod(fieldstr);
      // m_numLines = 11000000 cnt=33000000 sum=16498294753551.9
      // real 5.998s

      double field = crack_atof(start, curr);
      // m_numLines = 11000000 cnt=33000000 sum=16498294753551.9
      // real 1.327s

      sum += field;
      ++cnt;
      if (*curr == '\n') lines_n++;
      curr++;
      start = curr;
    } else {
      ++curr;
    }
  }

  std::cout << std::setprecision(15) << "m_numLines = " << lines_n << " cnt=" << cnt
            << " sum=" << sum << "\n";
}

代码也在 github gist 上:

https://gist.github.com/oschonrock/67fc870ba067ebf0f369897a9d52c2dd

于 2019-11-23T23:14:01.683 回答
0

使用 C 将是最快的解决方案。使用拆分为标记strtok,然后使用 . 转换为浮动strtof。或者,如果您知道确切的格式,请使用fscanf.

于 2013-07-04T08:13:26.477 回答
0

一个基本的解决方案是在问题上投入更多的核心,产生多个线程。如果瓶颈只是 CPU,您可以通过生成两个线程(在多核 CPU 上)将运行时间减半

其他一些提示:

  • 尽量避免从库中解析函数,例如 boost 和/或 std。它们因错误检查条件而臃肿,并且大部分处理时间都花在了这些检查上。只需进行几次转换,它们就可以了,但在处理数百万个值时却惨遭失败。如果您已经知道您的数据格式正确,您可以编写(或查找)一个自定义优化的 C 函数,它只进行数据转换

  • 使用一个大的内存缓冲区(比如说 10 MB),您可以在其中加载文件块并在那里进行转换

  • divide et impera:将您的问题拆分为更简单的问题:预处理您的文件,使其成为单行单浮点数,用“。”分隔每一行 字符并转换整数而不是浮点数,然后合并两个整数以创建浮点数

于 2013-07-04T08:16:40.867 回答
0

我相信字符串处理中最重要的一条规则是“一次只读取一次,一次一个字符”。我认为它总是更简单、更快、更可靠。

我制作了简单的基准测试程序来展示它是多么简单。我的测试表明此代码的运行速度比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
于 2013-07-04T12:47:44.460 回答