Documentation |
On this page… |
---|
The simplest tool you can use to estimate code performance is the time function. This function measures the running time of your code snippet. The time function does not count the time spent outside of MuPAD^{®} processes: external function calls or processes running in the background do not affect the results of time. The function returns results measured in milliseconds.
The following example demonstrates different algorithms implemented for the same task. The task is to check whether each integer from 1 to 1000 appears in a 1000×1000 matrix of random integers. To create a 1000×1000 matrix of random integers, use linalg::randomMatrix:
matrixSize := 1000: M := linalg::randomMatrix(matrixSize, matrixSize, Dom::Integer):
The direct approach is to write a procedure that checks every element of a matrix proceeding row by row and column by column:
f := proc(M, n, x) begin for j from 1 to n do for k from 1 to n do if M[j, k] = x then return(TRUE) end_if end_for end_for; return(FALSE) end_proc:
Call the procedure f 1000 times to check if each number from 1 to 1000 appears in that matrix:
g := proc() begin f(M, matrixSize, i) $ i = 1..1000 end_proc:
This algorithm is very inefficient for the specified task. The function f performs 10^{4} computation steps to find out that an integer does not occur in the matrix M. Since you call the function f 1000 times, executing this algorithm takes a long time:
time(g())
62435.902
In this example, the bottleneck of the chosen approach is obviously the algorithm that accesses each matrix element. To accelerate the computation, rewrite the procedure f using the bisection method. Before using this method, convert the matrix M to a list and sort the list. Then select the first and last elements of the sorted list as initial points. Each step in this algorithm divides the list of elements at the midpoint:
f := proc(M, n, x) begin if (M[1] - x)*(M[n] - x) > 0 then return(FALSE) elif (M[1] - x)*(M[n] - x) = 0 then return(TRUE); else a := 1: b := n: while (b - a > 1) do if is(b - a, Type::Odd) then c := a + (b - a + 1)/2 else c := a + (b - a)/2 end_if; if M[c] - x = 0 then return(TRUE) elif (M[a] - x)*(M[c] - x) < 0 then b := c: else a := c: end_if; end_while; end_if; return(FALSE) end_proc:
Use the op function to access all elements of the matrix M. This function returns a sequence of elements. Use brackets to convert this sequence to a list. Then use the sort function to sort the list in ascending order. Finally, call the procedure f for each integer from 1 to 1000:
g := proc() local M1; begin M1 := sort([op(M)]): f(M1, matrixSize^2, i) $ i = 1..1000 end_proc:
Using the bisection method instead of accessing each matrix element significantly improves the performance of the example:
time(g())
3724.233
Typically, the best approach is to use the appropriate MuPAD functions whenever possible. For example, to improve performance further, rewrite the code using the MuPAD function has. Also, converting a matrix to a set can reduce the number of elements. (MuPAD removes duplicate elements of a set.) In addition to speed up, this approach makes your code significantly shorter and easier to read:
g := proc() local M1; begin M1 := {op(M)}: has(M1, i) $ i = 1..1000 end_proc:
In this case, execution time is even shorter than for the code that implements the bisectional method:
time(g())
1508.094
Results returned by the time function exclude the time spent on calls to external programs. If your code uses external programs, you can measure the total time spent by that code, including calls to external processes. To measure the total time, use the rtime function instead of time. For example, the function call rtime() returns the elapsed time of the current MuPAD session. This time includes idle time of the current session:
t := rtime(): print(Unquoted, "This session runtime is ".stringlib::formatTime(t))
This session runtime is 5 minutes, 25.579 seconds
When measuring code performance using rtime, avoid running other processes in the background. Also ensure that enough memory is available. The rtime function counts the total time, including idle time during which some other process uses the CPU or your computer swaps data between different types of memory.