Julia What is The Fastest Way to Evaluate a Math Tree

user_14073246 0
Viewed 77

I have a tree of data representing a mathematical function, like this: enter image description here

It is stored in arrays, so 2+3^2 would be represented as:

["+", 2, ["^2", 3] ]

To actually evaluate the tree, I have a recursive function

function evaluate(mathstructure::Array)
    if mathstructure[1] == "+"
        # do the operation
        evaluate(mathstructure[2]) + evaluate(mathstructure[3])
    elseif mathstructure[1] == "*"
        # do the operation
        evaluate(mathstructure[2]) * evaluate(mathstructure[3])
    elseif mathstructure[1] == "σ"
        # do the operation
        x = evaluate(mathstructure[2])
        1 / (1 + exp(-x))
    elseif mathstructure[1] == "^2"
        # do the operation
        x = evaluate(mathstructure[2])
        x^2
    end
end
function evaluate(mathstructure::Variable)
    mathstructure.value
end

(I actually have a Variable structure which has a value and an identifier to represent numbers, so I can change constants later)

This code works, but it is extremely slow. What steps should I take to optimize its performance? I can't use tail recursion because oftentimes the function calls its self twice.

Thank you!

-Diego

julia data-structures performance
3 Answers

The tree representation is directly supported by the language so you can just write something like:

+(^(*(5,10),2),+(30,25))

This will be the fastest

However if you want a parser you could leverage the power of language and to this as a one liner.

I propose you the following representation of math tree having always 2 arguments:

dat = [:+,[:^,[:*, 5, 10],2], [:+, 30, 25]]

Than you can handle all with this one liner (should you have Strings instead of Symbols you could always do Symbol(d[1]) in my code):

compu(d) = quote
    $(d[1])($(typeof(d[2])<:AbstractVector ? compu(d[2]) : d[2]), $(typeof(d[3])<:AbstractVector ? compu(d[3]) : d[3]))
end

Now lets test it:

julia> (+(^(*(5,10),2),+(30,25) ))
2555

julia> eval(compu(dat))
2555
user_99577100

I think you can get better performance if you make use of Julia's multiple dispatch, using tuples as your main type instead of heterogenous arrays.

julia> using BenchmarkTools

julia> evaluate(x::Number) = x
evaluate (generic function with 1 method)

julia> function evaluate(ex::Tuple{Symbol,Union{Tuple,Number}})
           (op, x_) = ex
           x = evaluate(x_)
           if op == :σ
               return 1 / (1 + exp(-x))
           elseif op == Symbol("^2")
               return x ^ 2
           else
               error("invalid unary operator $(op)")
           end
       end
evaluate (generic function with 2 methods)

julia> function evaluate(ex::Tuple{Symbol,Union{Number,Tuple},Union{Number,Tuple}})
           (op, x_, y_) = ex
           (x, y) = evaluate.((x_, y_))
           if op == :(+)
               return x + y
           elseif op == :(*)
               return x * y
           else
               error("invalid binary operation $(op)")
           end
       end
evaluate (generic function with 3 methods)

julia> evaluate((:+, 2, (Symbol("^2"), (:*, 4, (:σ, 9)))))
17.99605161718798

julia> 2 + (4 * 1/(1+exp(-9)))^2
17.99605161718798

julia> @benchmark evaluate((:+, 2, (Symbol("^2"), (:*, 4, (:σ, 9)))))
BenchmarkTools.Trial: 10000 samples with 998 evaluations.
 Range (min … max):  14.893 ns … 57.041 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     14.947 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   15.465 ns ±  2.190 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █   ▂    ▅                                                  ▁
  █▁█▃█▁▃▁▁█▅▄▄▄▃▁▁▁▁▁▃▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▄▅▅▇▆▆▆▆▆▆▆ █
  14.9 ns      Histogram: log(frequency) by time      25.6 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.
user_54964330

A bit of a frame challenge, but depending on your high-level goals you could consider not inventing your own expression system, but reuse something like Symbolics.jl.

Symbolic algebra packages usually have built-in support for expression simplification and "compilation" to native functions, such as Symbolics' build_function (which is more or less a fancy version of Przemyslaw's answer, but may result in much better optimized code if you expressions involve things like large arrays).

user_13462760
Related