Как мне реализовать dict с абстрактными базовыми классами в Python?
Я попытался реализовать отображение в Python, используя абстрактный базовый класс MutableMapping, но я получил ошибку при создании экземпляра. Как бы я сделал рабочую версию этого словаря, которая будет подражать встроенному dict класс, насколько это возможно, чтобы быть ясным, с абстрактными базовыми классами?
>>> 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__
Хороший ответ покажет, как заставить это работать, особенно без подклассов dict ( концепция, с которой я довольно хорошо знаком).
5 ответов
Как мне реализовать dict с помощью абстрактных базовых классов?
Хороший ответ покажет, как заставить это работать, особенно без подкласса dict.
Вот сообщение об ошибке: TypeError: Can't instantiate abstract class D with abstract methods __delitem__, __getitem__, __iter__, __len__, __setitem__
Оказывается, нужно реализовать их, чтобы использовать абстрактный базовый класс (ABC), MutableMapping,
Реализация
Поэтому я реализую сопоставление, которое во многих отношениях работает как dict, в котором для сопоставления используется ссылка на атрибут объекта. (Делегирование не то же самое, что наследование, поэтому мы просто делегируем экземпляру __dict__Мы могли бы использовать любое другое специальное сопоставление, но вам, кажется, вас не интересует эта часть реализации. Имеет смысл сделать это таким образом в Python 2, потому что MutableMapping не имеет __slots__ в Python 2, так что вы создаете __dict__ в любом случае. В Python 3 вы могли бы вообще избежать диктов, установив __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__)
демонстрация
И чтобы продемонстрировать использование:
>>> 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]}
И для того, чтобы обеспечить dict API, урок заключается в том, что вы всегда можете проверить collections.MutableMapping:
>>> isinstance(d, collections.MutableMapping)
True
>>> isinstance(dict(), collections.MutableMapping)
True
И хотя dict всегда будет экземпляром MutableMapping из-за регистрации при импорте коллекций, обратное не всегда верно:
>>> isinstance(d, dict)
False
>>> isinstance(d, (dict, collections.MutableMapping))
True
После выполнения этого упражнения мне стало ясно, что использование абстрактных базовых классов обеспечивает только гарантию стандартного API для пользователей класса. В этом случае пользователям, предполагающим наличие объекта MutableMapping, будет гарантирован стандартный API для Python.
Предостережения:
fromkeys Метод конструктора класса не реализован.
>>> 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'
Можно замаскировать встроенные методы dict как get или же setdefault
>>> d['get'] = 'baz'
>>> d.get('get')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object is not callable
Это довольно просто снова разоблачить:
>>> del d['get']
>>> d.get('get', 'Not there, but working')
'Not there, but working'
Но я бы не использовал этот код в производстве.
Демонстрация без диктата, 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__'
Лучший способ продемонстрировать это, не используя dict где-нибудь, вероятно, реализовать что-то очень простое, очень отличается от dict и не совсем бесполезно. Как отображение фиксированного размера фиксированного размера bytes одинакового размера bytes, (Вы можете использовать это, например, для таблицы маршрутизации - она будет гораздо более компактной, чем dict сопоставление распакованных ключей с распакованными значениями, хотя, очевидно, за счет скорости и гибкости.)
Хеш-таблица - это просто массив (hash, key, value) кортежи. Поскольку весь смысл в этом заключается в упаковке данных, мы впихиваем их в struct Это означает, что мы можем просто использовать большой bytearray для хранения. Чтобы пометить слот пустым, мы устанавливаем его значение хэш 0 Что означает, что нам нужно "сбежать" от любого реального 0 превратив его в 1, что глупо, но проще для кода. Мы также будем использовать самый тупой из возможных probe алгоритм для простоты.
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
Как говорится в сообщении об ошибке, вам нужно предоставить реализации для абстрактных методов __delitem__, __getitem__, __iter__, __len__, а также __setitem__, Однако лучшее место для поиска - документы, которые скажут вам, что если вы реализуете эти пять методов (плюс любые другие методы, требуемые базовыми классами, но, как видно из таблицы, их нет), вы получите все остальные методы бесплатно. Возможно, вы не получите наиболее эффективную из всех возможных реализаций, но мы вернемся к этому.
Во-первых, давайте разберемся с __len__, Обычно люди ожидают, что это будет O(1), что означает, что мы должны отслеживать это независимо, обновляя его по мере необходимости. Так:
class FixedDict(collections.abc.MutableMapping):
def __init__(self, elementsize, size):
self.hashtable = FixedHashTable(elementsize, size)
self.len = 0
Сейчас, __getitem__ просто исследует, пока не найдет нужный ключ или не достигнет конца:
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
А также __delitem__ делает то же самое, за исключением того, что очищает слот, если найден, и обновляет 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__ немного сложнее - если найдено, мы должны заменить значение в слоте; если нет, мы должны заполнить пустое место. И здесь мы имеем дело с тем, что хеш-таблица может быть заполнена. И, конечно же, мы должны позаботиться о 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')
И это оставляет __iter__, Так же, как с dict У нас нет определенного порядка, поэтому мы можем просто выполнить итерации слотов хеш-таблицы и получить все непустые:
def __iter__(self):
return (k for (h, k, v) in self.hashtable.fetch(i)
for i in range(self.hashtable.size) if h)
Пока мы на этом, мы могли бы также написать __repr__, Обратите внимание, что мы можем использовать тот факт, что мы получаем items бесплатно:
def __repr__(self):
return '{}({})'.format(type(self).__name__, dict(self.items()))
Тем не менее, обратите внимание, что по умолчанию items просто создает ItemsView(self) и если вы проследите это через источник, вы увидите, что он повторяется self и ищет каждое значение. Очевидно, вы можете добиться большего успеха, если производительность имеет значение:
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)
И аналогично для values и, возможно, другие методы.
По крайней мере
Вы должны реализовать в своем подклассе все абстрактные методы, которые вы наследуете от 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>
более того
Вам необходимо предоставить структуру данных для хранения вашего отображения (хэш, AVL, Red Black) и способ создания словаря.
С MutableMapping в качестве базового класса вы должны сами создать эти методы в своем классе: __delitem__, __getitem__, __iter__, __len__, __setitem__,
Чтобы создать собственный класс dict, вы можете получить его из dict:
>>> class D(dict):
... pass
...
>>> d = D()
>>> d
{}
Вся идея абстрактного базового класса заключается в том, что он имеет несколько членов (чисто виртуальных членов в терминах C++), которые должен предоставить ваш код - в C++ это члены Pure Virtual и другие члены Virtual, которые вы можете переопределить.
Python отличается от C++ тем, что все члены всех классов являются виртуальными и могут быть переопределены (и вы можете добавлять члены ко всем классам и экземплярам), но у абстрактных базовых классов есть некоторые обязательные пропущенные классы, которые эквивалентны чисто виртуальному C++.
Чтобы избавиться от этого, вам просто нужно предоставить недостающие члены, чтобы иметь возможность создать экземпляр вашего производного класса.
В качестве примера того, что вы пытаетесь сделать, смотрите здесь принятый ответ, но вместо того, чтобы использовать диктет в классе, вы должны будете предоставить методы, которые он предоставляет самостоятельно.