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?Représentation graphique de la représentation graphique
Répondre
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.
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"
@Martin: merci pour votre réponse, je comprends parfaitement. S'il vous plaît, supportez-moi car je n'ai jamais utilisé quelque chose comme ça. Savez-vous comment TimeNow() est appelé en java? – Carlos
l'a trouvé! import java.util.Date; - DateFormat dateFormat = new SimpleDateFormat ("aaaa/MM/jj HH: mm: ss") .... – Carlos
Une meilleure chose à utiliser dans Java est l'heure du système http://java.sun.com/j2se/1.5 .0/docs/api/java/lang/System.html # currentTimeMillis% 28% 29 – Martin
- 1. Représentation graphique
- 2. représentation graphique Flex dataTipFunction
- 3. Représentation graphique dans Haskell
- 4. Exemple de représentation graphique F #
- 5. données Haskell graphique de représentation de type
- 6. Représentation graphique d'un ensemble de données
- 7. Représentation graphique du tableau trier dans vb.net
- 8. Représentation graphique des données en flex
- 9. Bibliothèque pour la représentation graphique des tas binaires?
- 10. Représentation graphique de l'activité de branche/fusion SVN
- 11. Représentation graphique des données sous forme de texte
- 12. Plugin Trac avec représentation graphique des jalons et tickets
- 13. Représentation graphique d'instances dans RDF (sur le site Web)
- 14. Dessiner une représentation graphique ou un graphique de liens entre amis
- 15. 2d représentation de tableau
- 16. Conversion de nombres aléatoires en coordonnées XY pour la représentation graphique
- 17. Transformer la représentation typées d'un DSL dans la représentation typée
- 18. Représentation graphique de nouveaux utilisateurs par date dans une application Rails à l'aide de Seer
- 19. Générer une représentation de schéma graphique à partir de CREATE TABLE SQL
- 20. Représentation graphique d'une ligne et points de dispersion à l'aide de Matplotlib?
- 21. Représentation imprimée de la liste
- 22. Graphique mathématique à l'équation
- 23. Représentation graphique d'une application à l'aide de l'édition Visual Studio 2008 Professional
- 24. Est-il possible d'obtenir une représentation graphique des résultats de gprof?
- 25. conversion de chaîne entre représentation UTF-8 et représentation unicode
- 26. Représentation en treillis du graphe non orienté
- 27. représentation textuelle du contenu du répertoire
- 28. Piston personnaliser la représentation de la réponse
- 29. Représentation visuelle du schéma de base de données
- 30. Représentation numérique d'une couleur
très joli jack, merci beaucoup. Bonne chance avec votre article – Carlos
encore une fois merci mon pote – Carlos
Je n'ai jamais pensé à éliminer la variance dans les repères, c'est probablement une très bonne idée ... – Martin