lists and sequences
Collin Monahan
What is a python list? Is it a linked list or a random access structure
in contiguous memory? What type of situations should be avoided when
using it? E.g. when does n^2 time happen using it? What sorting
algorithm is used by its sort member function?
Are the answers to these questions the same for Jython? If there is a
good situation to use a Java collection from Jython because of above
considerations, how bad are the constant factors which arise from doing
so? That is, how preferable is it to stick with the python-language
structures when using Jython?
I'm not on the list so please copy me.
Thank you
Collin Monahan
__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
Gerhard Häring
> What is a python list? Is it a linked list or a random access structure
> in contiguous memory?
This type of questions can be easily answered by looking into its
implemenation (Objects/listobject.c).
> What type of situations should be avoided when using it?
Checking for containment using the 'in' operator.
> E.g. when does n^2 time happen using it? What sorting algorithm is
> used by its sort member function?
Read the Source, Luke. Looks like 'samplesort' (never heard of), and
quicksort are used, among others. IOW, it's pretty damn well
optimized.
> Are the answers to these questions the same for Jython?
Read the Source, Luke. Looks like it's a combination of quicksort and
insertion sort.
Gerhard
--
mail: gerhard <at> bigfoot <dot> de registered Linux user #64239
web: http://www.cs.fhm.edu/~ifw00065/ OpenPGP public key id AD24C930
public key fingerprint: 3FCC 8700 3012 0A9E B0C9 3667 814B 9CAA AD24 C930
reduce(lambda x,y:x+y,map(lambda x:chr(ord(x)^42),tuple('zS^BED\nX_FOY\x0b')))
Tim Peters
> What is a python list? Is it a linked list or a random access structure
> in contiguous memory?
A contiguous vector of pointers to objects.
> What type of situations should be avoided when using it?
Depends on the app and your judgment of appropriate tradeoffs.
> E.g. when does n^2 time happen using it?
alist.insert(0, newthing) physically moves len(alist) elements. Ditto
alist.pop(0).
> What sorting algorithm is used by its sort member function?
A hybrid of samplesort and binary insertion sort.
> Are the answers to these questions the same for Jython?
Don't know.
grateful-for-the-easy-ones<wink>-ly y'rs - tim
Dave Reed
> Cc: cmon...@yahoo.com
>
> [Collin Monahan]
> > What is a python list? Is it a linked list or a random access structure
> > in contiguous memory?
>
> A contiguous vector of pointers to objects.
>
> > What type of situations should be avoided when using it?
>
> Depends on the app and your judgment of appropriate tradeoffs.
>
> > E.g. when does n^2 time happen using it?
>
> alist.insert(0, newthing) physically moves len(alist) elements. Ditto
Just to be clear, these are order n, not order n^2.
<other info snipped>
Dave
Tim Peters
>>> E.g. when does n^2 time happen using it?
[Tim]
>> alist.insert(0, newthing) physically moves len(alist) elements. Ditto
[Dave Reed]
> Just to be clear, these are order n, not order n^2.
"in a loop of appropriate duration" was left to the reader's imagination,
assuming they had one <wink>. The obvious intent of Collin's question was
to discover which elementary operations required worse than O(1) time. His
"e.g." was for the benefit of those who couldn't decipher his immediately
preceding "What type of situations should be avoided when using it?".
Knowing that an individual insertion or deletion "at the wrong end" can be
expensive is responsive to what he really wanted to know.
modern-bots-don't-take-human-words-at-face-value-ly y'rs - tim