performance - Julia 什么是评估数学树的最快方法

Question

我有一个表示数学函数的数据树，如下所示:

它存储在数组中，因此 2+3^2 将表示为:

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

为了实际评估树，我有一个递归函数

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

(我实际上有一个 Variable 结构，它有一个值和一个标识符来表示数字，所以我可以稍后更改常量)

此代码有效，但速度极慢。我应该采取哪些步骤来优化其性能？我不能使用尾递归，因为该函数通常会调用其自身两次。

谢谢!

-迭戈

Answer 1

语言直接支持树形表示，所以你可以这样写:

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

这将是最快的

但是，如果您想要一个解析器，您可以利用语言的力量并将其作为一个内衬。

我建议您使用以下始终具有 2 个参数的数学树表示:

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

你可以用这个衬里处理所有事情(如果你有 Strings 而不是 Symbols 你总是可以做 Symbol(d[1]) 在我的代码中):

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

现在让我们测试一下:

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

julia> eval(compu(dat))
2555