Buen estilo en objetos de Python

La mayor parte de mi progtwigción anterior a Python estaba en C ++ o Matlab. No tengo un título en CS (casi completé un doctorado en física), pero he hecho algunos cursos y una buena cantidad de progtwigción real. Ahora, estoy tomando un curso de algoritmos en Coursera (excelente curso, por cierto, con un profesor de Stanford). Decidí implementar las tareas en Python. Sin embargo, a veces me encuentro con ganas de cosas que el lenguaje no admite tan fácilmente. Estoy muy acostumbrado a crear clases y objetos para cosas en C ++ solo para agrupar datos (es decir, cuando no hay métodos). Sin embargo, en Python, donde puedes agregar campos sobre la marcha, lo que básicamente acabo de querer todo el tiempo son las estructuras de Matlab. Creo que esto es posiblemente una señal de que no estoy usando un buen estilo y haciendo las cosas a la manera “pythonica”.

Debajo está mi implementación de una estructura de datos de búsqueda de unión (para el algoritmo de Kruskal). Aunque la implementación es relativamente corta y funciona bien (no hay mucha comprobación de errores), hay algunos puntos extraños. Por ejemplo, mi código asume que los datos que se pasaron originalmente a union-find son una lista de objetos. Sin embargo, si en su lugar se pasa una lista de datos explícitos (es decir, una lista de entradas), el código falla. ¿Hay alguna forma mucho más clara y más python de implementar esto? He intentado buscar en Google esto, pero la mayoría de los ejemplos son muy simples y se relacionan más con el código de procedimiento (es decir, la forma “adecuada” de hacer un bucle for en python).

class UnionFind: def __init__(self,data): self.data = data for d in self.data: d.size = 1 d.leader = d d.next = None d.last = d def find(self,element): return element.leader def union(self,leader1,leader2): if leader1.size >= leader2.size: newleader = leader1 oldleader = leader2 else: newleader = leader2 oldleader = leader1 newleader.size = leader1.size + leader2.size d = oldleader while d != None: d.leader = newleader d = d.next newleader.last.next = oldleader newleader.last = oldleader.last del(oldleader.size) del(oldleader.last) 

En términos generales, hacer este tipo de cosas Pythonically significa que intenta hacer que a su código no le importe lo que se le da, al menos no más de lo que realmente necesita.

Tomemos su ejemplo particular del algoritmo de búsqueda de unión. Lo único que el algoritmo de búsqueda de unión realmente hace con los valores que le pasas es compararlos para la igualdad. Por lo tanto, para hacer una clase UnionFind generalmente útil, su código no debe confiar en los valores que recibe y que tienen cualquier otro comportamiento que no sea la prueba de igualdad. En particular, no debe confiar en poder asignar atributos arbitrarios a los valores.

La forma en que sugeriría solucionar esto es hacer que UnionFind use objetos de envoltura que contengan los valores dados y los atributos que necesita para hacer que el algoritmo funcione. Puede usar namedtuple como lo sugiere otra respuesta, o hacer una clase de envoltorio pequeño. Cuando se agrega un elemento a UnionFind , primero lo envuelve en uno de estos objetos, y usa el objeto envoltorio para almacenar los atributos leader , size , etc. La única vez que accede al objeto que está siendo envuelto es para verificar si es igual a otro valor.

En la práctica, al menos en este caso, debería ser seguro asumir que sus valores son hashables, de modo que puede usarlos como claves en un diccionario de Python para encontrar el objeto envoltorio correspondiente a un valor dado. Por supuesto, no todos los objetos en Python son necesariamente modificables, pero los que no lo son son relativamente raros y será mucho más trabajo hacer una estructura de datos que sea capaz de manejarlos.

