julia - Julia 中的多参数递归类型和类型推断

Question

我已经创建了这种数据结构

abstract type Node end

struct Tree{A <: Node, B <: Node} <: Node
    a::A
    b::B
end

这种类型的结构使我可以方便地按子节点的类型来寻址树的节点。

作为一个例子，我可以有

struct Character <: Node
    c::Char
end

并制作一个专门的方法来识别一棵有两个Character孩子的树

function test(node::Tree{Character, Character}) end

但我也可以潜在地定义一个函数，比如

function test(node::Tree{Tree{Character, Character}, Tree}) end

其中地址 aTree最左边的分支包含两个Character和一个任意Tree的在右边。

我的实现以类似的方式调度了许多方法。

这种类型的结构有效，但对于相当大的树，我注意到一些减速，尤其是在尝试使用typeof. 这种模式被认为是有效的吗？如果没有，有没有办法让它更有效率？

标签： julia

Answer 1

根据特定场景，可能会有很多关于树定义的建议。但是，您肯定希望避免导致性能不佳的递归嵌套类型结构。

这是我的建议。这个二叉树可以保存任何类型的数据T

struct Tree{T}
    val::T
    a::Union{Tree{T}, Nothing}
    b::Union{Tree{T}, Nothing}
end

Tree(val::A) where A=Tree{A}(val,nothing,nothing)

leaf1 = Tree(4)
leaf2 = Tree(5)
subb1 = Tree(555,leaf1,leaf2)
tree = Tree(1000,subb1, Tree(888))

现在让我们看看那棵树：

juila> dump(tree)
Tree{Int64}
  val: Int64 1000
  a: Tree{Int64}
    val: Int64 555
    a: Tree{Int64}
      val: Int64 4
      a: Nothing nothing
      b: Nothing nothing
    b: Tree{Int64}
      val: Int64 5
      a: Nothing nothing
      b: Nothing nothing
  b: Tree{Int64}
    val: Int64 888
    a: Nothing nothing
    b: Nothing nothing