Home Original page

Iteration index

Tim Peters tim.one at home.com
Fri Jun 1 16:46:31 EDT 2001 
[D-Man]
> What is the difference between a "vector" and an "array" in this
> context?  (Not as in   void[] or void*  vs.  std::vector< void* > )

Beats me -- what do those words mean to *you*?  Then you can explain the
difference yourself <wink>.  I usually use them as synonyms.

> I took a look at listobject.c and liistobject.h and I see that the
> list itself is just a PyObject** -- a pointer to a C array on the
> heap.  I also noticed in the 'ins1' function that inserting an element
> (not at the end) causes all others elements to be moved.  Isn't this
> pretty inefficient or is it such an infrequent operation that it
> matters less than the O(1) PyList_GetItem?

Dozens and dozens of Kbs of discussions about this were posted to c.l.py
over the last 7 days.  "insert in the middle" on *long* Python lists is
indeed infrequent in well-written Python code, but hard to say whether
that's because it's a relatively rare desire, or just because people know
it's inefficient so avoid it (I suspect more the former).  For reasonably
short lists it's fine; e.g., using bisect.insort() to maintain a priority
queue of no more than a few hundred elements is generally faster than any
other way of doing it in Python.  Dumb data structures have very low
overhead, and that often covers differences in O(N) behavior until N grows
"large".
More information about the Python-list mailing list