Suppose the data that you want to collect is generated element-by-element
and you know in advance how many elements will be generated. The intuitive
approach for collecting such data is to create an empty list and append
each new element to the end of the list. For example, this procedure
uses this approach to collect random integers generated by
col := proc(n) local L, i; begin L := ; for i from 1 to n do L := L.[random()]; end_for; end:
The procedure generates random integers and collects them in a list:
To estimate the performance of this approach, use the procedure
generate a list of 50,000 random numbers:
returns results measured in milliseconds.
Now, check how much time the procedure actually spends generating random numbers:
time(random() $ i = 1..50000)
Thus, the procedure spends most of the time appending the newly
generated numbers to a list. In MuPAD®, appending a new entry
to a list of
n entries takes time proportional
n. Therefore, run time of
proportional to n2.
You can visualize this dependency by plotting the times that
when creating lists of 1 to 50,000 entries:
plotfunc2d(n -> time(col(n)), n = 1..50000, Mesh = 20, AdaptiveMesh = 0)
When appending a new entry to a list, MuPAD allocates space
for the new, longer list. Then it copies all entries of the old list
plus a new entry to this new list. The faster approach is to create
the entire list at once, without adding each new entry separately.
This approach is called parallel collection because
you create and collect data simultaneously. Use the sequence operator
implement this approach:
col := proc(n) local i; begin [random() $ i = 1..n]; end:
This procedure spends most of its time generating random numbers:
Suppose you know how many elements you will generate, but you
cannot generate them all at once. In this case, the best strategy
is to create a list of the required length filling it with some constant,
such as 0 or
Then you can replace any entry of this list with the generated value.
In this case, you do not need to generate elements in the order in
which you want them to appear in the list.
For example, use this procedure to generate the list of the
n Lucas numbers. The procedure creates a
n entries, where each entry is 0. Then
it assigns the values to the first two entries. To replace all other
entries of the list with the Lucas numbers, the procedure uses the
lucas := proc(n) local L, i; begin L := [0 $ n]; L := 1; L := 3; for i from 3 to n do L[i] := L[i-1] + L[i-2]; end_for; L end:
Measure the time needed to create a list of 10,000 Lucas numbers:
If you use the procedure that creates an empty list and appends each generated Lucas number to this list, then creating a list of 10,000 Lucas numbers takes much longer:
lucas := proc(n) local L, i; begin L := ; L :=L.; L := L.; for i from 3 to n do L := L.[L[i-1] + L[i-2]]; end_for; L end:
If you cannot predict the number of elements that you will generate, but have a reasonable upper limit on this number, use this strategy:
Create a list with the number of entries equal to or greater than the upper limit.
Generate the data and populate the list.
Discard the unused part of the list.
For example, use the following procedure to create a list. The
entries of this list are modular squares of a number
a (a2 mod n).
You cannot predict the number of entries in the resulting list because
it depends on the parameters
Nevertheless, you can see that in this case the number of entries
in the list cannot exceed
modPowers := proc(a, n) local L, i; begin L := [0 $ n]; L := a; L := a^2 mod n; i := 2; while L[i] <> a do L[i + 1] := a*L[i] mod n; i := i + 1; end_while; L := L[1..i - 1]; end:
When you call
a = 2, it creates two lists of
modPowers(3, 14); modPowers(2, 14)
Often, you cannot predict the number of elements and cannot estimate the upper limit on this number before you start generating actual data. One way of dealing with this problem is to choose some upper limit, and use the strategy described in Known Maximum Length Collection. If that limit is reached, then:
Choose a larger limit.
Create a new list with the number of elements corresponding to the new limit.
Copy existing collected data to the new list.
Typically, increasing the list length by a constant factor results in better performance than increasing it by a constant number of entries:
rndUntil42 := proc() local L, i; begin i := 1; L := [random()]; while L[i] mod 42 <> 0 do if i = nops(L) then L := L.L; end_if; i := i+1; L[i] := random(); end_while; L[1..i]; end:
SEED := 123456789: rndUntil42()
SEED := 123456789: time(rndUntil42() $ i = 1..500)
Alternatively, if you cannot predict the number of elements
that you will need to collect, then use a
table that grows automatically (a hash
rndUntil42 := proc() local L, i, j; begin i := 1; L := table(1 = random()); while L[i] mod 42 <> 0 do i := i+1; L[i] := random(); end_while; [L[j] $ j=1..i]; end:
SEED := 123456789: time(rndUntil42() $ i = 1..500)
For this example, using the table is slightly faster. If you change the value 42 to another value, using the list might be faster. In general, tables are preferable when you collect large amounts of data. Choose the approach that works best for solving your problem.