[Tutor] python list, right! but concretely?

[spir ☣]

On Sun, 2 May 2010 18:57:41 +1000
Steven D'Aprano <steve at pearwood.info> wrote:

> On Sun, 2 May 2010 03:49:02 pm 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?
> 
> I'm not sure if this is documented anywhere (other than the source code, 
> of course) but in CPython lists are implemented as arrays of pointers 
> to objects.
> 
> Because re-sizing arrays is expensive, the array is over-allocated: the 
> array is (very approximately) created twice the size needed, to give 
> room to grow. Then when the array is full, or nearly full, it is 
> doubled in size again. This gives amortised O(1) appends, at the cost 
> of being 50% larger than needed on average. This means that append is 
> nearly always very, very fast, with an occasional, and rare, slow 
> append when the list resizes.
> 
> Because the list is an array, iteration is very fast and lookups are 
> O(1). However, deleting from the start or middle of the list is O(N), 
> as are insertions. If speed is important, and you need fast insertions 
> and deletions at both the start and end of the list, then you should 
> use collections.deque; however item lookup for deques is O(N).
> 
> Of course all of this is an implementation detail. Other implementations 
> are free to make other memory/time tradeoffs, although if their lists 
> performed very differently, people would complain.

Thank you. The reason why I started with linked lists rather than flexible arrays is the problem of deletion & insertion other than at the end. Is the tail of the list after the given element really shifted left or right, or are tricks used to avoid that? (I mean in a typical implementation). I imagined for instance there could be kinds of null placeholders for deleted items (this indeed makes all the rest more complicated but avoids compressing the list after deletion).

> > 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.
> 
> The simplest implementation of a linked list in Pascal is something like 
> this:
> 
> type:
>   ptr = ^node;
>   node = record
>     data: integer;
>     next: ptr
>     end;
> 
> Here's a procedure to traverse the list, printing each item:
> 
> {untested}
> procedure walk(alist: ptr):
>   begin
>     while alist <> nil:
>       begin
>         writeln(alist^.data);
>         alist := alist^.next
>       end;
>   end;
> 
> Everything else, I leave as an exercise :)

Yes, you're right. But when I said "linked list", I actually meant a kind of type with all needed "methods" ;-) 


Denis
________________________________

vit esse estrany ☣

spir.wikidot.com