example - python interface

¿Cómo implementaría un dict con Abstract Base Classes en Python?

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo "anular" perfectamente un dict? 5 respuestas

Intenté implementar un mapeo en Python usando la clase base abstracta, MutableMapping, pero recibí un error en la instanciación. ¿Cómo podría hacer una versión de trabajo de este diccionario que emulara la clase dict incorporada, de la forma más clara posible, con Abstract Base Classes ?

>>> class D(collections.MutableMapping):
...     pass
... 
>>> d = D()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Can''t instantiate abstract class D with abstract methods __delitem__, __getitem__, __iter__, __len__, __setitem__

Una buena respuesta demostrará cómo hacer que esto funcione, específicamente sin subclasificar dict ( un concepto con el que estoy bastante familiarizado ).

Answer 1

Con MutableMapping como clase base, debe crear estos métodos usted mismo en su clase: __delitem__, __getitem__, __iter__, __len__, __setitem__ .

Para crear una clase dict personalizada, puedes derivarla de dict:

>>> class D(dict):
...     pass
... 
>>> d = D()
>>> d
{}

Answer 2

Por lo menos

Necesita implementar en su subclase, todos los métodos abstractos que hereda de MutableMapping

class D(MutableMapping):
    def __delitem__(self):
        ''''''
         Your Implementation for deleting the Item goes here
        ''''''
        raise NotImplementedError("del needs to be implemented")
    def __getitem__(self):
        ''''''
         Your Implementation for subscripting the Item goes here
        ''''''
        raise NotImplementedError("obj[index] needs to be implemented")
    def __iter__(self):
        ''''''
         Your Implementation for iterating the dictionary goes here
        ''''''
        raise NotImplementedError("Iterating the collection needs to be implemented")
    def __len__(self):
        ''''''
         Your Implementation for determing the size goes here
        ''''''
        raise NotImplementedError("len(obj) determination needs to be implemented")
    def __setitem__(self):
        ''''''
         Your Implementation for determing the size goes here
        ''''''
        raise NotImplementedError("obj[index] = item,  needs to be implemented")


>>> D()
<__main__.D object at 0x0258CD50>

Además

Debe proporcionar una estructura de datos para almacenar su asignación (hash, AVL, Red Black) y una forma de construir su diccionario.

Answer 3

La mejor manera de demostrar esto sin utilizar un dict cualquier lugar es implementar algo muerto simple, muy diferente de dict , y no completamente inútil. Como una asignación de tamaño fijo de bytes tamaño fijo a bytes tamaño fijo mismo. (Puede usar esto para, por ejemplo, una tabla de enrutamiento; será mucho más compacto que un dict mapeando claves desempaquetadas para valores desempaquetados, aunque obviamente a costa de velocidad y flexibilidad).

Una tabla hash es solo una matriz de tuplas (hash, key, value) . Dado que el objetivo de esto es empaquetar los datos, los incluimos en una struct , lo que significa que podemos usar un bytearray grande para el almacenamiento. Para marcar una ranura vacía, establecemos su valor hash en 0 que significa que necesitamos "escapar" cualquier 0 real convirtiéndolo en un 1 , que es estúpido, pero más simple de codificar. También usaremos el algoritmo de probe más tonto posible para simplificar.

class FixedHashTable(object):
    hashsize = 8
    def __init__(self, elementsize, size):
        self.elementsize = elementsize
        self.size = size
        self.entrysize = self.hashsize + self.elementsize * 2
        self.format = ''q{}s{}s''.format(self.elementsize, self.elementsize)
        assert struct.calcsize(self.format) == self.entrysize
        self.zero = b''/0'' * self.elementsize
        self.store = bytearray(struct.pack(self.format, 0,
                                           self.zero, self.zero)
                               ) * self.size
    def hash(self, k):
        return hash(k) or 1
    def stash(self, i, h, k, v):
        entry = struct.pack(self.format, h, k, v)
        self.store[i*self.entrysize:(i+1)*self.entrysize] = entry
    def fetch(self, i):
        entry = self.store[i*self.entrysize:(i+1)*self.entrysize]
        return struct.unpack(self.format, entry)
    def probe(self, keyhash):
        i = keyhash % self.size
        while True:
            h, k, v = self.fetch(i)
            yield i, h, k, v
            i = (i + 1) % self.size
            if i == keyhash % self.size:
                break

