数値の文字列を解析する

Question

1つのスペース文字で区切られた4つの浮動小数点数を含むいくつかのCスタイルの文字列（約500k）を解析する必要があります。単一の文字列の例は以下の通りです：

「5879 89042.2576 5879 90292」

私は2つの点を表す2つの構造体でこれらの番号を格納する必要があります。解析中に文字列を変更できることと、99.99％の数字が符号なし整数であることを考慮すると、それを行う最も速い方法は何ですか？続き

は私の現在の実装である：

#include <iostream> 
#include <cassert> 
#include <chrono> 
#include <algorithm> 
#include <vector> 
#include <string> 
using namespace std; 
using namespace chrono; 



struct PointF 
{ 
    float x; 
    float y; 
}; 


void parse_points(char* points, PointF& p1, PointF& p2) 
{ 
    auto start = points; 
    const auto end = start + strlen(points); 

    // p1.x 
    start = std::find(start, end, ' '); 
    assert(start < end); 
    *start = '\0'; 
    p1.x = static_cast<float>(atof(points)); 
    points = start + 1; 

    // p1.y 
    start = std::find(start, end, ' '); 
    assert(start < end); 
    *start = '\0'; 
    p1.y = static_cast<float>(atof(points)); 
    points = start + 1; 

    // p2.x 
    start = std::find(start, end, ' '); 
    assert(start < end); 
    *start = '\0'; 
    p2.x = static_cast<float>(atof(points)); 
    points = start + 1; 

    // p2.y 
    start = std::find(start, end, ' '); 
    assert(start == end); 
    p2.y = static_cast<float>(atof(points)); 
} 



int main() 
{ 
    const auto n = 500000; 
    char points_str[] = "90292 5879 89042.2576 5879"; 
    PointF p1, p2; 

    vector<string> data(n); 

    for (auto& s : data) 
     s.assign(points_str); 

    const auto t0 = system_clock::now(); 

    for (auto i = 0; i < n; i++) 
     parse_points(const_cast<char*>(data[i].c_str()), p1, p2); 

    const auto t1 = system_clock::now(); 
    const auto elapsed = duration_cast<milliseconds>(t1 - t0).count(); 

    cout << "Elapsed: " << elapsed << " ms" << endl; 

    cin.get(); 
    return 0; 
} 

Answer 1

は、浮動小数点値の文字列を指定すると、スペースで区切られた：

const std::string example_input = "90292 5879 89042.2576 5879"; 

あなたは浮動小数点として読んで、高速であるかを確認するプロフィールはずです：

std::istringstream text_stream(example_input); 
std::vector<double> container; 
double value; 
while (text_stream >> value) 
{ 
    container.push_back(value); 
} 

または浮動小数点の兆候がある場合にパフォーマンスヒットを取って、整数として読み：

std::istringstream text_stream(example_input); 
std::vector<double> container; 
double value; 
signed int int_value; 
std::streampos position_before_read = text_stream.tellg(); 
while (text_stream >> int_value) 
{ 
    // check the next character for possible floating point differences. 
    char c; 
    text_stream >> c; 
    switch (c) 
    { 
    case '.': 
    case 'E': case 'e': 
     // Rewind to before the number and read as floating point 
     text_stream.seekg(position_before_read); 
     text_stream >> value; 
     break; 
    default: 
     value = 1.0 * int_value; 
     break; 
    } 
    container.push_back(value); 
    position_before_read = text_stream.tellg(); 
} 

私の推測では、標準ライブラリは、浮動小数点を読むために最適化されていることである、すべてのためにたくさん上記の例よりも良いとアカウント浮動小数点フォーマットの分散。

注：小数点および指数を整数として読み取ることもできます（存在する場合）。次に、3つすべての浮動小数点値を作成することもできます。

Answer 2

spaceの位置を返すatofを実装できます。この方法では、各文字列を1回だけトラバースする必要があります。

例えば、

