Las 8 reinas es un problema en el cual se tienen que colocar ocho reinas en un tablero de ajedrez con la condición de que no se ataquen entre sí. Como parte de mi materia de Agentes Inteligentes nos dejaron solucionar este problema utilizando distintos algoritmos de búsqueda en árboles, en este post voy a presentar mis resultados y mi experiencia al momento de estar optimizando el algoritmo, tanto en Java como en Python. El rendimiento se mide en tiempo, no subo el código todavía pero prometo tenerlo pronto.
1.- La primera parte de la entrega consistía en un algoritmo que solucione las ocho reinas sin ninguna consideración especial (o búsqueda a ciegas), lo único “optimizado” es que no genera nodos que sean inválidos (o no pone reinas donde serian atacadas por una que ya estaba antes).
Java
time java ochoreinas.Main
real 0m0.239s
user 0m0.209s
sys 0m0.029s
De acuerdo con el profiler de NetBeans, esta ejecución genera 26093 nodos.
Python
time python _Main.py
real 0m7.666s
user 0m7.616s
sys 0m0.014s
time python Main.py
real 0m1.218s
user 0m1.154s
sys 0m0.009s
De acuerdo con el profiler de python, esta ejecución también genera 26093 nodos (confirmando que el algoritmo esta funcionando igual). La (drástica) diferencia entre _Main.py y Main.py es que uno genera nodos _Nodo, que en su constructor reciben un _Nodo padre y copian las matrices de reinas y posiciones inválidas haciendo uso del modulo copy de python; mientras que el otro genera nodos Nodo, que en su constructor reciben un Nodo padre y copian las matrices “a mano”, esta fue mi primera optimización, o corrección de errores propios (porque tengo mas interés en aprender python que java).
Método __init__ de _Nodo:
def __init__(self, padre=None):if type(padre) == type(self):
self.padre = padre
self.tablero = copy.deepcopy(padre.tablero)
self.invalidos = copy.deepcopy(padre.invalidos)
self.reinas = padre.reinas
Método __init__ de Nodo:
def __init__(self, padre=None):
try:
self.padre = padre
self.tablero = [[j for j in i] for i in padre.tablero]
self.invalidos = [[j for j in i] for i in padre.invalidos]
self.reinas = padre.reinas
except AttributeError:
pass
Conclusiones: algo exagerada la diferencia entre python y java, de hecho cuando vi que python tardaba 7 (casi ocho) segundos en hacer lo que java hace en 0.2 segundos, me decepcione bastante y fue por eso que empesé a buscar alternativas y surgió la idea de esta comparativa.
2.- La segunda parte es lo que el profesor llamo el “algoritmo a*”, básicamente consiste en que al ir generando los nodos y metiéndolos a la cola de nodos por visitar, se van ordenando para que siempre visitemos los nodos con menos espacios restantes para poner las reinas primero, en los dos casos utilicé métodos de ordenamiento que vienen incluidos por default en el lenguaje.
Java
time java ochoreinas.Main
real 0m0.122s
user 0m0.118s
sys 0m0.027s
Python
time python Main.py
real 0m0.069s
user 0m0.061s
sys 0m0.008s
Los dos lenguajes generan 1044 nodos (25 veces menos que en el algoritmo anterior). Para sorpresa mía java tomo casi el doble que python en este caso, la diferencia, supongo, radica en la manera de organizar los nodos creados. En los dos casos se genera una cola temporal a partir de los hijos de un nodo; esta cola es ordenada y después agregada a la cola original que contiene todos los nodos a revisar “a mano”, por lo que no tengo otra conclusión más que “python tiene una mejor implementación de un algoritmo de sort“.
De hecho el método encargado de regresar la comparativa entre dos nodos se ejecuta 1220 veces en python y únicamente 1134 en java; y el método encargado de regresar la cantidad de nodos inválidos (Nodo.cuentaInvalidos()) es llamado 2268 veces en java (el doble que sort) y 2440 en python (nuevamente el doble que sort), algo raro porque generalmente más operaciones implican más tiempo.
Otro punto a considerar es que en Java es necesario generar un objeto comparador cada que se ordena la cola, mientras que en python las listas tienen un muy util metodo sort ya integrado, al cual le pasas la función que reciba dos objetos a comparar y regrese un resultado de -1, 0 o 1 (menor, igual o mayor que).