¿Cómo maneja Python los escenarios de tipo genérico / plantilla? Digamos que quiero crear un archivo externo "BinaryTree.py" y que maneje árboles binarios, pero para cualquier tipo de datos.

Entonces podría pasarle el tipo de un objeto personalizado y tener un árbol binario de ese objeto. ¿Cómo se hace esto en Python?

86
keys 17 jul. 2011 a las 22:30

10 respuestas

La mejor respuesta

Python utiliza duck typing, por lo que no necesita una sintaxis especial para manejar múltiples tipos.

Si proviene de un entorno C ++, recordará que, siempre que las operaciones utilizadas en la función / clase de plantilla estén definidas en algún tipo T (en el nivel de sintaxis), puede usar ese tipo { {X1}} en la plantilla.

Entonces, básicamente, funciona de la misma manera:

  1. defina un contrato para el tipo de elementos que desea insertar en el árbol binario.
  2. documentar este contrato (es decir, en la documentación de la clase)
  3. implementar el árbol binario usando solo las operaciones especificadas en el contrato
  4. disfrutar

Sin embargo, notará que, a menos que escriba una comprobación de tipo explícita (que generalmente se desaconseja), no podrá exigir que un árbol binario contenga solo elementos del tipo elegido.

67
André Caron 17 jul. 2011 a las 18:38

Después de pensar en hacer tipos genéricos en python, comencé a buscar a otros que tuvieran la misma idea, pero no pude encontrar ninguno. Asi que aqui esta. Probé esto y funciona bien. Nos permite parametrizar nuestros tipos en python.

class List( type ):

    def __new__(type_ref, member_type):

        class List(list):

            def append(self, member):
                if not isinstance(member, member_type):
                    raise TypeError('Attempted to append a "{0}" to a "{1}" which only takes a "{2}"'.format(
                        type(member).__name__,
                        type(self).__name__,
                        member_type.__name__ 
                    ))

                    list.append(self, member)

        return List 

Ahora puede derivar tipos de este tipo genérico.

class TestMember:
        pass

class TestList(List(TestMember)):

    def __init__(self):
        super().__init__()


test_list = TestList()
test_list.append(TestMember())
test_list.append('test') # This line will raise an exception

Esta solución es simplista y tiene sus limitaciones. Cada vez que cree un tipo genérico, creará un nuevo tipo. Por lo tanto, varias clases que heredan List( str ) como padre heredarían de dos clases separadas. Para superar esto, debe crear un dict para almacenar las diversas formas de la clase interna y devolver la clase interna creada anteriormente, en lugar de crear una nueva. Esto evitaría la creación de tipos duplicados con los mismos parámetros. Si está interesado, se puede hacer una solución más elegante con decoradores y / o metaclases.

9
Yevhen Kuzmovych 24 sep. 2019 a las 12:48

Dado que Python se escribe dinámicamente, esto es muy fácil. De hecho, tendrías que hacer un trabajo extra para que tu clase BinaryTree no funcione con ningún tipo de datos.

Por ejemplo, si desea que los valores clave que se utilizan para colocar el objeto en el árbol estén disponibles dentro del objeto desde un método como key(), simplemente llame a key() en los objetos. Por ejemplo:

class BinaryTree(object):

    def insert(self, object_to_insert):
        key = object_to_insert.key()

Tenga en cuenta que nunca necesita definir qué tipo de clase es object_to_insert. Siempre que tenga un método key(), funcionará.

La excepción es si desea que funcione con tipos de datos básicos como cadenas o enteros. Tendrás que envolverlos en una clase para que funcionen con tu BinaryTree genérico. Si eso suena demasiado pesado y desea la eficiencia adicional de solo almacenar cadenas, lo siento, eso no es lo que Python es bueno.

3
Leopd 17 jul. 2011 a las 18:36

En realidad ahora puedes usar genéricos en Python 3.5+. Consulte PEP-484 y escribir documentación de la biblioteca.

Según mi práctica, no es muy transparente y claro, especialmente para aquellos que están familiarizados con Java Generics, pero aún son utilizables.

19
8bitjoey 17 sep. 2015 a las 14:12

Si usa Python 2 o desea reescribir el código de Java. Su no es una solución real para esto. Esto es lo que obtengo trabajando en una noche: https://github.com/FlorianSteenbuck/python-generics Todavía no obtengo ningún compilador, así que actualmente lo estás usando así:

class A(GenericObject):
    def __init__(self, *args, **kwargs):
        GenericObject.__init__(self, [
            ['b',extends,int],
            ['a',extends,str],
            [0,extends,bool],
            ['T',extends,float]
        ], *args, **kwargs)

    def _init(self, c, a, b):
        print "success c="+str(c)+" a="+str(a)+" b="+str(b)

