图形表示基准测试

发布于 2024-08-29 08:57:30 字数 143 浏览 2 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

陪你到最终 2024-09-05 08:57:31

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

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²) 来添加和删除顶点，因为您必须重新分配矩阵。

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

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

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

编辑2：好吧，现在我知道这是Java，这将很简单：

long before = System.nanoTime();

/* execution of your algorithm */

long elapsed = System.nanoTime() - before;

答案以纳秒为单位，并且不能保证准确性，所以请小心使用这个东西。对多次运行进行平均（并检查方差是否较低，丢弃与平均值相差较大的结果）将使您的结果具有一致性。

An useful table to work out with various graphs implementations:

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

where m is the number of edges, n is the number of vertices and d(vertex) is the number of elements in the vertex adjacency list.. adj matrix implementation has an O(n²) to add and remove vertices because you have to reallocate the matrix..

Just prepared this for an article, that why I have it ready :)

This is not directly related to benchmarking, since usually you study which operations you will mostly need and choose the right implementation for your needs, so it's a sort of "theoretical" benchmark that you do by studying what you are going to implement. Otherwise you can just measure time that your code needs to do the whole work with both implementations and compare it.

EDIT: since you use a sparse matrix implementation the complexity of operations could slightly change (mostly getting a little worse, since you are trading memory for speed).

EDIT2: ok, now that I know that this is Java it will be fair simple:

long before = System.nanoTime();

/* execution of your algorithm */

long elapsed = System.nanoTime() - before;

Answer is in nanoseconds and accuracy is not guaranteed, so use this thing carefully. Doing an average of many runs (and checking that variance is low, discarding the result that are more distant from the average) will give coherence to your results.

回复收藏 0 原文

奢欲 2024-09-05 08:57:31

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

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

Assuming you have a suitable methods, this should be fairly simple. Just wrap both the methods in a timer, and repeat it many times for statistical significance.

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

回复收藏 0 原文

~没有更多了~