char *atof(char *point, float &num) { 
    num = 0; 
    bool neg = false, dot = false; 
    float decimal = 0, mul = 0.1; 
    if (*point == '-') { 
    neg = true; 
    point++; 
    } else if (*point == '+') { 
    point++; 
    } 
    while (*point != ' ' && *point) { 
    if (*point == '.') { 
     dot = true; 
    } else { 
     if (dot) { 
     decimal += (*point - '0') * mul; 
     mul *= 0.1; 
     } else { 
     num = num * 10 + *point - '0'; 
     } 
    } 
    point++; 
    } 
    if (dot) { 
    num += decimal; 
    } 
    if (neg) { 
    num = -num; 
    } 
    return point; 
} 

Answer 3

私はコードで複数の問題を参照してください（と、それはあなたが求めてきましたことを、実際に良いことだ）：

• 番号（NBがある場合の取扱いはエラーはありません。議論あたりとしては、あなたはPointFは、このように、それはこれらが出ていることを呼び出し元のコードを読む人のために簡単なことではないですが、あなたが参照として渡す彼らに
  • を渡すことができるように二回オブジェクトを作成します。この場合は0）
  • を期待しますparams。（std::experimental::optional<>がboost::optional<>にここに同等であることに注意してください）
    ：私はこれをお勧めしたい
• 作成したパーサはC言語で利用可能である（それが速いか遅いだ場合は、測定可能性があるとはいえ）

#include <iostream> 
#include <cstring> 
#include <utility> 
#include <experimental/optional> 

struct PointF 
{ 
    float x; 
    float y; 
}; 

std::experimental::optional<std::pair<PointF, PointF>> parse_points(char* pch) 
{ 
    pch = strtok (pch, " "); 
    if (pch != NULL) 
    { 
     float x0 = atof(pch); 
     pch = strtok (NULL, " "); 
     if (pch != NULL) 
     { 
      float y0 = atof(pch); 
      pch = strtok (NULL, " "); 
      if (pch != NULL) 
      { 
       float x1 = atof(pch); 
       pch = strtok (NULL, " "); 
       if (pch != NULL) 
       { 
        float y1 = atof(pch); 
        PointF p0{x0, y0}, p1{x1, y1}; 
        return std::make_pair(p0, p1); 
       } 
      } 
     } 
    } 
    return std::experimental::nullopt; 
} 

int main() { 
    const char str[] ="90292 5879 89042.2576 5879"; 
    char* pch0 = new char[sizeof(str)], *pch = pch0; 
    memcpy(pch0, str, sizeof(str)); 

    std::experimental::optional<std::pair<PointF, PointF>> pOpt(parse_points(pch0)); 
    if(pOpt) 
     std::cout << pOpt->first.x << " " << pOpt->first.y << " " 
        << pOpt->second.x << " " << pOpt->second.y << " " << std::endl; 
    delete pch; 
} 

Answer 4

ここにstrlenを除き、strtok_sを使用した私のバージョンです。 私のマシンでは1.5secの代わりに1.1secが必要です。

void parse_points(char* points, PointF& p1, PointF& p2) 
{ 
    char *next_token1 = nullptr; 

    // p1.x 
    points = strtok_s(points, " ", &next_token1); 
    p1.x = points ? static_cast<float>(atof(points)) : 0.0f; 

    // p1.y 
    points = strtok_s(nullptr, " ", &next_token1); 
    p1.y = points ? static_cast<float>(atof(points)) : 0.0f; 

    // p2.x 
    points = strtok_s(nullptr, " ", &next_token1); 
    p2.x = points ? static_cast<float>(atof(points)) : 0.0f; 

    // p2.y 
    points = strtok_s(nullptr, " ", &next_token1); 
    p2.y = points ? static_cast<float>(atof(points)) : 0.0f; 
} 



int main() 
{ 
    const auto n = 500000; 
    char points_str[] = "90292 5879 89042.2576 5879"; 
    PointF p1, p2; 

    vector<string> data(n); 

    for (auto& s : data) 
     s.assign(points_str); 

    const auto t0 = system_clock::now(); 

    for (auto i = 0; i < n; i++) 
     parse_points(const_cast<char*>(data[i].c_str()), p1, p2); 

    const auto t1 = system_clock::now(); 
    const auto elapsed = duration_cast<milliseconds>(t1 - t0).count(); 

    cout << "Elapsed: " << elapsed << " ms" << endl; 

    //cin.get(); 
    return 0; 
}