TODOS

  • Compiladora
  • Haga que funcionen las clases y los tipos genéricos (para cosas como <? extends List<Number>>)
  • Agregar soporte super
  • Agregar soporte ?
  • Código de limpieza
1
Florian Steenbuck 18 sep. 2018 a las 11:29

Debido a que Python se escribe dinámicamente, los tipos de objetos no importan en muchos casos. Es una mejor idea aceptar cualquier cosa.

Para demostrar lo que quiero decir, esta clase de árbol aceptará cualquier cosa por sus dos ramas:

class BinaryTree:
    def __init__(self, left, right):
        self.left, self.right = left, right

Y podría usarse así:

branch1 = BinaryTree(1,2)
myitem = MyClass()
branch2 = BinaryTree(myitem, None)
tree = BinaryTree(branch1, branch2)
3
Gringo Suave 13 jun. 2015 a las 20:38

Aquí hay una variante de esta respuesta que usa metaclases para evitar la sintaxis desordenada y usa el estilo typing { {X1}} sintaxis:

class template(type):
    def __new__(metacls, f):
        cls = type.__new__(metacls, f.__name__, (), {
            '_f': f,
            '__qualname__': f.__qualname__,
            '__module__': f.__module__,
            '__doc__': f.__doc__
        })
        cls.__instances = {}
        return cls

    def __init__(cls, f):  # only needed in 3.5 and below
        pass

    def __getitem__(cls, item):
        if not isinstance(item, tuple):
            item = (item,)
        try:
            return cls.__instances[item]
        except KeyError:
            cls.__instances[item] = c = cls._f(*item)
            item_repr = '[' + ', '.join(repr(i) for i in item) + ']'
            c.__name__ = cls.__name__ + item_repr
            c.__qualname__ = cls.__qualname__ + item_repr
            c.__template__ = cls
            return c

    def __subclasscheck__(cls, subclass):
        for c in subclass.mro():
            if getattr(c, '__template__', None) == cls:
                return True
        return False

    def __instancecheck__(cls, instance):
        return cls.__subclasscheck__(type(instance))

    def __repr__(cls):
        import inspect
        return '<template {!r}>'.format('{}.{}[{}]'.format(
            cls.__module__, cls.__qualname__, str(inspect.signature(cls._f))[1:-1]
        ))

Con esta nueva metaclase, podemos reescribir el ejemplo en la respuesta a la que enlazo como:

@template
def List(member_type):
    class List(list):
        def append(self, member):
            if not isinstance(member, member_type):
                raise TypeError('Attempted to append a "{0}" to a "{1}" which only takes a "{2}"'.format(
                    type(member).__name__,
                    type(self).__name__,
                    member_type.__name__ 
                ))

                list.append(self, member)
    return List

l = List[int]()
l.append(1)  # ok
l.append("one")  # error

Este enfoque tiene algunos buenos beneficios

print(List)  # <template '__main__.List[member_type]'>
print(List[int])  # <class '__main__.List[<class 'int'>, 10]'>
assert List[int] is List[int]
assert issubclass(List[int], List)  # True
1
Eric 16 nov. 2019 a las 12:53

Las otras respuestas están totalmente bien: no se necesita una sintaxis especial para admitir los genéricos en Python y Python usa la escritura de pato como lo señala André. Sin embargo, si aún desea una variante escrita, hay una solución integrada desde Python 3.5:

from typing import TypeVar, Generic

T = TypeVar('T')

class Stack(Generic[T]):
    def __init__(self) -> None:
        # Create an empty list with items of type T
        self.items: List[T] = []

    def push(self, item: T) -> None:
        self.items.append(item)

    def pop(self) -> T:
        return self.items.pop()

    def empty(self) -> bool:
        return not self.items
# Construct an empty Stack[int] instance
stack = Stack[int]()
stack.push(2)
stack.pop()
stack.push('x')        # Type error

Referencia: documentación de mypy sobre generics.

2
momo 4 ene. 2020 a las 10:36

Mira cómo lo hacen los contenedores incorporados. dict y list y así sucesivamente contienen elementos heterogéneos de cualquier tipo que desee. Si define, digamos, una función insert(val) para su árbol, en algún momento hará algo como node.value = val y Python se encargará del resto.

1
John Zwinck 17 jul. 2011 a las 18:35

Afortunadamente ha habido algunos esfuerzos para la programación genérica en python. Hay una biblioteca: generic

Aquí está la documentación para ello: http://generic.readthedocs.org/en/latest/

No ha progresado en los últimos años, pero puede tener una idea aproximada de cómo usar y hacer su propia biblioteca.

Salud

1
igaurav 25 oct. 2014 a las 06:02