The memory manager is called once every for 50 queue insertions and memory is freed after every 50 pops. Outside of that, every push and pop just a fast array access and pointer increment. Long queues incur about a 15-20% space overhead as compared to a straight-list implementation. Speedwise, this beats the socks off of the current approach.
Meaning pairing append() and pop(0)? Sure -- it would be hard not to beat that <wink>.
I've never needed a queue in Python where "the standard" two-list
No, I meant that it is *much* faster to do an indexed write to a pre-allocated list than to use anything relying on PyList_Append() or ins1(). All of those individual calls to realloc are expensive. The 50 to 1 dilution of that expense is how it beats Knuth's two stack trick. Guess which of these two statements is faster and by how much: list(itertools.repeat(None, 5000)) list(tuple(itertools.repeat(None, 5000))) The answer is important because it points the way to faster list comprehensions and other list building applications. trick
(as shown in Josiah's Cookbook comment) wasn't more than good enough, so my interest in this is really limited to whether Python's native list type can (realistically) be made efficient for general deque operation.
And my interest is in a collections module which should probably published elsewhere (too much negativity on the subject here). I am frankly surprised that so many here think that a collections module would be bad for the language. Go figure. It's not like these are new, untried ideas -- the goal was supposed be improving productivity by providing higher level tools. A fast underlying implementation was just icing on the cake. Raymond Hettinger ################################################################# ################################################################# ################################################################# ##### ##### ##### ################################################################# ################################################################# #################################################################