Named Tuples en Python
La programación orientada a objetos se basa en asociar en un mismo elemento (un objeto) tanto un estado como las operaciones asociadas a dicho estado. Como dice Martin Fowler:
In programming, the fundamental notion of an object is the bundling of data and behavior.
Como resultado de dichas operaciones podremos obtener, o bien el mismo objeto con distinto estado1, o bien un objeto distinto con el estado modificado. Obviamente habrá operaciones, como pueden ser imprimir u obtener el hash de un objeto, que no devuelvan ningún resultado o modifiquen el estado del objeto con el que estemos trabajando.
Es muy típico que, en ocasiones, lo único que nos interese sea tener una serie de datos dentro de un contenedor por estar relacionados entre sí. Para almacenar dichos datos podemos usar estructuras de datos. Si queremos acceder a ellos emplearemos formas distintas según la estructura: en el caso de que simplemente queramos almacenarlos en un contenedor secuencial (lista, vector, etc) usaremos los índices de los elementos.
Si por ejemplo queremos almacenar los datos de los nodos de un grafo, en los cuales almacenamos tanto un estado asociado a cada nodo, como un enlace al nodo que generó el nodo actual (el padre del nodo), la profundidad a la que se encuentra cada nodo en el grafo, y su coste, para acceder a sus elementos empleando índices haremos:
node = [state father d c] node-state = node[0] node-father = node[1] node-depth = node[2] node-cost = node[3]
Esto tiene varios problemas:
- necesitamos una estructura de datos que nos permita almacenar elementos de distinto tipo2; y
- la forma de acceder a los elementos del nodo dista mucho de ser cómoda y/o legible.
Por estos motivos, es bastante común el uso de objetos3. Esta solución es tan habitual que en Kotlin tenemos el concepto de data class, las cuales simplemente sirven como almacén de datos heterogéneos. Incluso en Scala es bastante común el uso de case class únicamente con atributos, sin definir ningún método.
Pero esta solución no es (imo) correcta. Ni conceptualmente, ni a nivel de coste: tanto la creación de objetos como el acceso a sus atributos distan mucho de ser arbitrarias computacionalmente hablando, y son desde luego mucho más costosas que el acceso a las posiciones correlativas de una estructura de datos secuencial.
Sobre todo esto, la legibilidad y el rendimiento de las distintas opciones que encontramos en Python para el almecenamiento de los atributos de alguna entidad, es de lo que he venido a hablar hoy aquí. Para poder medir el tiempo de ejecución usaremos la siguiente función:
def time_measurement_loop(f, times=100000): @wraps(f) def measure_time(*args, **kwargs): total_time = 0 t_loop = sys.maxsize t0 = time.time() for idx in range(times): t1 = time.time() res = f(*args, **kwargs) t2 = time.time() t = t2 - t1 if t_loop > t: t_loop = t total_time = t2 - t0 print("-----------------------------") print("@time_measurement: [{}]".format(f.__name__)) print("\t{} executions take {} s".format(times, total_time)) print("\ttotal loops: {}".format(times)) print("\tthe best loop takes {} s".format(t_loop)) print("-----------------------------") return total_time return measure_time def wrap(times): def deco(fn): return time_measurement_loop(fn, times) return deco
Opciones para almacenamiento heterogéneo
Vamos a hablar de algunas de las opciones más comunes que Python nos ofrece. Nos dejamos algunas, como por ejemplo crear una clase a partir de los struct de C, no por que no sea útil, sino porque jamás la he empleado. Tampoco tiene sentido emplear otras estructuras de datos secuenciales como deque, las cuales para este problema no nos aportan ventaja respecto a las listas o tuplas.
Objetos
Definamos primero la clase descrita anteriormente:
class Node(object): def __init__(self, state, father=None, depth=0, cost=0): self.__state = state self.__father = father self.__depth = depth self.__cost = cost @property def state(self): return self.__state @state.setter def state(self, value): self.__state = value # The other attributes will have also the same kind of getter/setter methods. ...
Aunque todos sabemos como, dejemos constancia de cómo crear un nodo y acceder a sus atributos:
node = Node((1, 2, 3, 4), Node(0, 0, 0), 1) state, father, depth, cost = node.state, node.father, node.depth, node.cost node == node.father node.state = (4, 3, 2, 1)
y Diccionarios
:CUSTOMID: diccionarios
Otra opción que podemos emplear es un diccionario. Creo sinceramente que son el mayor hallazgo del lenguaje, y que su facilidad de creación y uso son de largo más sencillas que las de la estructura equivalente en cualquier otro lenguaje en los que tengo un mínimo de experiencia.
Para crear un nodo equivalente al anterior mediante la definición de una clase, crearemos un diccionario en el cual las claves serán los nombre de los atributos, y los valores obviamente los valores que tomará cada uno de ellos:
node = { "state": (1, 2, 3, 4), "father": {"state": (0, 0, 0, 0), "father": None, "depth": 0, "cost": 0}, "depth": 1, "cost": 0} state, father = node["state"], node["father"] depth, cost = node["depth"], node["cost"] node == node["father"] node["state"] = (4, 3, 2, 1)
Esta opción, para este caso concreto, tiene serias desventajas:
- la referencia al padre se pierde si reusamos el nombre del objeto en la creación de los nodos (si no tenemos que guardar referencia a otro elemento previo, no tendremos ningún problema);
- es bastante más verbosa, y facilita mucho el cometer errores; y
- si trabajamos con un ide o con algún plugin para facilitar la escritura de código, no tendremos ayuda a la hora de mostrar los elementos existentes.
Como ventaja… es más eficiente. Aunque en este caso no es útil (por el problema comentado de la reutilización de referencias), en otros casos será la estructura a elegir.
y Listas-tuplas
:CUSTOMID: listas-tuplas
Poco que explicar, la diferencia entre ambas (mutable/inmutable) nos hará cambiar la forma de trabajar, pero el acceso será igual:
node = [(1, 2, 3, 4), [(0, 0, 0, 0), None, 0, 0], 1, 0] [state, father, depth, cost] = node node == node[1] node[0] = (4, 3, 2, 1) # If we use tuples... node = ((4, 3, 2, 1), node[1], node[2], node[3])
Las desventajas son parecidas a las del diccionario:
- imposibilidad de llevar registro de nodos anteriores;
- poca legibilidad a la hora acceder a los elementos; y
- no poder disfrutar de las ventajas de entornos de desarrollo o plugins, por lo tanto mayor tendencia a cometer errores.
La ventaja, igual que con el diccionario, es la eficiencia. Si necesitamos reasignar valores a una tupla, como el proceso será crear una nueva con el mismo nombre a partir de la antigua con los valores modificados, será más eficiente la lista. En caso de no necesitar reasignar, será más eficiente la tupla. Podemos resumirlo diciendo que si en el primer caso optaremos pr la lista, y en el segundo por la tupla.
y Tuplas con nombre
:CUSTOMID: tuplas-con-nombre
Las tuplas con nombre o namedtuple nos van a permitir acceder a los elementos almacenados en las mismas tanto con el índice como con el nombre de los campos. En este caso se empleará la dot notation4 típica de la programación orientada a objetos, por lo que el código será muchísimo más legible.
Para trabajar con ellas, la importaremos del módulo correspondiente, y crearemos una especie de constructor que nos servirá para crearlas. A este constructor hemos de pasar tanto el nombre de la estructura (lo que vendría siendo el nombre de la clase) como los nombres de los campos por los cuales queremos acceder a las posiciones dentro de la tupla:
from collections import namedtuple Node = namedtuple('Node', ['state', 'father', 'depth', 'cost']) root = Node((), None, 0, 0) node = Node((1), root, root.depth + 1, root[3] + 1)
Hemos visto como en efecto podemos acceder de ambas formas a los atributos. También, a la hora de crear las instancias, podemos emplear keywords:
node = Node(state=(1), father=root, depth=root.depth+1, cost=root.cost+1)
Como siempre en Python, una vez empleamos palabras clave hemos de emplearlas hasta el final. Esto es, podemos emplear campos posicionales hasta el momento en que empleamos keywords, momento a partir del cual estamos obligados a usar éstas. Por eso esto es correcto:
node = Node((1), root, depth=root.depth+1, cost=root.cost+1)
pero esto no:
node = Node(state=(1), father=root, root.depth+1, root.cost+1)
Para más información, nada mejor que la documentación del lenguaje.
Resultados
Para medir el rendimiento de cada estructura, vamos a emplear las siguientes funciones (adaptadas a cada una de las estructuras empleadas):
# With reassignment @wrap(rep) def class_way(): node = Node((5, 6, 7, 8), root_node, root_node.depth + 1, root_node.cost + 1) node.state = tuple([e**5 for e in root_node.state]) node == node.father # Without reassignment @wrap(rep) def class_way(): node = Node((5, 6, 7, 8), root_node, root_node.depth + 1, root_node.cost + 1) state = tuple([e**5 for e in root_node.state]) node == node.father
Como una imagen vale más que mil palabras, en las siguientes podemos ver los resultados obtenidos al ejecutar el código presente en este notebook de ipython:
Figure 1: con reasignación
Vemos como, al haber reasignación, las tuplas con nombre tienen el peor comportamiento, con un rendimiento peor incluso que la solución empleando objetos. Aunque esto ocurre para un número elevado de repeticiones de la operación (aproximadamente a partir de 200000 operaciones). En este caso, tal y como dijimos, la lista tiene mejor comportamiento que la tupla, al requerir esta la creación de una nueva cada vez que queremos llevar a cabo un cambio en algún valor.
Figure 2: sin reasignación
En cambio, cuando no hay reasignación, las tuplas con nombre trabajan mucho mejor que la solución empleando objetos y, aunque funcionan peor que diccionarios y estructuras secuenciales básicas, la mejora en la legibilidad hacen muy recomendable su uso.
Conclusión
He intentado con este artículo dar a conocer un elemento que, aunque goza de mucha publicidad (y artículos) en literatura anglosajona, no está tan presente en blogs en español.
Sinceramente recomiento su uso, la mejora en el rendimiento es enorme frente a objetos, y en aplicaciones de cálculo intensivo (por ejemplo en problemas de búsqueda, juegos o cálculo numérico), puede convertir un código inutilizable, por lento, en un programa aceptable. En mi caso, en la resolución en su momento del algoritmo minimax, supuso una mejora sustancial.
Notas
Podríamos discutir si, ante estados distintos (si tenemos distintos atributos), estamos ante el mismo objeto, o por contra estamos ante objetos distintos. De hecho, al comparar objetos, si definimos la función de igualdad como igualdad de sus atributos, obviamente estaremos ante objetos distintos. Obviamente me refiero aquí, por igualdad, a que la referencia es la misma, esto es, a que lo que almacenamos en el stack no varía, aunque sí lo hagan los datos en el heap.
En python nos servirán tanto la lista como la tupla para este fin. En otros lenguajes, como Java o C, esto es bien imposible bien bastante costoso, con uso de arrays de punteros a void y conversión entre tipos cada vez que queremos acceder a algún valor.
Obviamente no en C, pero en él disponemos de los struct para este fin.
Sinceramente no sé cómo traducir esta expresión.