Queues - Is Infinity all right?

Rob Hunter rob at cs.brown.edu
Mon Oct 6 10:14:38 EDT 2003


On Sunday, October 5, 2003, at 09:53 PM, Jeremy Fincher wrote:

> Rob Hunter <rob at cs.brown.edu> wrote in message 
> news:<mailman.1065367209.7046.python-list at python.org>...
>> But it doesn't depend on such things.  There is no cost.  Check out 
>> the
>> source code if you like.  On my computer it's in /usr/lib/python<some
>> version>/Queue.py
>
> That's where your wrong.  list.pop(0) is an O(n) operation.

And this O(n) operation is used no matter is a bound was chosen for the 
queue size, or not.

Several people seemed to interpret the original question as, "What is 
the running time of the queue operations when there is an infinite 
bound on the size given?"  I interpreted the original question to be, 
"Is anything saved, in terms of running time, by choosing some 
particular queue size bound instead of leaving the it unbounded?"  And 
for that the answer is "No".  Agreed?

Above, when I wrote, "There is no cost", I should have written "There 
is no cost difference".  But

Rob






More information about the Python-list mailing list