Représentation graphique de la représentation graphique

Question

Je suis en train de développer un programme qui résout (si possible) un labyrinthe donné de dimensions de 3X4 à 26x30. Je représente le graphique en utilisant à la fois la matrice adj (sparse) et la liste adj. Je voudrais savoir comment sortir le temps total pris par le DFS pour trouver la solution en utilisant l'une puis l'autre méthode. Par programme, comment pourrais-je produire un tel benchmark?

Answer 1

Une table utile pour travailler avec diverses implémentations graphiques:

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

où m est le nombre d'arêtes, n est le nombre de sommets et d(vertex) est le nombre d'éléments dans le sommet contiguïté liste .. adj implémentation matricielle a un O(n²) pour ajouter et supprimer des sommets parce que vous devez réaffecter la matrice ..

Juste préparé ceci pour un article, cela pourquoi je l'ai ready :)

Ceci n'est pas directement lié à l'analyse comparative, puisque vous étudiez généralement les opérations dont vous aurez besoin et choisissez la bonne implémentation pour vos besoins, c'est donc une sorte de benchmark "théorique" que vous faites en étudiant ce que vous vont mettre en œuvre. Sinon, vous pouvez simplement mesurer le temps dont votre code a besoin pour faire tout le travail avec les deux implémentations et le comparer. Étant donné que vous utilisez une implémentation à matrice clairsemée, la complexité des opérations pourrait légèrement changer (la plupart du temps étant un peu moins bonnes, car vous échangez de la mémoire contre de la vitesse).

EDIT2: ok, maintenant que je sais que c'est Java, il sera simple juste:

long before = System.nanoTime(); 

/* execution of your algorithm */ 

long elapsed = System.nanoTime() - before; 

réponse est en nanosecondes et la précision n'est pas garantie, utilisez donc soigneusement cette chose. Faire une moyenne de plusieurs passages (et vérifier que la variance est faible, en écartant le résultat plus éloigné de la moyenne) donnera de la cohérence à vos résultats.

Answer 2

En supposant que vous avez des méthodes appropriées, cela devrait être assez simple. Il suffit d'envelopper les deux méthodes dans une minuterie, et répétez-le plusieurs fois pour la signification statistique.

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