さまざまなコンテナからの効率的な削除を可能にする汎用参照

Question

私はカスタムコンテナクラスを作成しています。構成オブジェクトはコンテナとは独立して作成され、コンテナのないメンバーまたは複数のコンテナのメンバーになることができます。すべてのオブジェクトの上に

• 反復
• 既存のオブジェクト

コンテナはいくつかの追加作業を行うの新しいオブジェクト

除去の挿入、およびその：コンテナの公開APIは、3つの操作をサポートする必要があります正確な実装が変わる可能性があります。

実装を変更しても安定した状態になるように、このクラスにパブリックAPIを書き込むにはどうすればよいですか？

コンテナがlistの場合、効率的な削除にはオブジェクトのインデックスの知識が必要です。オブジェクトそのものが良くないことを知っている（私は要素のコンテナ全体を検索したくない）。

コンテナがsetの場合は、インデックスと同じものは何もありません。オブジェクト自体が必要です。

コンテナが単独でリンクされたリストのようなものなら、削除するオブジェクトの前のオブジェクトへの参照が必要です。

コンテナが二重リンクリストのようなものなら、オブジェクト自体への参照が必要です。

私は除去方法に意味がないか、削除方法の外で使用する単一の引数referenceを取ることを考えています。反復では、（object,reference）のペアが生成されます。

このデザインに問題はありますか？私が見ることができる例やデザインパターンはありますか？

理想的には、元のobjectとreferenceの両方を含み、両方のインターフェイスを示す複雑なオブジェクトを生成することが理想です。しかし、私はこれが実行可能であるとは思わない？

Answer 1

は、他の誰かがよりよい解決策を見つけることによって助けない限り、私がやるものだ：

# to get __hash__ and __eq__ return id(self) 
class Reference: 
    def __init__(self, item): 
    self.item = item 

class RemovalAPI: 
    def add_removal_info(self, item, removal_info): 
    try: 
     references = item.__reference 
    except AttributeError: 
     references = item.__reference = {} 
    references[Reference(self)] = removal_info 

    def get_removal_info(self, item): 
    try: 
     references = item.__reference 
     self_reference = Reference(self) 
     return references[self_reference] 



class Container(list, RemovalAPI): 
    def __iter__(self): 
    for i in range(len(self)): 
     item = self[i] 
     self.add_removal_info(item, i) 
     yield item 

    def remove(self, item): 
    removal_info = self.get_removal_info(item) 
    del self[removal_info] 

    def insert(self, item): 
    self.add_removal_info(item, len(self)) 
    self.append(item) 
    # do whatever post-processing I need 
    # ... 

場合実装をlistから他のデータ構造に変更することを決定した場合、パブリックインターフェイスは変更されないままです。

class Container(orderedset, RemovalAPI): 
    # inheriting __iter__, remove from parent 
    def insert(self, item): 
    self.add(item) 
    # do whatever post-processing I need 
    # ... 

または

class Container(linkedlist, RemovalAPI): 
    def __iter__(self): 
    it = super().__iter__() 
    last_item = None 
    for item in it: 
     self.add_removal_info(item, last_item) 
     yield item 

    def remove(self, item): 
    removal_info = self.get_removal_info(item) 
    if removal_info is None: 
     self.remove_first() 
    else: 
     self.remove_after(removal_info) 

    def insert(self, item): 
    self.add_removal_info(item, None) 
    self.add_to_front(item) 
    # do whatever post-processing I need 
    # ... 

Answer 2

ほとんどのコンテナタイプは、インデックスからインデックス、現在のものから次のものなど、うまく機能するような方向性を持っています。双方向性はありますが、すべてから遠いものもあります。

インデックスを使用せずにPythonリストの値を見つけようとすると、かなり多くO（n）になります。あなたはO（n）を受け入れるか、別のタイプを使用する必要があります。

これに気をつけることの1つは、大量のコンテナタイプから何かをすばやく削除する必要がある場合、値に「ignore_this」属性を追加することができるということです。それをtrueに設定すると、すべてのコンテナタイプが無視され始めます。見たときにコンテナタイプを削除することもできます。

Answer 3

だけでカプセル化しlistとdict/listとset、...

は大雑把にあなたのメモリ使用量と動作時間を倍増、しかし巧妙なカプセル化は、多くの場合、ほぼすべての 問題関連ます操作 O(1)。

Answer 4

あなたは、Python 2.7以上を使用している場合はcollections.OrderedDictを見て価値があるかもしれません。ここでhttp://docs.python.org/library/collections.html#collections.OrderedDict