Python自带的队列实现deque直接在CPython中以C代码实现。因此,很难用纯Python代码达到它的性能匹配。但这不应该阻止您尝试(与@Cecil Curry所说的不同),因为这会让您学得更好。
Shaon shaonty将其实现为一个链表。我使用字典实现如下:
class Queue:
slots = ['_dict','_max_item','_min_item','_min_reshape_countdown_length', '_reshape_countdown']
def __init__(self):
self._min_reshape_countdown_length = 1000
self._dict = {}
self._max_item = None
self._min_item = None
self._reshape_countdown = self._min_reshape_countdown_length
def appendleft(self, item):
if not self._dict:
self._dict = {0:item}
self._max_item = self._min_item = 0
else:
self._dict[self._min_item - 1] = item
self._min_item -= 1
if self._reshape_countdown == 0:
self._reshape_countdown = max(len(self._dict), self._min_reshape_countdown_length)
self._reshape()
else:
self._reshape_countdown -=1
def pop(self):
if not self._dict:
raise IndexError('Queue is empty!')
item = self._dict[self._max_item]
del self._dict[self._max_item]
if not self._dict:
self._max_item = self._min_item = None
else:
self._max_item -= 1
if self._reshape_countdown == 0:
self._reshape_countdown = max(len(self._dict), self._min_reshape_countdown_length)
self._reshape()
else:
self._reshape_countdown -=1
return item
def _reshape(self):
if not self._dict:
return
positives = max(0, self._max_item)
negatives = -min(0, self._min_item)
size = len(self._dict)
if positives > size/3 and negatives > size/3:
return
center = (self._min_item + self._max_item)//2
self._dict = {key-center: value for key,value in self._dict.items()}
self._max_item = self._max_item - center
self._min_item = self._min_item - center
请注意,这不是用于大型队列的好实现方式,因为创建大整数将会成为一个问题。可以通过将队列分成每个具有某个固定大小字典的块来解决该问题。
我使用以下代码比较了
Shaon shaonty的链表实现、我的字典实现和collections.deque。
import random
operations = []
queue_commands = 0
dequeue_commands = 0
for i in range(1000000):
if queue_commands > dequeue_commands:
operations.append(('q',random.random()) if random.random() < 1/2 else ('d',None))
else:
operations.append(('q',random.random()))
if operations[-1][0] == 'q':
queue_commands += 1
else:
dequeue_commands += 1
def test_case(queue):
for command, element in operations:
if command == 'q':
queue.appendleft(element)
else:
queue.pop()
结果是:
%timeit test_case(Linked_Queue())
796 ms ± 2.13 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit test_case(Queue())
838 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit test_case(deque())
120 ms ± 566 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
正如我所说的,用原始的Python代码来击败deque并不容易。
class Dummy:
def appendleft(self,item):
pass
def pop(self):
pass
%timeit test_case(Dummy())
176 ms ± 327 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
collections.deque
? - Uri Goren