Tree structure with parametric type

General Usage
1

Hello,

I want to build a tree from

abstract type ABC end

struct A{x <: ABC} <: ABC
    a::Vector{x}
end

struct B <: ABC
    a::Vector{Float64}
end

Then I can build the two first layers like this

low1 = [B([0.1, 0.2]), B([0.3,0.4])]
low2 = [B([0.5, 0.6]), B([0.7,0.8])]
mid1 = A{B}(low1)
mid2 = A{B}(low2)

What is the best way to create the next layer ?

top = A{A{B}}([mid1, mid2])

or

top = A{A}([mid1, mid2])

Is there an efficiency gain with the first way or both are equivalent and I should use the second one for simplicity?

Thanks,

Max

2

Both are possible (and different), but neither is ideal, in my opinion. The issue with A{A}(...) is that A is a non-concrete type, so the outer layer will contain a Vector{A} whose elements are non-concrete. That may harm performance.

A{A{B}} does fix that particular issue, but it’s starting to feel like an abuse of the type system. You definitely can do this, but it means, for example, compiling new native code for every layer in the tree (because every layer is a different type).

In RegionTrees.jl I essentially make every node both and A and a B. That is, every node can contain data and/or a vector of children. I use Nullables to keep everything concretely typed, and it seems to work pretty well.

Another option would be to use a small Union:

struct A
  children::Vector{Union{A, B}}
end

struct B
  data::Vector{Float64}
end

In particular, this may end up performing better on Julia v0.7 (nightly) than on the current v0.6 release.

But, really, the most important thing is: there is no single answer to efficiency questions like this. The only way to know for sure what the right approach is is to benchmark it.

1 Like
3

So, if I understand well, you suggest something like

struct A
   data::Nullable{Vector{Float64}}
   children::Nullable{Vector{A}}
end
4

Yeah, that seems like a good option. But I’d definitely try out a few different structures and see which performs well in practice.

5

Good, thank for the advice.