朱莉娅 评估数学树的最快方法是什么

Question

我有一个代表数学函数的数据树，如下所示：\n

\n

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

\n

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

\n

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

\n

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

\n

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

\n

这段代码可以工作，但是速度非常慢。我应该采取哪些步骤来优化其性能？我无法使用尾递归，因为该函数通常会调用其自身两次。

\n

谢谢你！

\n

-迭戈

\n

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