Разделение строки в C ++ занимает все больше времени, в то время как строки примерно одинаковы по длине. - PullRequest
Новая
       17

Разделение строки в C ++ занимает все больше времени, в то время как строки примерно одинаковы по длине.

3 голосов
/ 11 октября 2019

Для моего проекта мне нужно прочитать и обработать большой файл, содержащий энергию сейсмических приемников. Для универсальности, он должен уметь обрабатывать файлы .dat и .segy. Моя проблема с файлами .dat. Моя текущая реализация разбивает строку на символ '\t', помещает совпадение в подстроку и переводит значение в виде числа с плавающей точкой в ​​std::vector<float>. Подстрока и табуляция затем удаляются из строки, и выполняется поиск следующего значения. См. Ниже: 

std::vector<float> parseLine(std::string& number, std::ifstream& file)
{
    getline(file, number); // read the number
    std::vector<float> datalist = selectData(number);

    //for (auto y : datalist) std::cout << y << " ";
    //std::cout << std::endl;
    return datalist;

}


std::vector<float> selectData(std::string& line)
{
    std::vector<float> returnVec;
    //auto parsing_start = std::chrono::high_resolution_clock::now();

    // The question is about this part
    while (true)
    {
        int index = line.find_first_of("\t");
        std::string match = line.substr(0, index);
        if (!line.empty()) {
            returnVec.push_back(std::stof(match));
            line.erase(0, match.length());
        }
        if (line[0] == '\t') line.erase(0,1);
        if (line.empty()) {
            //std::cout << "line is empty" << std::endl; 
            break;
        }

    }   
    return returnVec;
}

Каждую сотую строку я печатаю время, прошедшее с предыдущего интервала в 100 строк. Это говорит мне о том, что программе нужны только 1,3 секунды для первых 100 строк, но эта цифра постоянно увеличивается до более 40 секунд для последних 100 строк (см. Рисунок ниже). Учитывая, что в моем файле содержится 6000 строк из примерно 4000 точек данных, просто чтение файла занимает слишком много времени (около 38 минут, когда я отсчитывал время). Все линии похожи по длине и составу, и я не могу понять, почему это время так сильно увеличивается. Строки выглядят следующим образом (первые 2 столбца - это координаты): 

400 1   200.0   205.1   80.1    44.5
400 2   250.0   209.1   70.1    40.0

, но затем, конечно, 4000 столбцов вместо 6.

Вот основная функция, а также способ измерениявремя и #include s: 

#include <stdio.h>
#include <fstream>
#include <string>
#include <iostream>
#define _SILENCE_EXPERIMENTAL_FILESYSTEM_DEPRECATION_WARNING
#include <experimental/filesystem>
#include <regex>
#include <iterator>
#include <chrono>
#include <Eigen/Dense>
#include "readSeis.h"

MatrixXf extractSeismics(std::string file)
{
    MatrixXf M;

    auto start = std::chrono::high_resolution_clock::now();
    auto interstart = std::chrono::high_resolution_clock::now();
    checkExistence(file);
    std::ifstream myfile(file);
    if (!myfile)
    {
        std::cout << "Could not open file " << file << std::endl;
        exit(1);
    }
    int skipCols = 2; // I don't need the coordinates now
    size_t linecount = 0;
    size_t colcount = 0;
    while (!myfile.eof()) // while not at End Of File (eof)
    {
        std::string number;
        std::vector<float> data = parseLine(number, myfile);
        if (linecount == 0)  colcount = data.size() - skipCols;
        //auto resize_start = std::chrono::high_resolution_clock::now();
        M.conservativeResize(linecount + 1, colcount); // preserves old values :)
        //printElapsedTime(resize_start);
        for (int i = skipCols; i < data.size(); i++)
        {
            M(linecount, i - skipCols) = data[i];

        }
        linecount++;
        // Measure interval time
        if (linecount % 100 == 0)
        {
            std::cout << "Parsing line " << linecount << ", ";
            printElapsedTime(interstart);
            interstart = std::chrono::high_resolution_clock::now();
        }
    }
    myfile.close();
    printElapsedTime(start);
    return M;

}

В качестве примечания я также попытался проанализировать строку с регулярным выражением, и это привело к постоянному времени 300 мс для каждой строки (давая 30 мин. для этого файла). Метод разделения намного быстрее в начале (12 мс на строку), но намного медленнее в конце (440 мс на строку). Время увеличивается линейно.

Time needed to read 100 lines.

Для полноты, вывод здесь: 

