Bill Allombert on Fri, 10 Dec 2010 23:15:15 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Lists |
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.