我有一些用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