그래프 표현 벤치마킹

Question

현재 3X4에서 26x30까지의 임의의 주어진 미로를 해결할 수있는 프로그램을 개발 중입니다. adj 매트릭스 (희소)와 adj리스트를 모두 사용하여 그래프를 나타냅니다. DFS가 취한 총 시간을 출력하여 하나를 사용하여 솔루션을 찾은 다음 다른 방법을 사용하는 방법을 알고 싶습니다. 프로그래밍 방식으로, 어떻게 그런 벤치 마크를 생산할 수 있습니까?

Answer 1

유용한 표는 다양한 그래프 구현으로 해결해야 :

m은 에지의 개수

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²) 

, n 정점의 개수이고 d(vertex) 버텍스 인접 요소의 개수 목록 .. adj 행렬 구현은 행렬을 다시 할당해야하기 때문에 정점을 추가하고 제거하는 O(n²)을가집니다.

기사를 위해 이것을 준비했습니다. 준비 :)

보통 벤치마킹과 관련이 없으므로 대개 필요한 작업을 연구하고 필요에 맞는 적절한 구현을 선택하므로 일종의 "이론적 인"벤치 마크입니다. 구현할 것입니다. 그렇지 않으면 두 구현으로 전체 작업을 수행하고 비교하는 데 코드가 필요한 시간을 측정 할 수 있습니다.

편집 : 스파 스 매트릭스 구현을 사용하기 때문에 조작의 복잡도가 약간 변경 될 수 있습니다 (속도가 느려질수록 메모리가 조금씩 증가하기 때문에).

EDIT2 :이이 공정 간단하다 자바 것을 알고 지금 확인 :

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"