Como dice el mensaje de error, debe proporcionar implementaciones para los métodos abstractos __delitem__ , __getitem__ , __iter__ , __len__ , y __setitem__ . Sin embargo, un mejor lugar para mirar son los documentos , que le dirán que si implementa esos cinco métodos (más cualquier otro método requerido por las clases base, pero como puede ver en la tabla no hay ninguno), obtendrá todos los demás métodos de forma gratuita. Es posible que no obtenga la implementación más eficiente posible de todas ellas, pero volveremos sobre eso.

Primero, tratemos con __len__ . Normalmente las personas esperan que esto sea O (1), lo que significa que debemos hacer un seguimiento de forma independiente, actualizándolo según sea necesario. Asi que:

class FixedDict(collections.abc.MutableMapping):
    def __init__(self, elementsize, size):
        self.hashtable = FixedHashTable(elementsize, size)
        self.len = 0

Ahora, __getitem__ solo prueba hasta que encuentra la clave deseada o llega al final:

    def __getitem__(self, key):
        keyhash = self.hashtable.hash(key)
        for i, h, k, v in self.hashtable.probe(keyhash):
            if h and k == key:
                return v

Y __delitem__ hace lo mismo, excepto que vacía el espacio si se encuentra y actualiza len .

    def __delitem__(self, key):
        keyhash = self.hashtable.hash(key)
        for i, h, k, v in self.hashtable.probe(keyhash):
            if h and k == key:
                self.hashtable.stash(i, 0, self.hashtable.zero, self.hashtable.zero)
                self.len -= 1
                return
        raise KeyError(key)

__setitem__ es un poco más complicado: si lo encontramos, tenemos que reemplazar el valor en la ranura; si no, tenemos que llenar un espacio vacío. Y aquí tenemos que lidiar con el hecho de que la tabla hash puede estar llena. Y, por supuesto, tenemos que encargarnos de len :

    def __setitem__(self, key, value):
        keyhash = self.hashtable.hash(key)
        for i, h, k, v in self.hashtable.probe(keyhash):
            if not h or k == key:
                if not h:
                    self.len += 1
                self.hashtable.stash(i, keyhash, key, value)
                return
        raise ValueError(''hash table full'')

Y eso deja __iter__ . Al igual que con un dict , no tenemos ningún orden en particular, por lo que podemos iterar las ranuras de la tabla hash y obtener todas las no vacías:

def __iter__(self):
    return (k for (h, k, v) in self.hashtable.fetch(i)
            for i in range(self.hashtable.size) if h)

Mientras estamos en eso, también podríamos escribir un __repr__ . Tenga en cuenta que podemos usar el hecho de que obtenemos items gratis:

def __repr__(self):
    return ''{}({})''.format(type(self).__name__, dict(self.items()))

Sin embargo, tenga en cuenta que los items predeterminados solo crean un ItemsView(self) , y si realiza un seguimiento de eso a través de la fuente, verá que se itera y busca cada valor. Obviamente, puedes hacerlo mejor si el rendimiento importa:

def items(self):
    pairs = ((k, v) for (h, k, v) in self.hashtable.fetch(i)
             for i in range(self.hashtable.size) if h)
    return collections.abc.ItemsView._from_iterable(pairs)

Y también para los values , y posiblemente otros métodos.

Answer 4

¿Cómo implementaría un dict con Abstract Base Classes?

Una buena respuesta demostrará cómo hacer que esto funcione, específicamente sin subclasificar dict.

Aquí está el mensaje de error: TypeError: Can''t instantiate abstract class D with abstract methods __delitem__, __getitem__, __iter__, __len__, __setitem__

Resulta que uno debe implementarlos para usar la Clase Base Abstracta (ABC), MutableMapping .

Implementación

Así que implemento un mapeo que funciona como un dict en la mayoría de los aspectos que usa el dict de referencia de atributo del objeto para el mapeo. (La delegación no es lo mismo que la herencia, por lo que solo __dict__ en la instancia __dict__ , podríamos usar cualquier otra asignación ad-hoc, pero no parece importarle esa parte de la implementación. Tiene sentido hacerlo de esta manera en Python 2, porque MutableMapping no tiene __slots__ en Python 2, por lo que está creando un __dict__ . En Python 3, puede evitar los dicts por completo configurando __slots__ .)

