Counting elementary operations required by algorithm

[Alexey Tikhonov]

Hello!

One day I had to evaluate several algorithms solving the same problem to find the most effective one. I implemented them all and compared the time each algorithm took to get the result. But computational time is not a reliable metric - it can be different for several consecutive runs. What I really wanted to demonstrate was the number of elementary operations that each of the algorithms used to solve the problem. Can I write in Ela such "operations counter" to compare, for instance, elementary operations in quick sort algorithm (comparisons + swappings) and in bubble sort?

Alexey

[vorov2]

There is probably no universal approach here. The most straightforward way would be to count each occurrence of an operation with some debugging function. You can use a dirty function or an IO monad. You can use overloaded operations so that each invocation of an operation (such as a special version of multiplication or division) would do the math *and* put a record somewhere counting total number of operations. Same staff can be done with custom numeric type with all standard operations being overloaded for it.

By the way standard library already does something similar with symbolic module:

open symbolic math

show $ vdc 10s 12s

/*The result is:
"(0d + ((12d % 10d) / (1d * 10d))) + (((truncate (12d / 10d)) % 10d) / ((1d * 10d) * 10d))"
*/

vds here  is a regular function which, when invoked with a symbolic number (note the literal with "s" postfix), would return a sort of an AST with all the operations in a tree instead of the operation result. This AST is then formatted to string using "show" function.

[Alexey Tikhonov]

Thanks for your example. Static analysis is a good starting point but AST does not tell how many times a conditional branch will be visited during calculation. I was thinking of creating a custom "float point number" type with incorporated statistics in it:

<<meta code>>

type my_number

value

additions_counter

subtractions_counter

mults_counter

divisions_counter
...

end type

Next step would be overloading the standard operators for this type using Ela classes so that the result of every binary operation (+, -, /, *) is a new my_number with accumulated statistics. It may be enough. If it works) Then this type can be used to compare, for instance, different algorithms of solving systems of linear equations. I would try it first.

For sorting algorithms its interesting to count comparisons and swappings. To track the comparisons I would use a dirty function. How to deal with swappings - it is a philosophical question) Unfortunatly, the algorithms I compared use sorting and without accounting for these type of operations the comparison will not be full.

[ba...@voronkov.name]

Sorry, I am afraid I have used a misleading term here. “symbolic” doesn’t evaluate calculations but instead represent all of them in the form of a graph. This graph is implemented through algebraic type and therefore can be pattern matched. So you can basically see the number of primitive operations and count them, e.g.:

 

open number symbolic math

calc 0u x = x

calc n x = calc (n - 1u) (x + 1u)

show $ calc 10s 12s ::: Sym

 

Output is:

 

(((((((((12d + 1d) + 1d) + 1d) + 1d) + 1d) + 1d) + 1d) + 1d) + 1d) + 1d

 

Not sure though that symbolic would do the job for you but you can take a look how symbolic is implemented. It is basically a custom number that (by default) doesn’t evaluate operations but instead constructs a graph (that can be evaluated later using ‘eval’ function). It can be a good starting point for your own numeric type.

--

---
You received this message because you are subscribed to the Google Groups "elalang" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elalang+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.