Самое ужасное в этом коде - это не разбор строк;это изменение размера целевого массива для каждой новой прочитанной точки.Чем больше вы читаете, тем хуже становится.В конечном итоге это становится операцией копирования порядка O (n ^ 2).
Чтобы дать вам представление о том, насколько это плохо, рассмотрим базовое суммирование n натуральных чисел , потому что вот сколько конструкций объектов, разрушений и копий вы делаете:
n (n + 1) / 2 = (20000 * 20001) / 2 = 200010000 объектов, созданных, скопированных и уничтоженных
Итак,Разбор строк не проблема.Анализируемые 20000 строк текста затмеваются более чем 200 миллионами конструкций, разрушений и копий объектов.
Вам не нужно ничего этого делать.Используйте соответствующий контейнер, такой как std::vector, и приблизьте начальный резерв на основе размера файла.Затем просто сгенерируйте точки и переместите их в контейнер.
Пример, который делает это, включая создание тестового файла из 100000 точек (в 5 раз больше, чем вы спрашиваете), показан ниже:
Код
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
struct Point
{
std::string name;
float x;
float y;
};
std::vector<Point> readFile(std::string const& fname)
{
std::vector<Point> res;
std::ifstream inp(fname);
if (inp.is_open())
{
// gather file size for a rough approximation of reserve
inp.seekg(0, std::ios::end);
auto flen = inp.tellg();
inp.seekg(0, std::ios::beg);
res.reserve(flen/40);
std::string line;
while (std::getline(inp, line))
{
auto pos = line.find("POINT");
if (pos != std::string::npos)
{
std::istringstream iss(line.substr(pos+5));
Point pt;
if (iss >> pt.name >> pt.x >> pt.y)
res.emplace_back(std::move(pt));
}
}
}
return res;
}
int main()
{
using namespace std::chrono;
std::mt19937 prng(std::random_device{}());
std::uniform_real_distribution<float> dist(-100.0, 100.0);
// generate test data
std::ofstream outf("testpoints.txt");
for (int i=1; i<=100000; ++i)
outf << "POINT \"" << i << "\" " << dist(prng) << ' ' << dist(prng) << '\n';
outf.close();
// rough benchmark
auto tp0 = steady_clock::now();
auto v = readFile("testpoints.txt");
auto tp1 = steady_clock::now();
std::cout << "Read " << v.size() << " points in ";
std::cout << duration_cast<milliseconds>(tp1-tp0).count() << "ms\n";
v.clear();
}
Вывод
Работая на двухъядерном ноутбуке i7 MacBook Air 2015 года, сборка в режиме выпуска производитследующий результат:
Read 100000 points in 164ms
A Возможно, более подходящий контейнер: std::deque
В конце концов, вам действительно нужен контейнерэто позволяет быстро вставлять в конец, минимизируя (или исключая) копирование элемента при изменении размера.Конечно, как показано в коде выше, установка резерва против std::vector является одним из способов сделать это.Другим вариантом является использование контейнера, который на самом деле специализируется на конечных вставках, но в то же время по большей части дружественным к кешу (не идеален, как std::vector, но, безусловно, лучше, чем что-то вроде связанных списков, которые отлично подходят для вставок, но ужасен для перечисления).
Именно это и сделает std::deque.Приведенный выше код, измененный для std::deque, позволяет исключить резервное предположение и просто начать отбрасывать узлы в конце последовательности, что автоматически добавит больше страниц по мере роста последовательности:
Код
#include <iostream>
#include <fstream>
#include <sstream>
#include <deque>
#include <string>
#include <random>
#include <chrono>
struct Point
{
std::string name;
float x;
float y;
};
std::deque<Point> readFile(std::string const& fname)
{
std::deque<Point> res;
std::ifstream inp(fname);
if (inp.is_open())
{
std::string line;
while (std::getline(inp, line))
{
auto pos = line.find("POINT");
if (pos != std::string::npos)
{
std::istringstream iss(line.substr(pos+5));
Point pt;
if (iss >> pt.name >> pt.x >> pt.y)
res.emplace_back(std::move(pt));
}
}
}
return res;
}
int main()
{
using namespace std::chrono;
std::mt19937 prng(std::random_device{}());
std::uniform_real_distribution<float> dist(-100.0, 100.0);
// generate test data
std::ofstream outf("testpoints.txt");
for (int i=1; i<=100000; ++i)
outf << "POINT \"" << i << "\" " << dist(prng) << ' ' << dist(prng) << '\n';
outf.close();
// rough benchmark
auto tp0 = steady_clock::now();
auto v = readFile("testpoints.txt");
auto tp1 = steady_clock::now();
std::cout << "Read " << v.size() << " points in ";
std::cout << duration_cast<milliseconds>(tp1-tp0).count() << "ms\n";
v.clear();
}
Выход
Read 100000 points in 160ms
Если вам требуется последовательность смежных , подход std::vectorпуть.Если вам просто нужен произвольный доступ к элементам и вам нужны быстрые вставки конца, лучше подойдет std::deque.Подумайте об этом и выберите наиболее подходящий для вас.
Резюме
Избавьтесь от этого ужасного алгоритма расширения.Это больной вопрос в вашем коде.Замените его алгоритмом геометрического изменения размера и начните с грубого приближения числа элементов, которые вам понадобятся с самого начала.Или используйте контейнер, подходящий для оптимальных вставок.В любом случае, это лучше, чем у вас сейчас.