Re: Lists

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Fri, Dec 10, 2010 at 04:43:32PM -0500, Charles Greathouse wrote:
> Pari has many types of collections: vectors, column vectors, matrices,
> sets, lists, small vectors, etc.  I understand the difference between
> matrices and the others (two-dimensional vs. one-) and between small
> vectors and the others (word-sized integers vs. Pari GENs).  Even sets
> I have a reasonable understanding of, even if I'm not too sure of
> their efficiency (what operations are fast and which slow?).  I can
> see that column vectors are useful if you're going to do matrix
> operations, but they are otherwise the same as vectors.
> 
> But what are lists?  When should they be used, why are they distinct
> from vectors, what's their underlying mathematical structure (if any)?
>  Can someone give an example of when it's 'right' to use a List but
> not a vector, or when a List is fast but a vector slow?

Lists (at least with PARI 2.4.3) are useful because you can change them
(enlarge them) without making copy, which is not possible with vectors.

For example: build a list of all prime numbers <= 100000:

? my(L=List());for(i=1,100000,if(isprime(i),listput(L,i)));L;
? ##
  ***   last result computed in 48 ms.

If you use a vector it is much slower:

? my(L=[]);for(i=1,100000,if(isprime(i),L=concat(L,i)));L;
? ##
  ***   last result computed in 2,268 ms.

To avoid this issue, you can do:
? my(L=vector(primepi(100000)),j);for(i=1,100000,if(isprime(i),L[j++]=i));L;
? ##
  ***   last result computed in 48 ms.
but this require to compute a reasonnable estimate of the maximum size of the vector.

The major downside of lists is that it is hard to use them (if at all) with GP2C.

Cheers,
Bill.