c++ - 向量> 初始化时间过长

Question

我有一些用 C++ 编写的代码，它是一个简单的程序，可以为具有 3000 多个顶点的图找出成对的 dmin。所有边都具有相同的权重 1。所以我对所有顶点对进行 BFS。

我的程序运行速度不够快，所以我使用 Xcode 4.2.1 的 product->profile 对我的代码进行了分析。它调用了一种称为“仪器”的工具。一段时间后，我想出了如何使用它。但是我得到的非常混乱。突出显示的行怎么会占用这么多时间？任何想法都受到高度赞赏。

我定义：向量被访问；vector<vector> G;//邻接表

Answer 1

声明中花费的绝大多数时间：(visited[G[n][i]] == false)将是由于大量缓存未命中。

请注意，这G是一个 3k*3k 的大矩阵，占用一个连续的虚拟内存空间，visited另一个 3k 数组在虚拟内存空间的不同位置占用另一个连续的内存。在同一语句中访问两个内存位置将导致大量缓存未命中，具体取决于处理器缓存的容量。

为了加快速度，重写程序时要牢记参考的局部性。

Answer 2

运行的仪器告诉您，大部分时间访问[G[n][i]] 是正确的。