Сравнительное тестирование представления графика
В настоящее время разрабатываю программу, которая решает (если возможный) любой данный лабиринт размеров от 3X4 до 26x30. Я представляю график с помощью и (редкой) матрицы прил и списка прил. Я хотел бы знать, как произвести общее время, потраченное DFS для нахождения решения с помощью один и затем другой метод. Programatically, как я мог произвести такой сравнительный тест?
2 ответа
Полезная таблица для работы с различными реализациями графов:
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 (вершина) - количество элементов в списке смежности вершин. Реализация матрицы adj имеет O (n² ) для добавления и удаления вершин, потому что вам нужно перераспределить матрицу ..
Просто подготовил это для статьи, поэтому у меня он готов :)
Это не имеет прямого отношения к тестированию, поскольку обычно вы изучите, какие операции вам больше всего понадобятся, и выберите правильную реализацию для своих нужд, так что это своего рода «теоретический» тест, который вы делаете, изучая, что вы собираетесь реализовать. В противном случае вы можете просто измерить время, необходимое вашему коду для выполнения всей работы с обеими реализациями, и сравнить его.
РЕДАКТИРОВАТЬ: поскольку вы используете реализацию с разреженной матрицей, сложность операций может немного измениться (в основном становится немного хуже, так как вы меняете память на скорость).
EDIT2: хорошо, теперь, когда я знаю, что это Java, все будет просто:
long before = System.nanoTime();
/* execution of your algorithm */
long elapsed = System.nanoTime() - before;
Ответ в наносекундах, и точность не гарантируется, поэтому используйте эту штуку осторожно. Выполнение среднего из многих прогонов (и проверка того, что дисперсия низкая, отбрасывание результатов, которые более далеки от среднего) придадут согласованности вашим результатам.
Если у вас есть подходящие методы, это должно быть довольно просто. Просто заключите оба метода в таймер и повторите его много раз для получения статистической значимости.
--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"