Representación gráfica del benchmarking

Question

Actualmente estoy desarrollando un programa que resuelve (si es posible) cualquier laberinto dado de dimensiones de 3X4 a 26x30. Represento el gráfico usando tanto la matriz adj (escasa) como la lista adj. Me gustaría saber cómo generar el tiempo total que toma el DFS para encontrar la solución usando uno y luego el otro método. Programativamente, ¿cómo podría producir tal punto de referencia?

Answer 1

Una tabla útil para trabajar con varias implementaciones gráficos:

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

donde m es el número de bordes, n es el número de vértices y d(vertex) es el número de elementos en la adyacencia vértice lista .. la implementación de la matriz adj tiene un O(n²) para agregar y quitar vértices porque tiene que reasignar la matriz ..

Acabo de preparar esto para un artículo, por eso lo tengo listo :)

Esto no está directamente relacionado con la evaluación comparativa, ya que normalmente estudia qué operaciones necesitará principalmente y elige la implementación correcta para sus necesidades, por lo que es una especie de punto de referencia "teórico" al estudiar lo que van a implementar. De lo contrario, puede medir el tiempo que su código necesita para hacer todo el trabajo con ambas implementaciones y compararlo.

EDIT: Dado que utiliza una implementación de matriz dispersa, la complejidad de las operaciones podría cambiar ligeramente (sobre todo empeorar un poco, ya que está intercambiando memoria por la velocidad).

Edit2: bien, ahora que sé que esto es Java será fácil justo:

long before = System.nanoTime(); 

/* execution of your algorithm */ 

long elapsed = System.nanoTime() - before; 

respuesta es en nanosegundos y la precisión no está garantizada, a fin de utilizar esto con cuidado. Hacer un promedio de muchas ejecuciones (y comprobar que la varianza es baja, descartando el resultado que está más alejado del promedio) dará coherencia a sus resultados.

Answer 2

Suponiendo que tiene un método adecuado, esto debería ser bastante simple. Simplemente ajuste ambos métodos en un temporizador y repítelo varias veces para obtener significancia estadística.

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