Looping over lists and sets

Posted on 2008-10-25 14:10 By Deadstar (6)

Categories:

How do I ...? with Maple (Student)

Write a procedure rsum that sums the reciprocals of the elements of a list. So rsum( [a,b,c] ) should return 1/a + 1/b + 1/c.

How would i modify my code so that it does this... I know theres a much simpler way (rsum := L -> add( 1/x, x in L ):) but i would like to know how to edit the one ive done.

Heres my code so far...

rsum := proc(L)
local n;
    for n in L do
      1/n
    end do;
end proc;

I think I have to define (for ex), N, as something then have...

for n in L do

N, 1/n.

Any help on this please?

summing

Comment on 2008-10-25 16:45 from Joe Riel ( Maple Rating 4

1260)

You need to initialize a value to zero and then increment it in the loop.

rsum := proc(L::list)
local sm, x;
   sm := 0;     # this will store the partial sums
   for x in L do
      sm := sm + 1/x;
   end do;
  return sm;
end proc:

gc

Comment on 2008-10-25 20:13 from momiji (

54)

I wonder if this creates a lot of sums that will need to be garbage collected, like trying to build up a list in a loop.

I would probably use a one-liner to avoid creating garbage:

rsumshort := proc(L)
option inline;
`+`(op(map(`/`,L)));
end proc;

L:=[seq(cat(`a`,i), i=1..10000)]:

time(rsumshort(L));
                                     0.044
time(rsum(L));
                                    10.064

inefficient

Comment on 2008-10-25 20:34 from Joe Riel ( Maple Rating 4

1260)

Yes, excellent point. I'm embarrassed that I didn't notice this; I wasn't thinking of a symbolic list. If the elements in the list are numeric, then this is not an issue. Of course, the proper method is to use add, but the original poster explicitly ruled that out. Your method is a nifty workaround, but I don't see any practical reasons to prefer it over add.

The reason that the do loop is O(n^2) with symbolic elements is that the k'th pass through the loop creates a partial summation with k distinct elements: a1 + a2 + ... + ak. This summand is stored, at least temporarily, in the Maple simplification table. So n passes creates a total of n objects with sizes from 1 to n, hence the total memory requirement is n*(n+1)/2, which is O(n^2).

Use an Array?

Comment on 2008-10-26 10:17 from momiji (

54)

I didn't read the OP carefully enough. If one really wants to do something like this with a do loop, one should build up a mutable object in the loop, then convert it to a sum afterwards. Here it is using an Array, but you could use a table instead.

rsum_array := proc(L::list)
local A, i, x;
    A := Array(1..nops(L));     # this will store the summands    
    i := 1;
    for x in L do
        A[i] := 1/x;       
        i := i + 1;
    end do;

    return convert(A,`+`); 
end proc:

time(rsum_array(L));

0.080

Using a table is not as straight forward but almost as fast:

rsum_table := proc(L::list)
local T, i, x;
    T := table();     # this will store the summands    
    i := 1;
    for x in L do
        T[i] := 1/x;       
        i := i + 1;
    end do;

    return convert(map(op,[entries(T)]), `+`);
end proc:

time(rsum_table(L));                                
                                     0.088

nolist

Comment on 2008-10-26 11:59 from Joe Riel ( Maple Rating 4

1260)

Just a note. The entries (indices) command provide a 'nolist' option that returns the results without enclosing each entry in a list, so you can forego the map(op, ...) call:

return convert([entries(T,'nolist')], `+`);

I prefer, however,

return add(T[k], k=1..i-1)

old

Comment on 2008-10-26 12:33 from acer ( Maple Rating 4

1410)

convert(...,`+`) is an old technique. I am not 100% sure, but I suspect that it may predate add.

acer

convert/+

Comment on 2008-10-26 17:44 from Joe Riel ( Maple Rating 4

1260)

I see that one can directly convert from a table to `+`, the call to entries is not needed:

convert(eval(T), `+`)

Note that the eval is necessary, otherwise the table itself is returned. This is different than when convert/list is called:

convert(T, 'list');  # eval is not required

The add and mul functions

Comment on 2008-10-26 15:28 from Robert Israel ( Maple Rating 4

1555)

The add and mul functions were introduced in Maple V Release 4: see the help page ?updatesR4,language. I'm sure convert(...,`+`) goes way back, long before I became involved with Maple. It's mentioned in the Maple V Library Reference Manual (that's for Maple V Release 1, copyright 1991)

efficiency

Comment on 2008-10-26 23:47 from momiji (

54)

I thought convert(...,`+`) might be more efficient than add() but I guess that SUM dag is not just a list with a different label, so convert is probably doing nearly the same computation as 'add' (though it does it without needing a local variable).

add: local variable

Comment on 2008-10-26 23:58 from Joe Riel ( Maple Rating 4

1260)

I was going to mention that that could be an advantage of convert/+, however, one can safely use a global variable with add (which permits it to be inlined). That is

mysum := proc(L::list) option inline; add(x, x in L) end proc:

is, so far as I can ascertain, completely safe and works properly regardless whether x is assigned. Are there exceptions? Note that this is not the case with seq:

myseq := proc(L::list) option inline; seq(x, x in L) end proc:

This fails with the list [g(x)].

myseq([g(x)]);
Error, too many levels of recursion

The variable x should be declared as local, which precludes inlining the procedure.

Looping over lists and sets

Comment viewing options