[Tutor] python list, right! but concretely?

[spir ☣]

On Sun, 02 May 2010 19:44:22 +1000
Lie Ryan <lie.1296 at gmail.com> wrote:

> On 05/02/10 15:49, spir ☣ wrote:
> > Hello,
> > 
> > Is there anywhere some introduction material to the implementation of python lists
> > (or to fully dynamic and flexible sequences, in general)?
> 
> 
> > More precisely, I'd like to know what kind of base data-structure is used
> > (linked list, dynamic array, something else -- and in case of array,
> how is
> > resizing computed). Also, how is "generics" (element are of free type, and
> > even heterogeneous) managed?
> 
> Python's 'list' is an array of pointers to `PyObject` ('object' in
> Python) and the resizing algorithm keeps the list size such that
> "allocated / 2 <= actual <= allocated". When list need to resize, it
> overallocates the list slightly over 1.125 times than the requested size
> "(newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize".

Thank you very much, that's exactly the kind of information I was looking for.
One "mystery" is now solved, if I understand correctly: actually it's not really generics, rather the type is a supertype of all relevant ones.

> If you're interested in more precise details (since I do omit some,
> especially those that seems to be micro-optimization-related), you need
> to read the source at
> http://code.python.org/hg/trunk/file/e9d930f8b8ff/Objects/listobject.c

Right, I'll have a look myself, now. Thank you for the pointer.

> > Denis
> > 
> > PS: The reason is I'm trying to understand better the underlying layers of
> > magic facilities we use everyday. Starting from about no computer science
> > knowledge. I have a working implementation of linked lists in primitive
> > langguages ;-) (namely C & Pascal), but rather complicated to my taste;
> > and I'm probably overlooking commonly known and used tricks that could
> > make the algorithm simpler or more efficient.
> 
> Real life implementation is always hairy, especially as the programmer
> cut corners to drench some speed benefit and include many error
> checkings. Today is the first time I actually looked at list's
> implementation, now I know why people hated C, for every line of real
> code, there's three or four lines of error checking code, e.g. to ensure
> malloc successfully allocated enough memory or that index access is in
> range.

Yes, I know that for having played with C a very long time ago. The reason why I started with Pascal, which makes things slightly simpler (esp. freepascal in my case). But maybe even more verbose: about 450 loc for a link list type (with all required operations, sure).


Denis
________________________________

vit esse estrany ☣

spir.wikidot.com