双端优先级队列
depq的Python项目详细描述
depq-双端优先级队列
- 线程安全高效的python实现 双端优先级队列(depq),其中的项及其 优先级值作为元组存储在deque对象中。
- 当然,这也可以用作常规优先级队列,或者 只是一个先进先出/后进先出队列。
- 优先级队列有许多用途,如调度、事件驱动 模拟、启发式分析、垃圾邮件过滤、图形搜索等。
此实现的功能和优点:
- 完全线程安全
- 可通过pickling或json序列化
- 优先级值可以是int/float、numpy类型、字符串或 任何其他可比类型你选择!
- popfirst()和poplast()具有o(1)性能,而不是 以对数时间运行,如在标准depq或其他 堆派生结构
- 自然也很快,因为deque对象是用c实现的
- 优先级相等的项按它们的顺序排序 最初添加
- 可以删除特定项目或更改其优先级
- 在o(1)中使用“in”运算符进行成员资格测试 通过计数(item)获取depq中项目的频率
实施:
优先级总是按正确的顺序排列,因此,二进制搜索 执行此操作是为了找到要插入新索引的正确索引 指定优先级时的项。通常,这会导致 o(n logn)通过insert添加项时的性能(项,优先级) 其中self.high()>;priority>;self.low(),因为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中的项也与它们的频率一起存储在 分开dict进行o(1)查找。如果项是不可哈希的,则repr() 而不是存储该项的。所以'item in depq'会检查 dict for item,如果引发typeerror,它将尝试repr(item)。
- 此实现在线性时间的中间插入 教科书depq是o(log n)。但是在实际的用例中 运行时间的无穷小增长是无关紧要的,特别是当 有人认为,与 其他两个主操作popfirst()和poplast()现在 在恒定的时间内发生。