[SciPy-user] How to start with SciPy and NumPy

[David Cournapeau]

Sturla Molden wrote:
>> On Sun, Jan 25, 2009 at 8:17 PM, Vicent <vginer at gmail.com> wrote:
>>     
>
>   
>>> (2) What about lists with different typed items within them?
>>>       
>> Numpy arrays - and generally arrays - fundamentally rely on the
>> assumption of the same type for every item. A lot of the performances
>> of array comes from this assumption (it means you can access any item
>> randomly without the need to traverse any other item first, etc...).
>>     
>
> Just to clear up a common misunderstanding:
>
> Pythons lists are also implemented as arrays, with the append to the back
> being amortized to O(1).

Hm, I did not know that - indeed, when I was talking about list, I was
thinking about linked list.

>  This means that Python allocates some empty space
> at the end, proportional to the size of the list. Thus, every append does
> not need to invoke realloc, and the complexity becomes O(1) on average.
>   

This is independent of the list implementation, isn't it ? I am quite
curious to understand how you could get O(1) complexity for a "growable"
container: if you don't know in advance the number of items, and you add
O(N) items, how come you can get O(1) complexity ?

> The performance of arrays over linked lists comes mainly from cache
> coherency, not random access. Most use of these containers are sequential.
>   

This may be true for one dimensional array, but generally, I think numpy
array performances come a lot from any item being reachable directly
from its 'coordinates' (this plus using native types instead of python
objects of course).

> I'd estimate that >75% of all
> programmers in this world does not know that list and tree structures can
> be implemented more efficiently using arrays instead of chained pointers.
>   

Maybe >75% programmers do not need to implement their own tree and list
:) The only time I implemented my own list was at my first course course
of programming, in C, which convinced me for quite some time that
programming was awful and consisted in looking for bus errors in that
strangely named ultrasparc machine,

cheers,

David