Internals and complexity of types, containers and algorithms

[Josiah Carlson]

Harald Luessen wrote:
> On Mon, 25 Jun 2007 Martin v. Löwis wrote:
> 
>> Sure, see below:
>>
>> - tuples are represented as arrays, with a single block for the
>>  entire objects (object header, tuple size, and data)
>> - list are represented as arrays, with two memory blocks:
>>  one for object header and sizes, and the other one for the
>>  "guts", i.e. the actual data. The list uses over-allocation,
>>  to avoid resizing on each addition.
>> - strings are implemented as arrays, with a single block for
>>  the entire string. In addition to header, size, and data,
>>  it also contains a cached hash and a pointer to the interned
>>  version of the string (if any).
>> - dicts are implemented as hash tables, with open addressing.
> ... and more interesting things ...
> 
> Thank you. That was the information I was looking for. 
> I just forgot to ask for sets.

Generally, sets are dictionaries without values (and some tweaks related 
to handling set operations).

  - Josiah