Chuẩn mực biểu diễn biểu đồ

Question

Hiện tại, tôi đang phát triển một chương trình giải quyết (nếu có thể) bất kỳ mê cung nào có kích thước từ 3X4 đến 26x30. Tôi đại diện cho các đồ thị bằng cách sử dụng cả hai ma trận adj (thưa thớt) và danh sách adj. Tôi muốn biết làm thế nào để sản xuất tổng thời gian được thực hiện bởi DFS để tìm giải pháp bằng cách sử dụng một và sau đó là phương pháp khác. Lập trình, làm cách nào tôi có thể tạo ra điểm chuẩn như vậy?

Answer 1

Một bảng hữu ích để làm việc với biểu đồ triển khai khác nhau:

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ơi m là số cạnh, n là số đỉnh và d(vertex) là số phần tử trong kề đỉnh danh sách .. thực hiện ma trận adj có một O(n²) để thêm và loại bỏ các đỉnh vì bạn phải phân bổ lại ma trận ..

Chỉ cần chuẩn bị điều này cho một bài viết, tại sao tôi có nó sẵn sàng :)

Điều này không liên quan trực tiếp đến điểm chuẩn, vì bạn thường nghiên cứu hoạt động nào bạn cần và chọn thực hiện đúng cho nhu cầu của bạn, vì vậy đó là loại chuẩn "lý thuyết" mà bạn thực hiện bằng cách nghiên cứu những gì bạn sẽ triển khai. Nếu không, bạn chỉ có thể đo thời gian mà mã của bạn cần làm toàn bộ công việc với cả hai triển khai và so sánh nó.

CHỈNH SỬA: vì bạn sử dụng ma trận thưa thớt sự phức tạp của hoạt động có thể thay đổi một chút (chủ yếu là tệ hơn một chút, vì bạn đang giao dịch bộ nhớ tốc độ).

EDIT2: ok, bây giờ mà tôi biết rằng đây là Java nó sẽ là công bằng đơn giản:

long before = System.nanoTime(); 

/* execution of your algorithm */ 

long elapsed = System.nanoTime() - before; 

trả lời là trong nano giây và độ chính xác không được bảo đảm, vì vậy sử dụng điều này một cách cẩn thận. Làm trung bình của nhiều lần chạy (và kiểm tra phương sai đó là thấp, loại bỏ kết quả xa hơn mức trung bình) sẽ cho kết hợp với kết quả của bạn.

Answer 2

Giả sử bạn có một phương pháp phù hợp, điều này sẽ khá đơn giản. Chỉ cần bọc cả hai phương pháp trong bộ hẹn giờ và lặp lại nó nhiều lần để có ý nghĩa thống kê.

--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"