4 ms·
> 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 ht
by tzs 9y ago
> 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 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?
- tyingq 9y agoThere's some discussion about that here: http://www.perlmonks.org/?node_id=17890 http://www.perlmonks.org/?node_id=17890
- daveFNbuck 9y agoYou can see the CPython list implementation here: https://hg.python.org/cpython/file/273e17260d25/Objects/listobject.c#l12 https://hg.python.org/cpython/file/273e17260d25/Objects/list... The CPython list implementation does indeed sacrifice performance to use less size. It uses a pre-allocated array for the list and when the list gets too large, it needs to allocate a new array to hold the list and re-insert all the items into the new array. You may have done this in an intro CS class and doubled the array size to get an amortized O(1) append time, but you only need to increase the size by at least a constant fraction of the current size. Python increases by 1/8 of the current size, plus 6. This means more reallocations over a large number of operations, but less memory overhead at any given time. Because of this implementation, you can pop from the right by just changing the size of the array, but to pop from the left requires shifting the entire array. You can pop the kth element from the right in O(k) time by just shifting those elements, which may be what the wiki means. I didn't read the code thoroughly enough to verify that it actually does this, but it seems reasonable. Popping from the right is still slower than a deque because in order to save memory, the list gets resized whenever it falls below half of its maximum allocated size. A deque is always O(1) for every push/pop operation, but lists have occasional expensive operations that bump up the runtime a bit. Deques require linear time to access elements due to being implemented as doubly-linked lists. They're really only meant for accessing the elements on the ends. You can get fast popleft on a list if you also keep a left pointer, but this complicates the implementation and has a corresponding performance penalty. You can even do a fast appendleft on a list if you allocate the elements so they start with empty cells on both the left and the right, but this makes the tradeoff between memory and performance even worse.