Python 类有六个要求,如下所示。只有粗体字才能被解读为要求。
- 以下四个操作中的许多操作的性能接近O(1) 。
- 在将对象插入容器时保持排序顺序。
- 能够查看对象中包含的最后一个值(最大值)。
- 允许两侧弹出(获取最小值或最大值)。
- 获取正在存储的对象的总大小或数量的能力。
- 作为一个现成的解决方案,就像 Python 标准库中的代码一样。
以下内容出于历史原因留在这里(帮助好奇并证明进行了研究)。
在查看了 Python 的标准库(特别是关于数据类型的部分)之后,我仍然没有找到一个满足分片表要求的类。collections.deque
接近要求,但不支持保持其中包含的数据排序。它提供:
- 在具有O(1) 性能的双端队列的任一侧进行高效的追加和弹出。
- 对象中包含的数据的两侧弹出。
- 获取其中包含的对象的总大小或计数。
使用列表实现一个低效的解决方案将是微不足道的,但找到一个表现良好的类将是更可取的。在没有上限的不断增长的内存模拟中,这样的类可以保持空(已删除)单元格的索引并降低碎片级别。该bisect
模块可能有助于:
- 帮助在数组中插入新对象时保持数组的排序。
- 在添加对象时保持列表排序的现成解决方案。
- 将允许执行
array[-1]
以查看数组中的最后一个值。
未能完全满足要求并且看起来最没有希望的最终候选是该heapq
模块。虽然支持看似有效的插入并确保这array[0]
是最小值,但数组并不总是处于完全排序的状态。没有其他任何东西有帮助。
有谁知道 Python 中接近这六个要求的类或数据结构?