testSeis1500_1510_290_832.dat exists, continuing program
Parsing line 100, Execution time : 1204968 Microseconds
Parsing line 200, Execution time : 1971723 Microseconds
Parsing line 300, Execution time : 2727474 Microseconds
Parsing line 400, Execution time : 3640131 Microseconds
Parsing line 500, Execution time : 4392584 Microseconds
Parsing line 600, Execution time : 5150465 Microseconds
Parsing line 700, Execution time : 5944256 Microseconds
Parsing line 800, Execution time : 6680841 Microseconds
Parsing line 900, Execution time : 7456237 Microseconds
Parsing line 1000, Execution time : 8201579 Microseconds
Parsing line 1100, Execution time : 8999075 Microseconds
Parsing line 1200, Execution time : 9860883 Microseconds
Parsing line 1300, Execution time : 10524525 Microseconds
Parsing line 1400, Execution time : 11286452 Microseconds
Parsing line 1500, Execution time : 12134566 Microseconds
Parsing line 1600, Execution time : 12872876 Microseconds
Parsing line 1700, Execution time : 13815265 Microseconds
Parsing line 1800, Execution time : 14528233 Microseconds
Parsing line 1900, Execution time : 15221609 Microseconds
Parsing line 2000, Execution time : 15989419 Microseconds
Parsing line 2100, Execution time : 16850944 Microseconds
Parsing line 2200, Execution time : 17717721 Microseconds
Parsing line 2300, Execution time : 18318276 Microseconds
Parsing line 2400, Execution time : 19286148 Microseconds
Parsing line 2500, Execution time : 19828358 Microseconds
Parsing line 2600, Execution time : 20678683 Microseconds
Parsing line 2700, Execution time : 21648089 Microseconds
Parsing line 2800, Execution time : 22229266 Microseconds
Parsing line 2900, Execution time : 23398151 Microseconds
Parsing line 3000, Execution time : 23915173 Microseconds
Parsing line 3100, Execution time : 24523879 Microseconds
Parsing line 3200, Execution time : 25547811 Microseconds
Parsing line 3300, Execution time : 26087140 Microseconds
Parsing line 3400, Execution time : 26991734 Microseconds
Parsing line 3500, Execution time : 27795577 Microseconds
Parsing line 3600, Execution time : 28367321 Microseconds
Parsing line 3700, Execution time : 29127089 Microseconds
Parsing line 3800, Execution time : 29998775 Microseconds
Parsing line 3900, Execution time : 30788170 Microseconds
Parsing line 4000, Execution time : 31456488 Microseconds
Parsing line 4100, Execution time : 32458102 Microseconds
Parsing line 4200, Execution time : 33345031 Microseconds
Parsing line 4300, Execution time : 33853183 Microseconds
Parsing line 4400, Execution time : 34676522 Microseconds
Parsing line 4500, Execution time : 35593187 Microseconds
Parsing line 4600, Execution time : 37059032 Microseconds
Parsing line 4700, Execution time : 37118954 Microseconds
Parsing line 4800, Execution time : 37824417 Microseconds
Parsing line 4900, Execution time : 38756924 Microseconds
Parsing line 5000, Execution time : 39446184 Microseconds
Parsing line 5100, Execution time : 40194553 Microseconds
Parsing line 5200, Execution time : 41051359 Microseconds
Parsing line 5300, Execution time : 41498345 Microseconds
Parsing line 5400, Execution time : 42524946 Microseconds
Parsing line 5500, Execution time : 43252436 Microseconds
Parsing line 5600, Execution time : 44145627 Microseconds
Parsing line 5700, Execution time : 45081208 Microseconds
Parsing line 5800, Execution time : 46072319 Microseconds
Parsing line 5900, Execution time : 46603417 Microseconds
Execution time : 1442777428 Microseconds

Может кто-нибудь увидеть, почему это происходит? Это будет высоко ценится. :)

1 Ответ

2 голосов
/ 12 октября 2019

Вот некоторый код для чтения файла примерно так, как вы описали. Он читает строку за раз, анализирует числа с плавающей точкой, пропускает первые N столбцов и помещает остаток в vector<float>. Основная функция сохраняет каждую строку в vector<vector<float>> и (чтобы гарантировать, что остальные не оптимизируются) складывает все прочитанные значения и в конце выводит их на печать. 

#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>
#include <numeric>
#include <fstream>

std::vector<float> selectData(std::string const &line, int skip_count) { 
    std::istringstream buffer(line);

    float ignore;
    for (int i=0; i<skip_count; i++)
        buffer >> ignore;

    return std::vector<float>{std::istream_iterator<float>(buffer), {}};
}

int main(int argc, char **argv) { 
    std::string line;
    float total = 0.0f;

    if (argc != 2) {
        std::cerr << "Usage: accum <infile>\n";
        return EXIT_FAILURE;
    }

    std::vector<std::vector<float>> matrix;

    std::ifstream infile(argv[1]);
    while (std::getline(infile, line)) {
        auto vals = selectData(line, 2);
        matrix.push_back(vals);
        total += std::accumulate(vals.begin(), vals.end(), 0.0f);
    }
    std::cout << "total: " <<total << "\n";
}

На моей машине это читает файл из 6000 строк с 4000 номерами в строке примерно за 22 секунды (но, как говорится, ваш пробег может отличаться - моя машина довольно старая; на более новой машине удвоение этой скорости не будетменя вообще удивить). Это открыто для дальнейшего улучшения, но, по-видимому, достаточно сократить время считывания с 38 минут до 22 секунд (или около того), чтобы дальнейшее улучшение не было приоритетным.

...