我有一个文本文件要读取和处理 20000 行。在文本文件中我想读取点坐标并分配给 DirectX 进行渲染。 Snapshot of Text file

我已经使用 std::ifstream、getline、stringstream 来获取点坐标。构建win32程序后开始运行，读取点坐标并存储到数组中耗时太长。 (5 分钟浏览 20000 行文本文件)。代码如下:

struct PointCoord { std::string PtName; float PtX = 0.0; float PtY = 0.0;}
PointCoord *PointPtr = NULL;
PointCoord pointcoord;

std::ifstream File_read(FileNameTXT);    
while (getline(File_read, TextHandler))
        {
            std::istringstream iss;
            std::string skip;
            if (TextHandler.find("  POINT ") != std::string::npos)
            {
                iss.str(TextHandler);
                std::string TempX, TempY;
                iss >> skip;
                iss >> pointcoord.PtName;                         

                //pointcoord pass value to PointCoord
                iss >> TempX;
                iss >> TempY;

                pointcoord.PtX = std::stof(TempX.c_str());
                pointcoord.PtY = std::stof(TempY.c_str());

                //dynamically store the points coordiantes
                if (PointPtr == NULL)
                {
                    PointPtr = new PointCoord[1];                     

                    //PointCoord pass value to PointPtr
                    PointPtr[0] = pointcoord;
                    Pt_Count++;
                }
                else
                {
                    PointCoord *Temp = PointPtr;
                    PointPtr = new PointCoord[Pt_Count + 1];

                    for (UINT i = 0; i < Pt_Count; i++)
                    {
                        PointPtr[i] = Temp[i];
                    }
                    PointPtr[Pt_Count] = pointcoord;
                    Pt_Count++;
                    delete[]Temp;
                }
            }//end of loading points
      }//end of getline

我还使用 std::fread 在字符串缓冲区中一次读取整个文本文件，速度很快(读取在几秒钟内完成)。然后在类似代码中使用stringstream将点坐标存储在动态数组中，这也太慢了。

欢迎提出任何建议。非常感谢。

最佳答案

这段代码中最该死的不是字符串解析；它是每个新点读取的目标数组的大小调整。你读得越多，情况就越糟。最终就变成了O(n^2)量级的复制操作。

为了让您了解这有多糟糕，请考虑 basic summation of n natural numbers ，因为那是您正在执行的对象构造、破坏和复制的数量:

n(n+1)/2 = (20000 * 20001)/2 = 200010000 objects created, copied, and destroyed

所以，字符串解析不是问题。被解析的 20000 行文本与超过 2 亿个对象的构造、破坏和复制相比相形见绌。

您不需要执行任何这些操作。使用适当的容器，如 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();
}

输出

在 2015 双核 i7 MacBook Air 笔记本电脑上运行， Release模式构建产生以下结果:

Read 100000 points in 164ms

一个可能更合适的容器: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 可能更合适。考虑一下，然后选择最适合您的。

总结

摆脱那个可怕的扩展算法。这是您代码中的痛点。将其替换为几何调整大小算法，并从一开始就粗略估计您将需要的元素数量开始。或者使用适合最佳末端插入的容器。无论哪种方式，它都比您现在拥有的要好。

关于c++ - 处理字符串最快的方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52922901/