我有一些用C++编写的代码，它是一个简单的程序，用于找出具有3000多个顶点的图形的pair-wise dmin。所有的边具有相同的权重1.所以我在所有的顶点对上做BFS。vector <vector<int>>需要太长的初始化
我的程序运行速度不够快，所以我使用Xcode 4.2.1的产品 - >配置文件对代码进行了分析。它称之为“工具”的工具。过了一会儿，我想出了如何使用它。但是我得到的东西很混乱。高亮线如何使用这么多时间？任何想法都非常感谢。
我定义了： vector visited; 矢量<矢量> G; //邻接表 
声明中绝大多数时间：(visited[G[n][i]] == false)可能是由于大量的缓存未命中所致。
注意G是一个很大的3K * 3K矩阵，以一个连续的虚拟存储器空间，并且visited是另一个3K阵列服用另一个邻接存储器在虚拟存储器空间中的不同位置。在同一语句中访问这两个内存位置将导致大量缓存未命中，具体取决于处理器缓存的容量。
为了加快速度，请牢记locality of reference。
好点，这是有道理的。你能否举一些例子说明我可以如何（参观[G [n] [i]] == false）跟随参考的地点？ – user2883918
@ user2883918，正如您在之前的评论中已经提到的那样，您正在考虑将G [n]排除在循环之外。这将有所帮助，取决于您的机器。对于小型机器，当“参观”与“G”一起杵状时，获得了主要优势。也就是说，当G被表示为所有节点的向量时，其中每个节点都有一个邻接列表以及一个布尔“已访问”变量。 – user2784234
如果你有多维数组并且遇到缓存问题，请尝试在[boost.MultiArray]（http://www.boost.org/doc/libs/1_54_0/libs/multi_array/doc/user.html）中交换这也可以让你自定义尺寸的存储顺序，所以你可以尝试获得最佳性能。 –
完成了吗？这可能是一个无限循环？ –
您有3000多个顶点。出于好奇，有多少边缘？ – WhozCraig
@科尔约翰逊，是的，它结束了。 – user2883918