5

そこに私のオプションは何ですか？たくさんのappends（右端から）とpoplefts（左端から当然）を呼び出す必要がありますが、アルゴリズムの性質上、着実に増大するストレージの中央から読み取る必要もあります。これらすべての操作をで行いたいと思いO(1)ます。

循環アドレス配列（単語は何ですか？）にCで簡単に実装できます。配列は、いっぱいになると自動的に大きくなります。しかし、Pythonはどうですか？他の言語へのポインタも高く評価されています（「collections」タグはJavaなどを重視していることを認識しており、比較をいただければ幸いですが、副次的な目標です）。

私はLispのバックグラウンドを持っていて、Pythonではリストからhead要素を削除することが操作であることを知って驚いていましたO(n)。dequeドキュメントにアクセスがO(n)途中であると記載されている場合を除いて、 Aが答えになる可能性があります。事前に構築されたものは他にありますか？

4

3 に答える 3

7

2つのPythonリストを使用して、償却されたO（1）データ構造を取得できます。1つは両端キューの左半分を保持し、もう1つは右半分を保持します。前半分は逆に格納されるため、両端キューの左端がリストの最後になります。このようなもの：

class mydeque(object):

  def __init__(self):
    self.left = []
    self.right = []

  def pushleft(self, v):
    self.left.append(v)

  def pushright(self, v):
    self.right.append(v)

  def popleft(self):
    if not self.left:
      self.__fill_left()
    return self.left.pop()

  def popright(self):
    if not self.right:
      self.__fill_right()
    return self.right.pop()

  def __len__(self):
    return len(self.left) + len(self.right)

  def __getitem__(self, i):
    if i >= len(self.left):
      return self.right[i-len(self.left)]
    else:
      return self.left[-(i+1)]

  def __fill_right(self):
    x = len(self.left)//2
    self.right.extend(self.left[0:x])
    self.right.reverse()
    del self.left[0:x]

  def __fill_left(self):
    x = len(self.right)//2
    self.left.extend(self.right[0:x])
    self.left.reverse()
    del self.right[0:x]

このコードとPythonのリストの償却パフォーマンスとの相互作用が、実際に各操作でO（1）になるかどうかは、100％わかりませんが、私の直感ではそう言っています。

于 2012-05-04T17:19:50.740 に答える
3

Lispリストの真ん中にアクセスすることもO（n）です。

Pythonlistは配列リストであるため、ヘッドをポップするのはコストがかかります（テールをポップするのは一定時間です）。

探しているのは、先頭に（償却された）定数時間の削除がある配列です。つまり、基本的には、list遅延削除を使用するデータ構造を構築する必要があり、キューが空のときに遅延削除されたスロットをリサイクルできることを意味します。

または、ハッシュテーブルといくつかの整数を使用して、現在の連続するキーの範囲を追跡します。

于 2012-05-04T17:13:04.753 に答える
0

アクセスがであるかどうかはわかりませんが、PythonのキューモジュールO(1)が役立つ場合があります。

于 2012-05-04T17:13:22.490 に答える