depq 1.5.5

此实现的特性与优势

• 完全线程安全

• 可以通过序列化或JSON进行序列化

• 优先级值可以是整数/浮点数、numpy类型、字符串或您选择的任何其他可比较类型！

• popfirst()和poplast()具有O(1)性能，而不是像标准DEPQ或其他基于堆的结构那样运行对数时间

• 由于deque对象是用C实现的，因此速度自然也很快

• 具有相同优先级的项按它们最初添加的顺序排序

• 可以删除特定项或更改它们的优先级

• 使用'in'运算符进行成员资格测试发生在O(1)，同样，在DEPQ中通过count(item)获取项的频率也发生在O(1)

实现

• 优先级总是按正确顺序排列，因此，在指定优先级时，会执行二分查找以找到正确插入新项的索引。通常情况下，通过insert(item, priority)添加项目时，如果self.high() > priority > self.low()，这将导致O(n log n)的性能，因为deque（作为双向链表）的随机访问是O(n)。

  尽管如此，实际上在这里并非如此，因为我已经通过修改二分查找以在内部deque并发旋转时操作，将其降低到O(n)。

示例

>>> from textwrap import fill  # For nice wrapped printing
>>> from depq import DEPQ
>>>
>>> # Defaults. If iterable is not None, extend(iterable) will be
>>> # called (example below). If maxlen is not None, abs(int(maxlen))
>>> # will become the length limit. If a maxlen is set and an item
>>> # is added with a priority > lowest prioritized item, it will be
>>> # added and the last item will be popped. After instantiation, the
>>> # maxlen can be retrieved with maxlen() and set with set_maxlen(length).
>>> depq = DEPQ(iterable=None, maxlen=None)
>>>
>>> # Add some characters with their ordinal
>>> # values as priority and keep count
>>> for c in 'AN_ERRONEOUS_STRING':
...     count = list(  # This is hacky and not important, skip next 4 lines :)
...         x + 1 if '{} #{}'.format(c, x + 1) in depq
...         else next(iter(())) if x != 0 else 0
...         for x in range(len(depq) + 1)
...     )[-1]
...
...     depq.insert('{} #{}'.format(c, count + 1), ord(c))  # item, priority
...
>>> print(fill(str(depq), 77))
DEPQ([('_ #1', 95), ('_ #2', 95), ('U #1', 85), ('T #1', 84), ('S #1', 83),
('S #2', 83), ('R #1', 82), ('R #2', 82), ('R #3', 82), ('O #1', 79), ('O
#2', 79), ('N #1', 78), ('N #2', 78), ('N #3', 78), ('I #1', 73), ('G #1',
71), ('E #1', 69), ('E #2', 69), ('A #1', 65)])
>>>
>>> # As you can see items with equal priorities are sorted in the order
>>> # they were originally added. Also note DEPQ root (depq[0]) is highest
>>> # priority like a max heap.
>>>
>>> depq.first()
'_ #1'
>>> depq.last()
'A #1'
>>> depq.high()
95
>>> depq.low()
65
>>> depq[7]  # Returns tuple(item, priority)
('R #2', 82)
>>>
>>> depq.poplast()
('A #1', 65)
>>> depq.last()
'E #2'
>>>
>>> depq.size()  # Alias for len(DEPQ)
18
>>> depq.is_empty()
False
>>> depq.clear()
>>> depq.is_empty()
True
>>>
>>> # Extend any length iterable of iterables of length >= 2
>>> depq.extend([('bar', 1, 'arbitrary'), (None, 5), ('foo', 2, 'blah')])
>>> depq
DEPQ([(None, 5), ('foo', 2), ('bar', 1)])
>>>
>>> depq.clear()
>>>
>>> depq.addfirst('starter')  # For an empty DEPQ, addfirst & addlast are
>>>                           # functionally identical; they add item to DEPQ
>>> depq                      # with given priority, or default 0
DEPQ([('starter', 0)])
>>>
>>> depq.addfirst('high', depq.high() + 1)
>>> depq.addlast('low', depq.low() - 1)
>>> depq
DEPQ([('high', 1), ('starter', 0), ('low', -1)])
>>>
>>> depq.addfirst('higher')  # Default priority DEPQ.high()
>>> depq.addlast('lower')  # Default priority DEPQ.low()
>>> depq
DEPQ([('higher', 1), ('high', 1), ('starter', 0), ('low', -1), ('lower', -1)])
>>>
>>> depq.addfirst('highest', 0)  # Invalid priority raises exception
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python34\lib\depq.py", line 340, in addfirst
    raise ValueError('Priority must be >= '
ValueError: Priority must be >= highest priority.
>>>
>>> del depq[0]  # As does del
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python34\lib\depq.py", line 639, in __delitem__
    raise NotImplementedError('Items cannot be deleted by '
NotImplementedError: Items cannot be deleted by referencing arbitrary indices.
>>>
>>> depq.clear()
>>> depq.count(None)
0
>>> for i in range(10):
...     depq.insert(None, i)
...
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 6), (None, 5), (None, 4),
(None, 3), (None, 2), (None, 1), (None, 0)])
>>>
>>> None in depq
True
>>> depq.count(None)
10
>>> depq.remove(None)  # Removes item from DEPQ, default # of removals is 1
[(None, 0)]
>>>
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 6), (None, 5), (None, 4),
(None, 3), (None, 2), (None, 1)])
>>>
>>> depq.remove(None, 4)  # As you see, returns list of tuple(item, priority)
[(None, 1), (None, 2), (None, 3), (None, 4)]
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 6), (None, 5)])
>>>
>>> depq[None] = 7  # Alias for DEPQ.insert(item, priority)
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 7), (None, 6), (None, 5)])
>>>
>>> depq.elim(None)  # This simply calls DEPQ.remove(item, -1)
[(None, 5), (None, 6), (None, 7), (None, 7), (None, 8), (None, 9)]
>>> print(fill(str(depq), 77))
DEPQ([])
>>>
>>> import pickle  # Pickling won't work if items aren't picklable
>>> import json  # JSON won't work if items aren't JSON serializable
>>>
>>> for i in range(5):
...     depq.insert([i], i)  # Unhashable types allowed but don't mutate them!
...
>>> depq
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>>
>>> binary_depq = pickle.dumps(depq)
>>> print(fill(str(binary_depq), 77))
b'\x80\x03cdepq\nDEPQ\nq\x00)\x81q\x01}q\x02(X\x05\x00\x00\x00itemsq\x03}q\x0
4(X\x03\x00\x00\x00[1]q\x05K\x01X\x03\x00\x00\x00[3]q\x06K\x01X\x03\x00\x00\x
00[2]q\x07K\x01X\x03\x00\x00\x00[4]q\x08K\x01X\x03\x00\x00\x00[0]q\tK\x01uX\x
04\x00\x00\x00dataq\nccollections\ndeque\nq\x0b]q\x0c(]q\rK\x04aK\x04\x86q\x0
e]q\x0fK\x03aK\x03\x86q\x10]q\x11K\x02aK\x02\x86q\x12]q\x13K\x01aK\x01\x86q\x
14]q\x15K\x00aK\x00\x86q\x16e\x85q\x17Rq\x18X\x05\x00\x00\x00startq\x19K\x00u
b.'
>>>
>>> json_depq = json.dumps(depq.to_json())
>>> print(fill(json_depq, 77))
{"items": {"[1]": 1, "[3]": 1, "[2]": 1, "[4]": 1, "[0]": 1}, "data": [[[4],
4], [[3], 3], [[2], 2], [[1], 1], [[0], 0]], "start": 0}
>>>
>>> depq_from_pickle = pickle.loads(binary_depq)
>>> depq_from_json = DEPQ.from_json(json_depq)  # Classmethod returns new DEPQ
>>>
>>> depq
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>> depq_from_pickle
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>> depq_from_json
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>>

备注

• DEPQ中的项目也存储在一个单独的字典中，以实现O(1)的查找。如果项目无法哈希，则存储该项目的repr()。因此，'item in DEPQ'将检查字典中的item，如果引发TypeError，它将尝试repr(item)。

• 此实现以线性时间插入中间，而教科书中的DEPQ是O(log n)。但在实际用例中，这种运行时间微小的增加并不重要，尤其是当考虑到额外获得的功能以及其他2个主要操作popfirst()和poplast()现在以常数时间发生的事实。