import collections

class D(collections.MutableMapping):
    ''''''
    Mapping that works like both a dict and a mutable object, i.e.
    d = D(foo=''bar'')
    and 
    d.foo returns ''bar''
    ''''''
    # ``__init__`` method required to create instance from class.
    def __init__(self, *args, **kwargs):
        ''''''Use the object dict''''''
        self.__dict__.update(*args, **kwargs)
    # The next five methods are requirements of the ABC.
    def __setitem__(self, key, value):
        self.__dict__[key] = value
    def __getitem__(self, key):
        return self.__dict__[key]
    def __delitem__(self, key):
        del self.__dict__[key]
    def __iter__(self):
        return iter(self.__dict__)
    def __len__(self):
        return len(self.__dict__)
    # The final two methods aren''t required, but nice for demo purposes:
    def __str__(self):
        ''''''returns simple dict representation of the mapping''''''
        return str(self.__dict__)
    def __repr__(self):
        ''''''echoes class, id, & reproducible representation in the REPL''''''
        return ''{}, D({})''.format(super(D, self).__repr__(), 
                                  self.__dict__)

Demostración

Y para demostrar el uso:

>>> d = D((e, i) for i, e in enumerate(''abc''))
>>> d
<__main__.D object at 0x7f75eb242e50>, D({''b'': 1, ''c'': 2, ''a'': 0})
>>> d.a
0
>>> d.get(''b'')
1
>>> d.setdefault(''d'', []).append(3)
>>> d.foo = ''bar''
>>> print(d)
{''b'': 1, ''c'': 2, ''a'': 0, ''foo'': ''bar'', ''d'': [3]}

Y para garantizar la API de dict, la lección aprendida es que siempre puedes verificar collections.MutableMapping :

>>> isinstance(d, collections.MutableMapping)
True
>>> isinstance(dict(), collections.MutableMapping)
True

Y aunque un dict siempre será una instancia de un MutableMapping debido a un registro en la importación de colecciones, lo contrario no siempre es cierto:

>>> isinstance(d, dict)
False
>>> isinstance(d, (dict, collections.MutableMapping))
True

Después de realizar este ejercicio, me queda claro que el uso de Clases base abstractas proporciona solo la garantía de una API estándar para los usuarios de la clase. En este caso, los usuarios que asuman un objeto MutableMapping tendrán garantizada la API estándar para Python.

Advertencias:

El método de constructor de la clase fromkeys no está implementado.

>>> dict.fromkeys(''abc'')
{''b'': None, ''c'': None, ''a'': None}
>>> D.fromkeys(''abc'')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: type object ''D'' has no attribute ''fromkeys''

Uno podría enmascarar los métodos dict setdefault como get o setdefault

>>> d[''get''] = ''baz''
>>> d.get(''get'')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ''str'' object is not callable

Es bastante simple de desenmascarar de nuevo:

>>> del d[''get'']
>>> d.get(''get'', ''Not there, but working'')
''Not there, but working''

Pero no usaría este código en producción.

Demostración sin un dict, Python 3:

>>> class MM(MutableMapping):
...   __delitem__, __getitem__, __iter__, __len__, __setitem__ = (None,) *5
...   __slots__ = ()
...
>>> MM().__dict__
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: ''MM'' object has no attribute ''__dict__''

Answer 5

La idea general de una clase base abstracta es que tiene algunos miembros, (miembros virtuales puros en términos de C ++), que su código debe suministrar: en C ++ estos son los miembros Pure Virtual y otros miembros virtuales que puede anular.

Python difiere de C ++ en que todos los miembros de todas las clases son Virtuales y pueden ser reemplazados (y puede agregar miembros a todas las clases e instancias) pero las Clases Base Abstractas tienen algunas clases requeridas que faltan, estas son equivalentes a las virtuales C ++.

Habiendo solucionado esto, solo necesita proporcionar los miembros faltantes para poder crear una instancia de su clase derivada.

Para ver un ejemplo del tipo de cosas que intenta hacer, vea la respuesta aceptada aquí, pero en lugar de usar un dictado dentro de la clase, tendrá que proporcionar los métodos que se le proporcionan.