处理字符串的最快方法

我有一个文本文件来阅读和处理20000行.在文本文件中,我想读取点坐标并分配给DirectX进行渲染.文本文件的快照

我使用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 

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

欢迎任何建议.非常感谢.


1> WhozCraig..：
这段代码中最令人讨厌的事情不是字符串解析; 它为每个新读取的点调整目标数组的大小.你读的越多,它就越糟糕.最终,它成为O(n ^ 2)的复制操作.

为了给你一个想法如何不好说是,考虑的基本总和n自然数,因为这是你做了多少对象结构,破坏,和复印件:


  
n(n + 1)/ 2 =(20000*20001)/ 2 = 创建,复制和销毁200010000个对象


因此,字符串解析不是问题.被解析的20000行文本与超过2亿个对象构造,析构和副本相比相形见绌.



你不需要做任何这些.std::vector根据文件大小使用适当的容器,例如并接近初始保留.然后,只需生成点并将它们移动到容器中.

这样做的一个例子,包括生成一个100000点的测试文件(你问的大小的5倍),如下所示:

码

#include 
#include 
#include 
#include 
#include 
#include 
#include 

struct Point
{
    std::string name;
    float x;
    float y;
};

std::vector readFile(std::string const& fname)
{
    std::vector 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 dist(-100.0, 100.0);

    // generate test data
    std::ofstream outf("testpoints.txt");
    for (int i=1; i<=100000; ++i)
        outf <<"POINT  \"" <(tp1-tp0).count() <<"ms\n";
    v.clear();
}


产量

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

Read 100000 points in 164ms




一个可能更合适的容器: std::deque

最后,您真正需要的是一个允许在最后快速插入的容器,同时在调整大小期间最小化(或消除)元素复制.当然,正如上面的代码所示,设置对a的储备std::vector是一种方法.另一个选择是使用一个专门用于端插入的容器,同时仍然主要是缓存友好的(不完美的std::vector,但肯定比链接列表更好,这对于插入非常好,但对于枚举来说是可怕的).

这正是std::deque将要做的.上面的代码,更改为std::deque,允许您消除reserve-guess,并简单地开始关闭序列末尾的节点,这将随着序列的增长自动添加更多页面:

码

#include 
#include 
#include 
#include 
#include 
#include 
#include 

struct Point
{
    std::string name;
    float x;
    float y;
};

std::deque readFile(std::string const& fname)
{
    std::deque 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 dist(-100.0, 100.0);

    // generate test data
    std::ofstream outf("testpoints.txt");
    for (int i=1; i<=100000; ++i)
        outf <<"POINT  \"" <(tp1-tp0).count() <<"ms\n";
    v.clear();
}


产量

Read 100000 points in 160ms


如果您的需求需要连续的序列,那么这种std::vector方法就是您的选择.如果您只是需要随机访问元素并希望快速插入,那么std::deque可能更适合.想一想,选择最适合自己的.



摘要

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