Advanced Search
All Posts : Product Tips & Techniques
Consider the following three problems: 1) given a list [a,b,c,d,e], return the list [a=1,b=2,c=3,d=4,e=5] 2) given a nested list [a, [b, [c, [d, [e]]]]] return the list [a,b,c,d,e] 3) given an integer in base 10, compute it's base b representation First I will show you what not to do: 
L := [a,b,c,d,e];
M := [];
for i from 1 to nops(L) do
  M := [op(M), L[i]=i];
end do;
Building up lists (and sets) incrementally is quadratic time, because each iteration of the loop allocates linear storage to hold the new list. The standard solution is a loop with a temporary variable, assigning to a table: 
M := table():
for i to nops(L) do
  M[i] := L[i]=i;
end do:
[seq(M[i], i=1..nops(L))];
However for large lists this is slow, because you are accessing the elements of L incrementally. If you time it, you will see that seq(L[i], i=1..nops(L)) is much slower than seq(i, i=L) when L is a large list. Thus we need to do one linear pass through the list L. We can modify the loop as follows to acheive the desired result: 
M := table():
j := 1:
for i in L do 
  M[j] := i=j;
  j := j+1;
end do:
[seq(M[i], i=1..nops(L))];
The code above is asymptotically faster than all previous versions, however it still requires a table and random accesses to construct the result. Can't we just somehow use seq ? The answer is "yes", and the trick is to use the assign command: assign('x', v) assigns v to x and returns NULL. Here is the loop above, using one seq and two local variables i and j: 
L := [a,b,c,d,e];
j := 1;
[seq(i=`+`(j, assign('j', j+1)), i=L)];
Notice that I had to add the NULL to j in order to make it all fit in a seq. If this fails, for example if j is a modp1 polynomial, then you can do op([j, assign('j', j+1)]) instead which is slower but more general. Now lets look at the second problem. Nested lists are interesting because they are one way to implement stacks in Maple. The underlying lists [a, [...]] store a pointer to an object and a pointer to a substack. I don't know whether you actually want to use nested lists for stacks (you certainly don't want to display them), but the problems we face here pop up in other settings, for example you may need to extract linked list data from external code. Again the standard solution is a loop and table: 
L := [a, [b, [c, [d, [e]]]]];
M := table():
i := 1:
for i while nops(L) > 1 do
  M[i] := L[1];
  L := L[2];
end do:
M[i] := L[1]:
[seq(M[j], j=1..i)];
The point is that after we extract the leading element we assign the sublist to L. Here it is with a seq: 
L := [a, [b, [c, [d, [e]]]]];
L := [seq(`+`(L[1], assign('L', L[2])), i=1..4), L[1]];
Of course we cheated - how does one know ahead of time how many elements are in L ? The range for seq must be pre-specified and can not be changed, so the only solution for now is to guess and overshoot. Perhaps the Maple kernel developers will consider adding a seqwhile command in the future :) We will use an `if` statement to detect the end of the stack and return NULL. 
L := [a, [b, [c, [d, [e]]]]];
L := [seq(`if`(L=[], NULL, `+`(L[1], `if`(nops(L)=1, assign('L',[]), assign('L', L[2])))), i=1..10)];
This does too many comparisons and is slow. You can speed it up by using an explicit delimiter, where the last list element is [e, []]: 
L := [a, [b, [c, [d, [e, []]]]]];
L := [seq(`if`(L=[], NULL, `+`(L[1], assign('L', L[2]))), i=1..10)];
While we're on the topic, here's how to build that list with a seq. Note that the order must be reversed because we are building a stack. 
L := [e,d,c,b,a];  # input reversed
j := []:
seq(assign('j', [i, j]), i=L):  # outputs nothing
j;  # result
Now for the final problem, which was the original motivation. I want to compute the base b representation of an integer with the sign as the first element. Normally one would use `convert/base` but in my case it was too slow. I had thousands of integers to convert. My solution was based on the following: 
b := 11:
L := [4387324, -9879862, 4237654, -123489321];
# bound the number of base b digits required
k := trunc(evalf(ln(max(seq(abs(i), i=L)))/ln(b)))+1;
[seq([sign(i), assign('t',abs(i)), seq(irem(t, b, 't'), j=1..k)], i=L)];

# here is the code I replaced:
[seq([sign(i), op(convert(abs(i), base, b))], i=L)];
Note that the ceil function is very slow and should be avoided, along with floor, frac, and round. The irem trick is used by `convert/base` as well, however if you time the two methods on large lists you should find that my method is faster because there is much less overhead. Also, if your ultimate goal is to get a matrix of integers, you can use the (faster) rtable constructor instead of the Matrix command because the sublists are all the same size. In my case I was even able to compute the bound k must faster (using ilog2 and iquo) because my base was 2^32. There are many other applications of this "assign in a sequence" technique, and I would be interested to hear what people might have tried.
assign convert integer

Please Wait...