1

我有一个大约 400MB 的 1000 行文件，表示一些表示为字符串的数字数据。我想转置数据，以便每行只有 1000 个字符串（这样我就可以打开它并用 pandas 快速绘制它）。

我将整个文件导入到我想要转置的字符串向量的向量中（最终我想写回文件）。

我使用两个嵌套循环来遍历 2d 结构，并将其写入一些 std::ofstream。它很长。然后我尝试专注于转置，并编写了以下代码：

//Read 400MB file, 90K strings per line and 1K lines, and store it into
std::vector<std::vector<std::string>> mData;

// ... 
// IO the file and populate mData with raw data 
// ...

//All rows have same number of string
size_t nbRows = mData.size();
size_t nbCols = mData[0].size();

std::vector<std::vector<std::string> > transposedData(nbCols);
for(size_t i = 0 ; i < nbCols  ; ++i)
{
    transposedData[i].resize(nbRows);
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        transposedData[i][j] = doc.mData[j][i];
    }
}

我认为几秒钟就足够了，但它需要几分钟。另外，我正在尝试使用不同的输入尺寸（对于相同的 400MB 文件大小，每行只有 3 行和更多的字符串），而且速度要快得多。

编辑 1

根据人们的建议，我使用 callgrind 进行了分析。我在此过程中收到此消息：...线程#1 中的 brk 段溢出：无法增长到...

我对结果进行了分析并在此总结：
25 % 用于 basic_string 的 operator=
21 % 用于构建 basic_string （只有 3% 的时间在 new 中）
14 % 用于外部向量的 operator()[]
11 % 用于内部向量的 operator()[]

谢谢你的建议。

4

4 回答 4

1

首先，在对一段代码运行缓慢的原因提出任何声明之前，您应该真正测量其在您的机器上的性能，然后根据手头的数据推断原因。

也就是说，我在这种情况下非常有信心说问题可能在于您正在分配90kstring 的向量，每个向量都是 size 1k。如您所知，内存分配成本很高，它可能解释了您的性能损失。

以下是仅使用1D预先分配的数组来实现代码的方法。

size_t nbRows = mData.size();
size_t nbCols = mData[0].size();

auto get_idx = [](const int i, const int nr, const int j)
{
    return i*nr+j;
};

std::vector<std::string> transposedData(nbCols*nbRows);  
for(size_t i = 0 ; i < nbCols  ; ++i)
{
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        const int idx = get_idx(j, nbCols,i);
        transposedData[idx] = std::move(mData[j][i]);
    }
}

for(size_t i = 0 ; i < nbCols  ; ++i)
{
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        const int idx = get_idx(j, nbCols,i);
        cout<<transposedData[idx]<<" ";
    }
    cout<<endl;
}

我想再次强调一下：分析您的代码。试用软件，例如valgrind --tool= callgrind或gprof允许您分析和可视化有关您的应用的性能数据。

于 2019-10-03T09:13:59.560 回答
1

该计划在多个层面上都有冗余。

显而易见的是，您无需转置矢量即可转置文件。

vector<vector<string> originalData;
// read the file to originalData

for(size_t i = 0 ; i < nbCols  ; ++i)
{
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        cout << originalData[j][i] << " ";
    }
    cout<<endl;
}

假设您出于某种原因确实需要生成转置向量，编写转置循环的一种方法是

vector<vector<string>> transposedData (nbCols);
for (size_t j = 0; j < nbCols; ++j)
{
    transposedData[j].reserve(nrows);
    for (size_t i = 0; i < nbRows; ++i) 
    {
        transposedData[j].emplace_back(originalData[i][j]);
        // if keeping original veector is not needed ...
        // transposedData[j].emplace_back(std::move(originalData[i][j]));
    }
}

在我的（相当强大的）机器上，转置一个 1000x90000 的 3 字符字符串矩阵大约需要 6-7 秒。这并不是特别令人印象深刻，如果您不需要每天 24 小时转置数百万个元素的矩阵，它就可以满足您的需要，而不会产生太多开销。

于 2019-10-03T12:35:21.937 回答
0

惩罚可能来自您在 for 循环中过度使用 resize 的事实。

根据参考：

复杂

当前大小和计数之间的差异呈线性关系。如果容量小于计数，则可能由于重新分配而增加复杂性

内存分配成本很高，因此您可能希望避免过度使用。

正如其他人所指出的，预先分配将是一种有趣的方法，可以避免每次都重新创建（调整大小）你的向量。

于 2019-10-03T09:21:09.903 回答
0

我的机器上没有足够的可用内存来执行此任务（见下文）。将我的数据分成三部分，我在几秒钟内完成了任务。这是检查内存的代码的输出：

free ram 2.5GB  
IO populating mData with raw data  
free ram 0.2GB  
Empty string capacity : 15 bytes  
Intending to allocate 1.4 GB  
terminate called after throwing an instance of 'std::bad_alloc'  
  what() : std::bad_alloc  
Aborted
于 2019-10-03T10:31:44.347 回答