6

目前正在开发一个程序，可以解决（如果可能的话）从 3X4 到 26x30 的任何给定尺寸迷宫。我使用 adj 矩阵（稀疏）和 adj 列表来表示图形。我想知道如何输出 DFS 使用一种方法和另一种方法找到解决方案所花费的总时间。以编程方式，我怎么能产生这样的基准？

4

2 回答 2

10

一个有用的表格，用于计算各种图形实现：

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)是顶点邻接列表中的元素数。adj 矩阵实现具有O(n²)添加和删除顶点，因为您必须重新分配矩阵。

刚刚为一篇文章准备了这个，这就是为什么我准备好了:)

这与基准测试没有直接关系，因为通常您会研究您最需要哪些操作并根据您的需要选择正确的实现，因此它是一种“理论”基准，您可以通过研究您将要实现的内容来进行。否则，您可以只测量您的代码使用两种实现完成整个工作所需的时间并进行比较。

编辑：由于您使用稀疏矩阵实现，因此操作的复杂性可能会略有变化（大多数情况会变得更糟，因为您正在用内存换取速度）。

EDIT2：好的，现在我知道这是Java，这将很简单：

long before = System.nanoTime();

/* execution of your algorithm */

long elapsed = System.nanoTime() - before;

答案以纳秒为单位，无法保证准确性，因此请谨慎使用。对多次运行进行平均（并检查方差是否很低，丢弃与平均值较远的结果）将使您的结果具有一致性。

于 2010-04-16T23:55:35.887 回答
3

假设您有合适的方法，这应该相当简单。只需将这两种方法都包装在一个计时器中，并重复多次以获得统计意义。

--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"
于 2010-04-16T23:55:03.517 回答