Re: [Maxima-discuss] iterate over two lists

[Helmut J. <jar...@ig...>]

On 04/24/2014 04:37:11 PM, Stavros Macrakis wrote:
> The matrix transpose is nice.
> 
> Remember that Maxima lists are linear linked lists, so random access
> requires iterating through the list (O(n)), so this is better:
> 
>       multimap_for(f,l) := for i in args(transpose(apply('matrix,l)))  
> do
> f(i)$
> 
> If you want to accumulate the result, instead of for/push/reverse,  
> just use
> map:
> 
>       multimap_map(f,l) := map(f,args(transpose(apply('matrix,l))))$
> 

I was curious about the speed of this construction, so I made some  
tests.
The tests were done on an empty machine and the timings were  
reproducible on several runs.

@Stavros :
Why is your solution twice as fast as the array solution in Test III?

Helmut

P.S. the timings were done with SBCL-1.1.16 on an AMD Phenom II (3.2  
GHz)

Test I : A single loop over a short list
========================================

Short:true$
if Short then ( NLoops:100, NL:1000 )
    else       ( NLoops:1  , NL:100000 )$

L:makelist(0,NL)$
emptyloop(L):= block([i,sum:0,N:length(L)],
   for i:0 thru N do sum:sum+1,
   sum
)$

listaccess(L):= block([i,sum:0,N:length(L)],
   for i:1 thru N do sum:sum+L[i],
   sum
)$

matrixacces(L):= block([sum:0],
   for ds in args(transpose(apply('matrix,[L]))) do sum:sum+ds,
   sum
)$

arrayaccess(L):= block([i,sum:0,N0:length(L)-1],
   local(AL), array(AL,N0), fillarray(AL,L),
   for i:0 thru N0 do sum:sum+AL[i],
   sum
)$

timer(all)$
thru NLoops do (
    Se:emptyloop(L),
    Sl:listaccess(L),
    Sm:matrixacces(L),
    Sa:arrayaccess(L)
)$
timer_info();

/*
   N = 1000    NLoops = 100
  [  function           time//call         calls   runtime   gctime ]
  [                                                                 ]
  [ arrayaccess        0.00668 sec          100   0.668 sec    0    ]
  [                                                                 ]
  [ matrixacces  0.006670000000000001 sec   100   0.667 sec    0    ]
  [                                                                 ]
  [ listaccess         0.00915 sec          100   0.915 sec    0    ]
  [                                                                 ]
  [  emptyloop         0.00609 sec          100   0.609 sec    0    ]
*/



Test II : A single loop over a long list
========================================

Same as above except setting  Short: false$

/* N=100000   NLoops = 1
  [  function    time//call   calls   runtime    gctime ]
  [                                                     ]
  [ arrayaccess   0.654 sec     1    0.654 sec     0    ]
  [                                                     ]
  [ matrixacces   0.723 sec     1    0.723 sec     0    ]
  [                                                     ]
  [ listaccess   25.782 sec     1    25.782 sec    0    ]
  [                                                     ]
  [  emptyloop    0.596 sec     1    0.596 sec     0    ]
*/


Next, I tried several loops over the same list:

Test III : multiple loops over a list
=====================================

NL:10000$
L:makelist(0,NL)$
emptyloop(L,nit):= block([i,sum,N:length(L)],
   thru nit do (
     sum:0,
     for i:1 thru N do sum:sum+1
   ),
   sum
)$

listaccess(L,nit):= block([i,sum:0,N:length(L)],
   thru nit do (
     sum:0,
     for i:1 thru N do sum:sum+L[i]
   ),
   sum
)$

matrixaccess(L,nit):= block([sum:0,M],
   M:transpose(apply('matrix,[L])),
   thru nit do (
     sum:0,
     for ds in args(M) do sum:sum+ds[1]
   ),
   sum
)$

arrayaccess(L,nit):= block([i,sum:0,N0:length(L)-1],
   local(AL), array(AL,N0), fillarray(AL,L),
   thru nit do (
     sum:0,
     for i:0 thru N0 do sum:sum+AL[i]
   ),
   sum
)$

timer(all)$
Se:emptyloop(L,10)$
Sl:listaccess(L,10)$
Sm:matrixaccess(L,10)$
Sa:arrayaccess(L,10)$
timer_info();

/*
  [   function    time//call   calls   runtime   gctime ]
  [                                                     ]
  [ arrayaccess    0.662 sec     1    0.662 sec    0    ]
  [                                                     ]
  [ matrixaccess   0.327 sec     1    0.327 sec    0    ]
  [                                                     ]
  [  listaccess    3.089 sec     1    3.089 sec    0    ]
  [                                                     ]
  [  emptyloop     0.597 sec     1    0.597 sec    0    ]
*/