圖形表示基準測試

Question

目前，我正在開發一個程序，可以解決（如果可能）任何給定的從3X4到26x30的尺寸迷宮。我使用adj matrix（稀疏）和adj列表來表示圖形。我想知道如何輸出DFS花費的總時間，然後使用另一種方法查找解決方案。在編程上，我怎麼能產生這樣的基準？

Answer 1

一種有用表與各種圖形實現，以計算出：

OPERATION    EDGE LIST  ADJ LIST    ADJ MATRIX 

degree(v)     O(m)   O(d(v))    O(n) 
incidentEdges(v)   O(m)   O(d(v))    O(n) 
areAdjacent(v1,v2)  O(m)   O(min(d(v1),d(v2))  O(1) 
addVertex(v)    O(1)   O(1)     O(n²) 
addEdge(v)    O(1)   O(1)     O(1) 
removeVertex(v)   O(m)   O(m)     O(n²) 
removeEdge(e)    O(m)   O(d(v1)+d(v2))   O(1) 

memory     O(m+n)  O(m+n)     O(n²) 

其中m是邊緣的數量，n是頂點的數目和d(vertex)是在頂點鄰接元件的數量列表..形成矩陣實施有一個O(n²)添加和刪除頂點，因爲你必須重新分配矩陣..

剛剛準備這篇文章，爲什麼我有它準備好:)

這與基準測試沒有直接關係，因爲通常您會研究您最需要的操作，並根據您的需求選擇正確的實施，所以這是一種「理論」基準測試，您可以通過研究將要實施。否則，你可以測量你的代碼需要在兩個實現中完成整個工作的時間並進行比較。

編輯：由於您使用稀疏矩陣實現操作的複雜性可能會稍微改變（通常會變得更糟，因爲您正在交易內存的速度）。

EDIT2：好了，現在我知道，這是Java的將是公平簡單：

long before = System.nanoTime(); 

/* execution of your algorithm */ 

long elapsed = System.nanoTime() - before; 

答案是納秒和準確性不能保證，因此請謹慎使用這個東西。平均進行多次運行（並檢查差異是否較低，丟棄距離平均值較遠的結果）會使結果保持一致。

Answer 2

假設你有一個合適的方法，這應該相當簡單。只需將這兩種方法都包含在定時器中，並重復多次以獲得統計顯着性。

--test method with adjacency matrix 
start = TimeNow() 
repeat 1000 times 
    DepthFirstSearchWithAdjMatrix() 
timePerSearch = (TimeNow() - start)/1000.0 

--test method with adjacency list 
start = TimeNow() 
repeat 1000 times 
    DepthFirsySearchWithAdjList() 
timePerOtherSearch = (TimeNow() - start)/1000.0 

if timePerSearch < timePerOtherSearch 
    print "Adj Matrix is better than adj list" 
else 
    print "Adj Matrix is worse than adj list"