我仍然是C的新手,还有很多需要学习的东西,但我最近变得非常依旧的是使用嵌套(多维)向量.所以我通常会得到这样的东西：
std::vector<std::vector<std::string> > table;
然后,我可以轻松访问这样的元素：
std::string data = table[3][5];
然而,最近我得到的印象是(在性能方面)更好地拥有一维向量,然后只使用“索引算术”来相应地访问元素.我认为这种性能影响对于更大或更高维度的向量来说是重要的,但我真的不知道,到目前为止还没有找到关于它的大量信息.
虽然直觉上,单个向量比高维向量具有更好的性能是有道理的,但老实说,我并不理解其实际原因.此外,如果我只是使用单维向量,我将失去用于访问多维元素的直观语法.所以这是我的问题：
为什么多维向量效率低下？如果我只使用一维向量(表示更高维度的数据),那么访问其元素的最佳,最直观的方法是什么？
解决方法
这取决于具体条件.当嵌套版本是真正的2D表格(即,所有行具有相同的长度)时,我将讨论这种情况.
一维矢量通常在每种使用模式上都会更快.或者,至少,它不会比嵌套版本慢.
嵌套版本可以被认为更糟,因为：
>它需要分配行数而不是一行.
>访问元素需要额外的间接,因此它更慢(额外的间接通常比1D情况下所需的乘法更慢)
>如果您按顺序处理数据,那么如果2D数据散布在内存中,则速度会慢得多.这是因为可能存在大量缓存未命中,这取决于内存分配器如何返回不同行的内存区域.
所以,如果你追求性能,我建议你为1D向量创建一个2D包装类.这样,您可以获得与嵌套版本一样简单的API,并且您也将获得最佳性能.甚至,如果由于某种原因,您决定使用嵌套版本,您只需更改此包装类的内部实现.
访问1D元素的最直观方式是y * width x.但是,如果您知道自己的访问模式,则可以选择其他模式.例如,在绘画程序中,基于图块的索引可以更好地存储和操纵图像.在这里,数据可以像这样索引：
int tileMask = (1<<tileSizeL)-1; // tileSizeL is log of tileSize int tileX = x>>tileSizeL; int tileY = y>>tileSizeL; int tileIndex = tileY*numberOfTilesInARow + tileX; int index = (tileIndex<<(tileSizeL*2)) + ((y&tileMask)<<tileSizeL) + (x&tileMask);
该方法在存储器中具有更好的空间局部性(彼此接近的像素倾向于具有接近的存储器地址).索引计算比简单的y * width x慢,但是这种方法可以减少缓存未命中率,所以最后它可能更快.
