Technical question on complexity.

J

Jerzy Karczmarczuk

Anybody knows where I can find a concrete and guaranteed answer to the following
extremely basic and simple question?

What is the complexity of appending an element at the end of a list?
Concatenating with another?

The point is that I don't know what is the allocation policy... If Python lists
are standard pointer-chained small chunks, then obviously linear. But perhaps
there is some optimisation, after all a tuple uses a contiguous chunk, so it
*might* be possible that a list is essentially equivalent to an array, with its
length stored within, and adding something may be done in constant time (unless
the whole stuff is copied, which again makes the complexity related to the size
of existing structure...)

It is probably possible to retrieve this information from the sources, but I try
first an easier way.
Thank you.

Jerzy Karczmarczuk
 
F

Fredrik Lundh

Jerzy said:
Anybody knows where I can find a concrete and guaranteed answer to the following
extremely basic and simple question?

What is the complexity of appending an element at the end of a list?

amortized O(1)
Concatenating with another?
O(n)

The point is that I don't know what is the allocation policy... If Python lists
are standard pointer-chained small chunks, then obviously linear. But perhaps
there is some optimisation, after all a tuple uses a contiguous chunk, so it
*might* be possible that a list is essentially equivalent to an array, with its
length stored within, and adding something may be done in constant time

a list consists of a single array of PyObject pointers, plus "allocated" and
"current size" fields. when you append, allocation is only done when needed,
and the new size is chosen carefully to keep the number of allocations low.
see the source for details (the exact "overallocation" strategy varies some-
what in different Python versions).

</F>
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top