-2

カスタム コンテナ クラスを作成しています。構成オブジェクトはコンテナとは独立して作成され、コンテナなしまたは複数のコンテナのメンバーになることができます。コンテナーのパブリック API は、次の 3 つの操作をサポートする必要があります。

  • すべてのオブジェクトに対する反復
  • 新しいオブジェクトの挿入
  • 既存のオブジェクトの削除

コンテナーはいくつかの追加作業を行い、その正確な実装は変更される可能性があります。

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

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

コンテナがsetのようなものである場合、インデックスに相当するものはなく、オブジェクト自体が必要です。

コンテナーが単一リンク リストのようなものである場合、オブジェクトを削除する前に、そのオブジェクトへの何らかの参照が必要です。

コンテナーが双方向リンク リストのようなものである場合、オブジェクト自体への参照が必要です。

削除メソッドに単一の引数を取ることを考えていますreference。これは、削除メソッドの外では意味も使用もありません。反復により ( object, reference) のペアが生成されます。

このデザインに問題はありますか？参照できる例または設計パターンはありますか?

理想的には、元のobjectと の両方を含み、両方referenceのインターフェイスを示す複雑なオブジェクトを反復処理で生成したいと考えています。しかし、これは実行可能ではないと思いますか？

4

4 に答える 4

0

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

インデックスを使用せずにPythonリストで値を見つけようとすると、ほとんどO（n）になります。O（n）を採用するか、別のタイプを使用する必要があります。

これについて頭に浮かぶことの1つは、多数のコンテナタイプから何かをまとめてすばやく削除する必要がある場合は、値に「ignore_this」属性を追加できることです。これをtrueに設定すると、すべてのコンテナタイプがそれを無視し始め、表示されたときに削除することさえあります。

于 2012-04-30T22:20:09.887 に答える
0

list aとa dict/alist とa set、..をカプセル化するだけです。

メモリ使用量と操作時間は約2倍になりますが、巧妙なカプセル化により、ほとんどすべての問題関連の操作が行われることがよくありますO(1)。

于 2012-04-30T22:20:42.797 に答える
0

collections.OrderedDictPython 2.7以降を使用している場合は、一見の価値があるかもしれません：http: //docs.python.org/library/collections.html#collections.OrderedDict

于 2012-04-30T22:50:38.810 に答える
0

他の誰かがより良い解決策を見つけて助けない限り、私は次のことを行います。

# 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
    # ...
于 2012-04-30T23:28:34.290 に答える