> The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation.
That's somewhat surprising. The documentation at https://wiki.python.org/moin/TimeComplexity says that the time complexity of pop(k) on a list of size of n is O(k). Since k is constant in this program, that time complexity should be constant, not linear.
However, a quick little test program:
import sys
import time
n = int(sys.argv[1])
l = list(range(n))
print("list ready")
start = time.time()
for i in range(1000):
l.pop(0)
took = time.time() - start;
print(n, took)
agrees with you rather than with wiki.python.org:
10000 0.00488591194152832
100000 0.06201004981994629
1000000 0.7796049118041992
10000000 12.354434967041016
The documentation for deques at docs.python.org does say that pop(0) on a list is O(n), so it looks like the wiki needs clarification.
I tried it in Perl, too:
use Time::HiRes qw(gettimeofday tv_interval);
my $n = shift;
my @list = (1 .. $n);
my $start = [gettimeofday];
for ($i = 0; $i < 1000; ++$i)
{
shift @list;
}
my $elapsed = tv_interval($start, [gettimeofday]);
print "$n $elapsed\n";
and there it does appear to be approximately constant time (which is what I expected):
10000 0.000135
100000 0.000142
1000000 0.000178
10000000 0.000163
100000000 0.000176
Changing the Python program to use a deque (and changing pop to popleft) gives results similar to Perl:
10000 0.00017404556274414062
100000 0.00018596649169921875
1000000 0.0001850128173828125
10000000 0.0001819133758544922
100000000 0.00019288063049316406
The numbers are essentially the same popping from the other side.
Out of curiosity I then changed the Python program to pop the last item of the list instead of the first, and got this:
10000 0.00025200843811035156
100000 0.00026297569274902344
1000000 0.0002658367156982422
10000000 0.0002770423889160156
100000000 0.0002639293670654297
So even on the fast side, the list is slower at popping than the deque.
I was then curious to compare list and deque for accessing interior elements. I changed the programs from poping item to adding 1000 items from the list or deque spaced evenly throughout.
List:
10000 0.0002741813659667969
100000 0.0003039836883544922
1000000 0.0004611015319824219
10000000 0.0005731582641601562
100000000 0.0006010532379150391
Deque:
10000 0.00033092498779296875
100000 0.0014951229095458984
1000000 0.03908801078796387
10000000 0.45997095108032227
100000000 16.526084899902344
OK...so that's why we don't just use deque everywhere.
I did the same thing with my Perl program:
10000 0.000301
100000 0.000375
1000000 0.000511
10000000 0.000624
100000000 0.000638
It's interesting that Perl's array seems to combine the fast access at both ends of Python's deque with the fast random access of Python's list. I wonder how it does this? The Perl array seems to use more memory than the Python list, so maybe Perl is trading off size to get versatility?