[Tutor] speeding code along [lists and dictionaries are fast]

[Bob Gailer]

At 08:29 PM 11/17/2002 -0800, Danny Yoo wrote:
>Lists and dictionary lookup is nearly instantaneous: we use them to trade
>time with space.  That is, list lookup should take a constant amount of
>time, regardless of how large our lists are.

I don't know how python manages lists internally, but I offer an idea from 
IBM's implementation of APL2. (In APL variables are arrays with 0 or more 
dimensions. Before APL2 all elements of an array were the same internal 
datatype, which made indexing extremely efficient). In APL2 each element of 
an array could be a value or a "nested array", making it somewhat like 
Python's lists, but messier; indexing now found the pointer to the element. 
If changing an array by element assignment resulted in all elements being 
the same simple datatype, the array was flagged as "not nested", and 
therefore subject to indexing by offset. Perhaps a future implementation of 
Python could do something similar.

Bob Gailer
170 Forsythe Rd
Nederland CO 80466
303-442-2625