El grupo de Samuel consiguió, en el primer nivel del laberinto, que el cálculo del camino más largo pasara de hacerse en 16 segundos a hacerse en menos de un segundo sin bajada de frames con este cambio:
Implementación del BinaryHeap: la clase BinaryHeap, que intenta simular un montículo binario para mantener los elementos ordenados, es altamente ineficiente y es de hecho el principal cuello de botella en el rendimiento, principalmente porque no está funcionando como un monticulo binario, sino es un array que se ordena en cada cambio de datos internos. Por lo tanto las operaciones de inserción/eliminación en lugar de ser O(log n) como serían en un montículo, son de orden O(n log n), lo cual provoca un impacto brutal en el rendimiento. La solución a este problema es cambiar el uso de BinaryHeap en las listas de open y closed por la clase SortedSet , que viene implementada "de base" en C# y garantiza inserciones/eliminaciones en O (log N),además la consulta del top del montículo, se puede cambiar por set.Min, que devuelve el mínimo elemento del set , lo cual en nuestro caso es exactamente lo mismo y justo lo que necesitamos
Nota: si bien es cierto que esta solución es más que suficiente para las necesidades de la práctica, si por algún motivo se deseara mantener el uso de un montículo binario, para por ejemplo acceder a los elementos por índice(cosa que al menos en nuestra implementación de la práctica no hemos necesitado) habría que cambiar la implementación interna y aplicar operaciones de flotar y hundir elementos (como hemos visto en MARP) por el montículo en lugar de usar Array.Sort , que es lo que se utiliza actualmente, para así poder tener un coste O(log n)
Otra opción, entiendo, es recurrir al PriorityQueue de C# que dijimos...
El grupo de Samuel consiguió, en el primer nivel del laberinto, que el cálculo del camino más largo pasara de hacerse en 16 segundos a hacerse en menos de un segundo sin bajada de frames con este cambio:
Implementación del BinaryHeap: la clase BinaryHeap, que intenta simular un montículo binario para mantener los elementos ordenados, es altamente ineficiente y es de hecho el principal cuello de botella en el rendimiento, principalmente porque no está funcionando como un monticulo binario, sino es un array que se ordena en cada cambio de datos internos. Por lo tanto las operaciones de inserción/eliminación en lugar de ser O(log n) como serían en un montículo, son de orden O(n log n), lo cual provoca un impacto brutal en el rendimiento. La solución a este problema es cambiar el uso de BinaryHeap en las listas de open y closed por la clase SortedSet , que viene implementada "de base" en C# y garantiza inserciones/eliminaciones en O (log N),además la consulta del top del montículo, se puede cambiar por set.Min, que devuelve el mínimo elemento del set , lo cual en nuestro caso es exactamente lo mismo y justo lo que necesitamos
Nota: si bien es cierto que esta solución es más que suficiente para las necesidades de la práctica, si por algún motivo se deseara mantener el uso de un montículo binario, para por ejemplo acceder a los elementos por índice(cosa que al menos en nuestra implementación de la práctica no hemos necesitado) habría que cambiar la implementación interna y aplicar operaciones de flotar y hundir elementos (como hemos visto en MARP) por el montículo en lugar de usar Array.Sort , que es lo que se utiliza actualmente, para así poder tener un coste O(log n)
Otra opción, entiendo, es recurrir al PriorityQueue de C# que dijimos...