代码之家 › 专栏 › 技术社区 › Noctis Skytower

有人知道这个Python数据结构吗?

deque insert sorting performance python

6

Noctis Skytower · 技术社区 · 15 年前

粗体字 将被视为要求。

接近用于以下四种操作中的任意一种。
维护容器中的物体。
有能力 (最大值)包含在对象中。
考虑到 (得到最小或最大的值)。
能力 获取总大小 或存储的对象数。
作为一个 现成的解决方案 就像Python标准库中的代码一样。

在查看了Python的标准库(特别是数据类型部分)之后,我仍然没有找到满足碎片表要求的类。 collections.deque

有效的附加和弹出 .
两边都有 对象中包含的数据。
获取总大小

使用列表实现一个效率低下的解决方案是很简单的,但是找到一个性能良好的类将是非常理想的。在没有上限的不断增长的内存模拟中,这样的类可以保留空(已删除)单元格的索引,并降低碎片级别。这个 bisect

有助于保持数组 插入时的排序顺序
现成的解决方案 用于将列表按添加的对象排序。
将允许执行 array[-1] 查看最后一个值 在阵列中。

最后一个没有完全满足要求并且看起来最没有希望的候选人是 heapq 模块。同时支持看似有效的插入并确保 array[0] 是最小的值,数组并不总是处于完全排序状态。没有什么比这更有用的了。

有没有人知道Python中的类或数据结构接近这六个要求?

3 回复 | 直到 15 年前

1

11

Katriel 15 年前

你的要求似乎是:

O(1)从两端弹出
有效的 len
排序顺序
查看最后一个值

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 ,但这不是重点。)

2

8

Noctis Skytower 11 年前

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)

3

2

tzot 15 年前

blist.sortedlist

对于以下四种操作中的任意一种,接近于O(1)性能。
查看对象中包含的最后一个值(最大值)的能力。
得到总数的能力 ~~大小或~~
成为一个现成的解决方案,就像Python标准库中的代码一样。

这是一棵B+树。