抽象基底クラス MutableMapping を使用して Python でマッピングを実装しようとしましたが、インスタンス化でエラーが発生しました。Abstract Base Classesdictを使用して、できるだけ多くの方法で組み込みクラスをエミュレートするこの辞書の作業バージョンを作成するにはどうすればよいですか?
>>> 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（私がよく知っている概念）。
どこでも実際に使用せずにこれを実証する最良の方法dictは、おそらく非常に単純で、 とは非常に異なり、dict完全に役に立たないものを実装することです。bytesfixed-sizeから same-fixed- size への固定サイズのマッピングのようにbytes。dict(これは、たとえばルーティング テーブルに使用できます。明らかに速度と柔軟性が犠牲になりますが、アンパックされたキーをアンパックされた値にマッピングするよりもはるかにコンパクトになります。)
ハッシュ テーブルは単なる(hash, key, value)タプルの配列です。これの要点はデータを詰め込むことなので、それらを に詰め込みますstruct。つまり、大きなbytearrayものをストレージに使用できます。スロットを空としてマークするには、そのハッシュ値を — に設定します。これは、実数を に変換して0「エスケープ」する必要があることを意味します。簡単にするために、可能な限り最も馬鹿げたアルゴリズムも使用します。01probe
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__。ただし、より適切な場所は docsです。これらの 5 つのメソッド (および基本クラスに必要なその他のメソッド。ただし、表からわかるように、何もありません) を実装すると、次のようになります。他のすべての方法は無料です。それらすべてを可能な限り効率的に実装することはできないかもしれませんが、それについては後で説明します。
まず、対処しましょう__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
And__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__ます。a と同じように、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、レッド ブラック) を格納するためのデータ構造と、辞書を作成する方法を提供する必要があります。
抽象基本クラスの全体的な考え方は、コードが提供する必要があるいくつかのメンバー (C++ 用語では純粋仮想メンバー) を持っているということです。C++ では、これらは純粋仮想メンバーと、オーバーライドできる他の仮想メンバーです。
Python は、すべてのクラスのすべてのメンバーが Virtual であり、オーバーライドされる可能性があるという点で C++ とは異なります (そして、すべてのクラスとインスタンスにメンバーを追加できます) が、Abstract Base クラスにはいくつかの必要な欠落クラスがあり、これらは C++ の純粋な仮想と同等です。
それが終わったら、不足しているメンバーを提供して、派生クラスのインスタンスを作成できるようにするだけです。
あなたがしようとしている種類の例については、ここで受け入れられた回答を参照してください。ただし、クラス内でdictを使用するのではなく、それが提供するメソッドを提供する必要があります。