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.
> 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 :)
--
Steven D'Aprano
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
