5

我有什么选择？我需要调用很多appends（到右端）和poplefts（从左端，自然），还需要从存储的中间读取，这将根据算法的性质稳步增长。我想把所有这些操作都放在O(1).

我可以在循环寻址数组（这个词是什么？）上很容易地在 C 中实现它，它会在它满时自动增长；但是 Python 呢？指向其他语言的指针也很受欢迎（我意识到“集合”标签更面向 Java 等，并且希望进行比较，但作为次要目标）。

我来自 Lisp 背景，惊讶地发现在 Python 中从列表中删除头部元素是一个O(n)操作。Adeque可能是一个答案，除了文档说访问O(n)在中间。还有什么，预建的？

4

3 回答 3

7

您可以通过使用两个 python 列表来获得一个摊销的 O(1) 数据结构，一个保存 deque 的左半部分，另一个保存右半部分。前半部分被反转存储，因此双端队列的左端位于列表的后面。像这样的东西：

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]

我不能 100% 确定这段代码与 python 列表的摊销性能之间的交互是否实际上导致每个操作的 O(1)，但我的直觉是这样说的。

于 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 回答