Julia What is The Fastest Way to Evaluate a Math Tree-CodePudding

I have a tree of data representing a mathematical function, like this:

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

CodePudding user response：

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.