1

我正在创建一个存储在嵌套向量中的巨大矩阵：

typedef vector<vector<pair<unsigned int, char>>> Matrix;

外部向量最终将包含约 400.000 个向量，每个向量最多包含约 220 对（大多数包含较少）。这需要大约 1GB 的 RAM，并且是这样完成的：

Matrix matrix;
for (unsigned int i = 0; i < rows; i++) {
    vector<pair<unsigned int, char>> row;
    for (unsigned int j = 0; j < cols; j++) {
        // ...calculations...
        row.push_back( pair<unsigned int, char>(x, y) );
    }
    matrix.push_back(row);
}

前 20% 的速度非常快，但外部向量增长得越大，整个过程的速度就越慢。我很确定可以进行一些优化，但我不是该领域的专家。有什么简单的技巧可以加快速度吗？或者我的尝试有什么重大错误？

4

4 回答 4

8

最好只使用单个一维向量并在某些函数/类中包装行、列索引。这样可以保证整个矩阵的内存是连续的。

而不是预先push_back分配整个矩阵：

std::vector<pair<unsigned int, char>> matrix(rows * cols);
于 2012-08-17T11:46:46.233 回答
2

我将从明显的优化开始。如果您在开始填充值（或可用上限）之前知道行数，则只需事先保留空间。push_back 大量值时花费的最多时间是重新分配内存和复制已包含的值。

Matrix matrix(rows);
for(unsigned i = 0; i < rows; i++) {
    vector<pair<unsigned int, char>> row(cols);
    for(unsigned j; j < cols; j++) {
        row[j] = // value
    }
    matrix[i] = row;
}
于 2012-08-17T12:36:42.943 回答
2

使用 VS 2010 编译器，以下结果效果最佳：

Matrix matrix;
matrix.reserve(rows);

vector<pair<unsigned int, char>> row;
row.reserve(cols);

for (unsigned int i = 0; i < rows; i++) {
    for (unsigned int j = 0; j < cols; j++) {
        // ...calculations...
        row.push_back( pair<unsigned int, char>(x, y) );
    }
    matrix.push_back(row);
    row.clear();
}

与创建一个每次为“cols”条目分配内存的新向量相比，只创建一个用于构建所有行的向量消耗的内存要少得多。不太清楚为什么会这样。

但是，我接受 Andreas 的回答，因为这只是针对我的具体情况的解决方案，而他的回答提供了此类优化所需的一般信息。

于 2012-08-18T10:11:32.403 回答
1

问题是当外部向量增长时会复制大量数据。考虑将您的 typedef 更改为

typedef vector< shared_ptr< vector<pair<unsigned int, char>> > > Matrix;

并matrix.reserve(rows)在你开始用值填充它之前做。

于 2012-08-17T12:20:59.087 回答