>
> b. In trying to set up, e.g., a 'Max' function for a list, one can
> do it as
> for li in list do z: max(z,li), return(z)
> or one can do
> sort(list), return(last(list))
> ...
> After compiling, should it make much difference, say on lists
> of length <= 50000 ?
>
I'd be surprised if sorting were ever faster than the linear approach. Not
only does it take n*log(n) comparison operations in general, but it also has
to manipulate the array or list structure. But it's easy enough to do the
experiment.
>From the results, below, you can see that xreduce('min,...) is the fastest
approach, and also one of the simplest. The do-loop with < is only about
50% slower, but is more complicated. I do wonder why lreduce and rreduce are
so slow -- much slower than a full sort! --, but we'll leave that for
another day.
For fun, I thought I'd also try it for the symbolic case: s100 is a
100-length list of symbols with declared relations. I am not sure why do<
is faster than xreduce in this case. It is also weird that sort is
competitive with reduce.
By the way, the "return" statements above are not necessary. See code
below.
I hope you find this useful (and interesting, perhaps).
-s
Results (Maxima 5.11, GCL, Athlon 1GHz)
100 500 2500 12500 S 100
minlist 0.10 0.50 0.23 1.46 2.46 do min
minlist1 0.10 0.00 0.10 0.20 0.39 do <
minlist2 0.00 0.10 0.10 0.13 0.64 xreduce
minlist3 0.10 0.60 0.36 18.56 2.79 lreduce
minlist4 0.10 0.50 0.37 17.47 2.57 rreduce
minlist5 0.10 0.60 0.24 1.62 2.79 tree_reduce
minlist6 0.10 0.60 0.28 3.73 2.24 sort
Code
minlist(l):=block([r:'inf],for i in l do r:min(i,r),r)$
minlist1(l):=block([r:'inf],for i in l do if i<r then r:i,r)$
minlist2(l):=xreduce('min,l)$
minlist3(l):=lreduce('min,l)$
minlist4(l):=rreduce('min,l)$
minlist5(l):=tree_reduce('min,l)$
minlist6(l):=first(sort(l))$
compile(minlist,minlist1,minlist2,minlist3,minlist4,minlist5,minlist6)$
showtime:all$
ll: makelist(random(100000),i,1,100)$
minlist(ll)$
minlist1(ll)$
minlist2(ll)$
minlist3(ll)$
minlist4(ll)$
minlist5(ll)$
minlist6(ll)$
ll: makelist(random(100000),i,1,500)$
minlist(ll)$
minlist1(ll)$
minlist2(ll)$
minlist3(ll)$
minlist4(ll)$
minlist5(ll)$
minlist6(ll)$
ll: makelist(random(100000),i,1,2500)$
minlist(ll)$
minlist1(ll)$
minlist2(ll)$
minlist3(ll)$
minlist4(ll)$
minlist5(ll)$
minlist6(ll)$
ll: makelist(random(100000),i,1,12500)$
minlist(ll)$
minlist1(ll)$
minlist2(ll)$
minlist3(ll)$
minlist4(ll)$
minlist5(ll)$
minlist6(ll)$
minlist6(l):=first(sort(l,"<"))$ /* careful! */
for i 100 do assume(a[i-1]<a[i])$
ll: makelist(a[random(100)],i,1,100)$
minlist(ll)$
minlist1(ll)$
minlist2(ll)$
minlist3(ll)$
minlist4(ll)$
minlist5(ll)$
minlist6(ll)$