La forma más pythonica es evitar los objetos tediosos si no es necesario.

 class UnionFind(object): def __init__(self, members=10, data=None): """union-find data structure for Kruskal's algorithm members are ignored if data is provided """ if not data: self.data = [self.default_data() for i in range(members)] for d in self.data: d.size = 1 d.leader = d d.next = None d.last = d else: self.data = data def default_data(self): """create a starting point for data""" return Data(**{'last': None, 'leader':None, 'next': None, 'size': 1}) def find(self, element): return element.leader def union(self, leader1, leader2): if leader2.leader is leader1: return if leader1.size >= leader2.size: newleader = leader1 oldleader = leader2 else: newleader = leader2 oldleader = leader1 newleader.size = leader1.size + leader2.size d = oldleader while d is not None: d.leader = newleader d = d.next newleader.last.next = oldleader newleader.last = oldleader.last oldleader.size = 0 oldleader.last = None class Data(object): def __init__(self, **data_dict): """convert a data member dict into an object""" self.__dict__.update(**data_dict) 

Una opción es usar diccionarios para almacenar la información que necesita sobre un elemento de datos, en lugar de atributos directamente en el elemento. Por ejemplo, en lugar de referirse a d.size , puede referirse a size[d] (donde size es una instancia de dict ). Esto requiere que sus elementos de datos sean hashable, pero no necesitan permitir que se asignen atributos en ellos.

Aquí hay una traducción directa de su código actual para usar este estilo:

 class UnionFind: def __init__(self,data): self.data = data self.size = {d:1 for d in data} self.leader = {d:d for d in data} self.next = {d:None for d in data} self.last = {d:d for d in data} def find(self,element): return self.leader[element] def union(self,leader1,leader2): if self.size[leader1] >= self.size[leader2]: newleader = leader1 oldleader = leader2 else: newleader = leader2 oldleader = leader1 self.size[newleader] = self.size[leader1] + self.size[leader2] d = oldleader while d != None: self.leader[d] = newleader d = self.next[d] self.next[self.last[newleader]] = oldleader self.last[newleader] = self.last[oldleader] 

Un caso de prueba mínimo:

 >>> uf = UnionFind(list(range(100))) >>> uf.find(10) 10 >>> uf.find(20) 20 >>> uf.union(10,20) >>> uf.find(10) 10 >>> uf.find(20) 10 

Más allá de esto, también podría considerar cambiar un poco su implementación para requerir menos inicialización. Aquí hay una versión que no hace ninguna inicialización (ni siquiera necesita saber el conjunto de datos en los que va a funcionar). Utiliza la compresión de ruta y la unión por rango en lugar de mantener siempre un valor leader actualizado para todos los miembros de un conjunto. Debe ser asintóticamente más rápido que su código actual, especialmente si está haciendo muchas uniones:

 class UnionFind: def __init__(self): self.rank = {} self.parent = {} def find(self, element): if element not in self.parent: # leader elements are not in `parent` dict return element leader = self.find(self.parent[element]) # search recursively self.parent[element] = leader # compress path by saving leader as parent return leader def union(self, leader1, leader2): rank1 = self.rank.get(leader1,1) rank2 = self.rank.get(leader2,1) if rank1 > rank2: # union by rank self.parent[leader2] = leader1 elif rank2 > rank1: self.parent[leader1] = leader2 else: # ranks are equal self.parent[leader2] = leader1 # favor leader1 arbitrarily self.rank[leader1] = rank1+1 # increment rank 

Para verificar si un argumento es del tipo esperado, use la función incorporada isinstance() :

 if not isinstance(leader1, UnionFind): raise ValueError('leader1 must be a UnionFind instance') 

Además, es un buen hábito agregar cadenas de documentación a funciones, clases y funciones miembro. Dicha cadena de documentos para una función o método debe describir lo que hace, qué argumentos se le pasarán y, si corresponde, qué se devuelve y qué excepciones se pueden generar.

Supongo que los problemas de sangrado aquí son solo errores simples al ingresar el código en SO. ¿Podrías crear una subclase de un tipo de datos simple e integrado? Por ejemplo, puede crear una subclase del tipo de datos de la lista colocando el tipo de datos entre paréntesis:

 class UnionFind(list): '''extends list object'''