7

Python 类有六个要求，如下所示。只有粗体字才能被解读为要求。

  1. 以下四个操作中的许多操作的性能接近O(1) 。
  2. 在将对象插入容器时保持排序顺序。
  3. 能够查看对象中包含的最后一个值（最大值）。
  4. 允许两侧弹出（获取最小值或最大值）。
  5. 获取正在存储的对象的总大小或数量的能力。
  6. 作为一个现成的解决方案，就像 Python 标准库中的代码一样。

以下内容出于历史原因留在这里（帮助好奇并证明进行了研究）。

在查看了 Python 的标准库（特别是关于数据类型的部分）之后，我仍然没有找到一个满足分片表要求的类。collections.deque接近要求，但不支持保持其中包含的数据排序。它提供：

  1. 在具有O(1) 性能的双端队列的任一侧进行高效的追加和弹出。
  2. 对象中包含的数据的两侧弹出。
  3. 获取其中包含的对象的总大小或计数。

使用列表实现一个低效的解决方案将是微不足道的，但找到一个表现良好的类将是更可取的。在没有上限的不断增长的内存模拟中，这样的类可以保持空（已删除）单元格的索引并降低碎片级别。该bisect模块可能有助于：

  1. 帮助在数组中插入新对象时保持数组的排序。
  2. 在添加对象时保持列表排序的现成解决方案。
  3. 将允许执行array[-1]以查看数组中的最后一个值。

未能完全满足要求并且看起来最没有希望的最终候选是该heapq模块。虽然支持看似有效的插入并确保这array[0]是最小值，但数组并不总是处于完全排序的状态。没有其他任何东西有帮助。

有谁知道 Python 中接近这六个要求的类或数据结构？

4

3 回答 3

12

您的要求似乎是：

  1. O(1) 从每一端弹出
  2. 高效的len
  3. 排序顺序
  4. 查看最后一个值

您可以将 a与旋转双端队列、附加到一端并取消旋转deque的自定义方法一起使用。insert

>>> from collections import deque
>>> import bisect
>>> class FunkyDeque(deque):
...     def _insert(self, index, value):
...             self.rotate(-index)
...             self.appendleft(value)
...             self.rotate(index)
...
...     def insert(self, value):
...             self._insert(bisect.bisect_left(self, value), value)
...
...     def __init__(self, iterable):
...             super(FunkyDeque, self).__init__(sorted(iterable))
...
>>> foo = FunkyDeque([3,2,1])
>>> foo
deque([1, 2, 3])
>>> foo.insert(2.5)
>>> foo
deque([1, 2, 2.5, 3])

请注意，需求 1、2 和 4 都直接源于底层数据结构是双端队列这一事实，而需求 3 由于数据的插入方式而成立。（当然请注意，您可以通过调用 eg 来绕过排序要求_insert，但这不是重点。）

于 2010-11-04T15:35:24.880 回答
9

非常感谢您katrielalex提供了导致以下 Python 类的灵感：

import collections
import bisect

class FastTable:

    def __init__(self):
        self.__deque = collections.deque()

    def __len__(self):
        return len(self.__deque)

    def head(self):
        return self.__deque.popleft()

    def tail(self):
        return self.__deque.pop()

    def peek(self):
        return self.__deque[-1]

    def insert(self, obj):
        index = bisect.bisect_left(self.__deque, obj)
        self.__deque.rotate(-index)
        self.__deque.appendleft(obj)
        self.__deque.rotate(index)
于 2010-11-04T16:45:59.820 回答
2

blist.sortedlist

  1. 以下四个操作中的许多操作的性能接近 O(1)。
  2. 在将对象插入容器时保持排序顺序。
  3. 能够查看对象中包含的最后一个值（最大值）。
  4. 允许两侧弹出（获取最小值或最大值）。
  5. 获取正在存储的对象的总大小或数量的能力。
  6. 作为一个现成的解决方案，就像 Python 标准库中的代码一样。

这是一棵 B+ 树。

于 2010-12-04T08:31:04.857 回答