Python lists/vectors/???

Thomas Wouters thomas at
Sat May 13 16:59:55 EDT 2000

On Sat, May 13, 2000 at 02:00:59PM +0000, Courageous wrote:

> Neel Krishnaswami wrote:

[The implementation of Python lists, in C]

> > They are O(1) arrays. list.append()ing to them is technically O(n),
> > but a full resize is triggered only every hundred (or thousand for big
> > lists) insertions because the resize leaves some slop.

> I noticed that (I have the code). That's the way I would have done
> it, too. I was more concerned about people pushing/popping python
> lists not realize that it was O(n).

Most people who use python do not really care about the theoretical speed
limits of the implementation. Compared to the rest of Python, lists are
'fast enough'. If you seek speed improvements, using a different algorithm
for the standard list is not going to gain you much. You are usually better
off using the array module, or rewriting your code into C (or some other
high-speed language ;)

Python's emphasis is *not* speed. And I, personally, thank g* it isn't. A
lot of things are more important than speed, in Python... Tim's Python
Philosophy (as re-posted a couple of times, recently) purpously does not
mention speed ;) Also, implementations should be allowed to change without
affecting current code (other than perhaps less bugs) -- so you shouldn't
rely on its speed.

(Actually, I think list speed is one of the FAQs.)

If (only) execution speed is the question, (only) Python is definately not
the answer.

Thomas Wouters <thomas at>

Hi! I'm a .signature virus! copy me into your .signature file to help me spread!

More information about the Python-list mailing list