处理字符串最快的方法

Question

我有一个文本文件要读取和处理 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将点坐标存储在动态数组中，这也太慢了。

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

Answer 1

这段代码中最糟糕的不是字符串解析，而是字符串解析。它是每个新点读取的目标数组的大小调整。你读得越多，情况就越糟。最终就变成了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 并根据文件大小估算初始保留。然后，生成点并将它们移动到容器中。

执行此操作的示例如下所示：

代码

#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 笔记本电脑上，发布模式构建产生以下结果：

Read 100000 points in 164ms

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

最后，您真正需要的是一个允许在最后快速插入，同时在调整大小时最小化（或消除）元素复制的容器。当然，如上面的代码所示，针对 std::vector 设置储备金是一种方法。另一种选择是使用一个专门从事末端插入的容器，同时仍然主要是缓存友好的（不像 std::vector 那样完美，但肯定比链表之类的东西要好，后者非常适合插入，但是 dreadful 用于枚举）。

这正是 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 可能更合适。考虑一下，然后选择最适合您的。

总结

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

Answer 2

如果您想进一步提高，可以做两件事。

您可以内存映射整个文件，而不是逐行读取文件，并使用基于指针的 C 风格代码将其拆分为行，然后将每行拆分为字段。可以在一次迭代中完成这两个步骤，就像您现在所做的那样。这样你就可以编写不复制字符串的代码，除了名称。如果您使用 Visual C++，请参阅 CAtlFileMapping<char> 模板 class。
标准的浮点解析器代码，std::strtof中的代码，非常通用。如果您的文本是 ASCII，并且数字以 -12.3456 这样的通常形式存储，即您没有 INF 或 NAN，并且您没有像 -1.23E+1 这样的科学计数法数字，您可以编写自己的strtof 的版本将比标准版本快 2-3 倍。

处理字符串最快的方法

Fastest method to deal with string

c++

fwrite

fread