Gráfico comparativo representación

Question

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

Answer 1

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

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 aristas, n es el número de vértices y d(vertex) es el número de elementos en la lista de adyacencia vértice .. adj aplicación matriz tiene un O(n²) para añadir y eliminar vértices porque hay que reasignar la matriz. .

Sólo preparado esto para un artículo, por eso lo tengo listo:)

Esto no está directamente relacionado con la evaluación comparativa, ya que por lo general se estudia qué operaciones que en su mayoría necesitan y elige la implementación adecuada para sus necesidades, por lo que es una especie de punto de referencia "teórico" que lo hace mediante el estudio de lo que se va a aplicar . De lo contrario sólo se puede medir el tiempo que necesita su código para hacer todo el trabajo con ambas implementaciones y compararlo.

EDIT:. ya que se utiliza una aplicación matriz dispersa la complejidad de las operaciones de cambio podría ligeramente (en su mayoría conseguir un poco peor, ya que usted está operando de memoria para la velocidad)

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

long before = System.nanoTime();

/* execution of your algorithm */

long elapsed = System.nanoTime() - before;

La respuesta es en nanosegundos y la precisión no está garantizada, a fin de utilizar esto con cuidado. Haciendo un promedio de muchas carreras (y la comprobación de que la varianza es baja, descartando el resultado de que son más distantes de la media) dará coherencia a sus resultados.

Answer 2

Asumiendo que tiene un método adecuado, esto debería ser bastante simple. Simplemente envuelva los dos métodos en un contador de tiempo, y repetir muchas veces para la significación 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"