java - グラフ表現のベンチマーク

Question

現在、(可能であれば) 3X4 から 26x30 までの寸法の任意の迷路を解くプログラムを開発しています。adj マトリックス (スパース) と adj リストの両方を使用してグラフを表します。DFS が 1 つの方法を使用してソリューションを見つけた後、別の方法を使用して合計時間を出力する方法を知りたいです。プログラム的に、どうすればそのようなベンチマークを作成できますか?

Answer 1

さまざまなグラフの実装を扱うのに役立つ表:

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;

答えはナノ秒単位であり、精度は保証されていませんので、慎重に使用してください。多くの実行の平均を行う (そして分散が低いことを確認し、平均から離れている結果を破棄する) と、結果に一貫性が得られます。

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"