有人知道这种Python数据结构吗？

Question

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中有没有一个类或数据结构，能够接近这六个要求？

Answer 1

blist.sortedlist

1. 在以下四个操作中，性能接近O(1)，也就是非常快。
2. 在往这个容器里插入一个对象时，能够保持里面的东西是有序的。
3. 可以查看容器里最后一个值（也就是最大的值）。
4. 可以从两端取出值（获取最小或最大值）。
5. 能够获取存储的对象总数。
6. 像Python标准库里的代码一样，已经是现成的解决方案。

这是一种B+树。

Answer 2

你的需求似乎是：

1. 从两端都能快速弹出元素
2. 高效获取长度
3. 保持有序
4. 查看最后一个值

为了满足这些需求，你可以使用一个叫做 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都是因为底层的数据结构是deque，所以能直接满足。而需求3之所以能实现，是因为数据的插入方式决定了顺序。（当然，你可以通过调用比如 _insert 来绕过排序的需求，但那不是重点。）

Answer 3

非常感谢 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)