Анализ строки чисел

Question

Мне нужно проанализировать несколько строк в стиле C (около 500 тыс.), Содержащих 4 числа с плавающей запятой, разделенные одним пробелом. Ниже приведен пример одной строки:

«90292 5879 5879 89042,2576»

мне нужно хранить эти числа в двух структур, представляющих две точки. Учитывая, что строка может быть изменена при анализе, и что 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(); 
} 

Я думаю, что стандартные библиотеки оптимизированы для чтения с плавающей точкой, намного лучше, чем вышеприведенный пример и счета для всех отклонения формата с плавающей запятой.

Примечание: в качестве альтернативы вы можете прочитать десятичные знаки и показатели как целые числа, если они есть, а затем построить значение с плавающей точкой со всеми тремя частями.

Answer 2

Вы можете реализовать atof, которые возвращают позицию space. Таким образом, вам нужно пройти каждую строку только один раз.

например.

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: в соответствии с обсуждения, вы ожидаете 0 в этом случае)
• вы создать PointF объекты дважды, чтобы быть в состоянии передать их
  • вы передаете их в качестве ссылки, таким образом, это не тривиальное для человека читающего код вызова, что они находятся вне Титулы.
• вы создали анализатор доступен в C (хотя вы могли бы измерить, если это быстрее или медленнее)

Я хотел бы предложить следующее: (обратите внимание, что std::experimental::optional<> эквивалентно здесь boost::optional<>)

#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.1sec вместо 1.5sec.

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; 
}