How does Python remove elements from a list so quickly?

Question

I'm studying Python now, and I'm trying to understand how containers work in practice. There is an issue I can't explain. Suppose, I create very large list:

>>> l = [i for i in range(100000000)] # ~3 sec

It takes ~3 seconds to create it (I use ascending numbers instead of the same value to avoid possible optimization)

As we can read here, delete operation costs O(n). But when I remove an element from the middle of the list, it returns instantly (just as fast as any other simple command, like element access)

>>> del l[50000000] # instantly (< 0.1 sec)

and after this I can access elements l[25000000] and l[75000000] in less than 3 seconds after deletion, and it also executes instantly (so, I can't explain this by delayed or background removal).

Can someone, please, explain me, how is it done internally? Is the list in fact implemented as some kind of tree? It sounds weird, and also, it would violate requirements for constant time element access.

Is it a common optimization, like return value optimization in C++, or something rare, specific only to my platform/version?

I use Linux and Python 3.4.1 (Python 2.7.9 shows the same results).

Answer 1

I decided to turn my set of comments into a proper answer.

First off, let's clarify what's happening when you do:

>>> l = [i for i in range(100000000)]

Here three things are happening:

1. 100000000 int objects are being created. Creating an object in CPython requires allocating memory and placing content into that memory, and this takes time.
2. You are running a loop. This affects performances considerably: [i for i in range(...)] is much slower than list(range(...)).
3. The large list is being created on the fly.

Reading your question, it seems that you are considering only the last point, ignoring the others. Therefore, your timings are inaccurate: creating a large list does not take 3 seconds, it takes a fraction of those 3 seconds.

How large is this fraction is an interesting question, which is difficult to answer using only Python code, but still we can try. Specifically, I'd try with the following statement:

>>> [None] * 100000000

Here CPython does not have to create a large amount of objects (there's only None), does not have to run loops and can allocate the memory for the list once (because it knows the size in advance).

Timings are self-explanatory:

$ python3 -m timeit "list(range(100000000))"
10 loops, best of 3: 2.26 sec per loop
$ python3 -m timeit "[None] * 100000000"
10 loops, best of 3: 375 msec per loop

---

Now, back to your question: how about item deletion?

$ python3 -m timeit --setup "l = [None] * 100000000" "del l[0]"
10 loops, best of 3: 89 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 4]"
10 loops, best of 3: 66.5 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 2]"
10 loops, best of 3: 45.3 msec per loop

These numbers tell us something important. Note that 2 × 45.3 ≈ 89. Also 66.5 × 4 / 3 ≈ 89.

These numbers are telling exactly what linear complexity is about. If a function has time complexity kn (which is O(n)), it means that if we double the input, we double time; if we increase the input size by 4/3, the time increases by 4/3.

And this is what's happening here. In CPython, our list of 100000000 items is a contiguous memory area containing pointers to Python objects:

l = |ptr0|ptr1|ptr2|...|ptr99999999|

When we run del l[0] we are moving ptr1 from right to left, overwriting ptr0. The same for other elements:

l = |ptr0|ptr1|ptr2|...|ptr99999999|
     ^^^^
         ` item to delete

l = |ptr1|ptr2|...|ptr99999999|

Therefore, when we run del l[0] we have to move 99999998 pointers to the left. This is different from del l[100000000 // 2], which requires moving only half the pointers (the pointers on the first half don't need to be moved). "Moving half the pointers" equals "performing half of the operations" which roughly mean "running in half the time" (this is not always true, but timings say that this is true in this case).

Answer 2

I'm not sure why you think it should take 3 seconds to delete a single element.

Your initial time is for 100000000 individual append operations. Each of those takes a fraction of a second; your delete operation takes a similar amount of time.

In any case, as Bartosz points out, O(n) complexity doesn't mean that all operations take the same length of time, it means that the length of time is proportional to the length of the list.