从二维向量切换到一维向量

Question

我听说向量的向量在性能方面很差。例如，我有以下 2D std::vector:

std::vector< std::vector<char> > characterMatrix;

// for iterating
for ( int row = 0; row < getY_AxisLen( ); ++row )
{
    for ( int column = 0; column < getX_AxisLen( ); ++column )
    {
        std::cout << characterMatrix[ row ][ column ];
    }
}

在这种方法中，矩阵在我的系统上会在 3-12 毫秒内打印出来。如果我看到例如减少，我会很高兴。 1-3 毫秒。

据我所知，每个内部向量（即行）都存储在堆内存的不同位置。所以这会导致很多碎片。
不仅如此，我编译器中的 sizeof(std::vector) returns 24（字节）。所以这意味着，例如，如果 characterMatrix 有 50 行（又名内部向量），那么它会在堆上分配 24*50 == 1200 字节来存储控件这 50 个向量的块，这是对矩阵中实际数据 (chars) 所采用的 space 的补充。

现在，如果我想将所有 char 保存在一个连续的内存块中，也许我可以将其写成一维向量，例如：

std::vector< char > characterMatrix;

// for iterating
for ( int row = 0; row < getY_AxisLen( ); ++row )
{
    for ( int column = 0; column < getX_AxisLen( ); ++column )
    {
        std::cout << characterMatrix[ row * getX_AxisLen( ) + column ]; // is this correct?
    }
}

这是一种有效的方法吗？如果我想以这种方式更改矩阵变量的实现，有人能告诉我应该记住哪些事情吗？可能的缺点是什么？

Answer 1

“听说过”和表演在一起从来都不是正确的做法。为了解决性能问题，黄金法则是：基准测试优先！

此外，性能并不总是最重要的。通常，只有当您发现您的应用程序的速度不足以满足您的目的时，您才应该优化性能。然后，按照以下步骤操作：

首先，您需要确保您正在查看的代码部分 实际上是应用程序中的性能瓶颈（为此使用分析器）。无需优化总计仅占计算时间 1% 的东西 - 即使将其速度提高 10 倍，也只会将总执行时间减少 0.9%！如果您发现此 2D 向量访问确实是瓶颈，那么 基准测试 它可以为以后的实验提供基线。
其次，您的代码需要正确。如果在针对性能对其进行优化后它没有做正确的事情，那么再快也没有用。在这里我建议把测试放到位（也就是用naive/unoptimized的方式记录结果，这样当你优化的时候，你知道你是否仍然得到相同的结果）。
第三，性能优化往往会对代码的可读性and/or可维护性产生负面影响。但是，这些可能非常重要，尤其是对于那些需要很好理解或经常更改的代码部分。

是的，2D 向量表明您的性能可能不理想，因为正如您所说，数据并非全部位于一个地方。然而，正如您目前所做的那样，在最内层循环内的每次访问上完成的索引计算也是“昂贵的”。因此，将数据放在一个大矢量而不是二维矢量场中会更快；特别是如果您总是必须处理所有元素并且不需要“邻域”访问，这意味着您可以简单地让一个循环从 0 迭代到您所谓的 getY_AxisLen() * getX_AxisLen()。如上所述，拥有一个基准可以帮助您找出哪些优化是有意义的！为了解决减少的 readability/maintanability，在您的情况下抽象出用于存储 2D 数据的实际数据结构可能会有所帮助，这样数据存储方式的实际实现就隐藏在数据所在的地方已访问。

从二维向量切换到一维向量

Switching from a 2D vector into a 1D vector

c++

stdvector

multidimensional-array

dynamic-memory-allocation