Recursive data structures with Julia

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Recursive data structures with Julia

Angel de Vicente
Hi,

I've been trying to implement some code to build Binary Search
Trees. The code below works, I'm able to build a tree and then print it
in ascending order, but it is quite ugly, with those Nullable types and
having to access subtrees with code like tree.value.left instead of
directly tree.left

Being used to nullify a pointer for this, I'm not sure how to best
proceed in Julia. Is there a better way to build recursive data
structures?

(I read the section on "Incomplete Initialization" at
http://docs.julialang.org/en/release-0.5/manual/constructors/, but I'm
not sure I can use the idea in there, since I want some elements of the
tree to point to nothing, not to some other element in the tree.)

Many thanks,
Ángel de Vicente

,----
| julia> include("bst.jl")
| b
|
| julia> tree = b.build_bst([10,2,4,8,2])
| Dropping 2. No repeated values allowed
| Nullable{b.Bst}(b.Bst(10,b.Bst(2,#NULL,b.Bst(4,#NULL,b.Bst(8,#NULL,#NULL))),#NULL))
|
| julia> b.print_bst(tree)
| 2
| 4
| 8
| 10
|
| julia>
`----


,----
| module b
|
| type Bst
|     val::Int
|     left::Nullable{Bst}
|     right::Nullable{Bst}
| end
| Bst(key::Int) = Bst(key, Nullable{Bst}(), Nullable{Bst}())  
|
| "Given an array of Ints, it will create a BST tree, type: Nullable(Bst)"
| function build_bst(list::Array{Int,1})
|     head = list[1]
|     tree = Nullable(Bst(head))
|     for e in list[2:end]
|         place_bst(tree,e)
|     end
|     return tree
| end
|
| "Adds element 'e' in the BST 'tree' (which cannot be a NULL BST)"
| function place_bst(tree::Nullable{Bst},e::Int)
|     if e == tree.value.val
|         println("Dropping $(e). No repeated values allowed")
|     elseif e < tree.value.val
|         if (isnull(tree.value.left))
|             tree.value.left = Nullable(Bst(e))
|         else
|             place_bst(tree.value.left,e)
|         end
|     else
|         if (isnull(tree.value.right))
|             tree.value.right = Nullable(Bst(e))
|         else
|             place_bst(tree.value.right,e)
|         end
|     end
| end
|
| "Prints a BST (does not accept a NULL BST as input)"
| function print_bst(tree::Nullable{Bst})
|     if !isnull(tree.value.left) print_bst(tree.value.left) end
|     println(tree.value.val)
|     if !isnull(tree.value.right) print_bst(tree.value.right) end
| end
|
| end
`----

--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Angel de Vicente
Hi,

by searching in the web I found
(http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia)
a way to make my BST code much cleaner (as posted below). Nevertheless,
I don't find this very ellegant, since the head node is of type Bst,
while the children are of type Nullable{Bst} (is this the 'canonical' way
of building recursive data structures with Julia?).

But when I first read the code in SO, I thought that it was probably
wrong, since it does:

node.left = BST(key)
where node.left is of type Nullable{BST}.

Then I realized that automatic conversion from BST to Nullable{BST} is
done when assigning to node.left, so all is good. Coming from Fortran,
this is a bit odd for me... what are the rules for automatic conversion?  


Thanks a lot,
Ángel de Vicente





,----
| module b
|
| type Bst
|     val::Int
|     left::Nullable{Bst}
|     right::Nullable{Bst}
| end
| Bst(key::Int) = Bst(key, Nullable{Bst}(), Nullable{Bst}())  
|
| "Given an array of Ints, it will create a BST tree, type: Bst"
| function build_bst(list::Array{Int,1})
|     head = list[1]
|     tree = Bst(head)
|     for e in list[2:end]
|         place_bst(tree,e)
|     end
|     return tree
| end
|
| function place_bst(tree::Bst,e::Int)
|     if e == tree.val
|         println("Dropping $(e). No repeated values allowed")
|     elseif e < tree.val
|         if (isnull(tree.left))
|             tree.left = Bst(e)
|         else
|             place_bst(tree.left.value,e)
|         end
|     else
|         if (isnull(tree.right))
|             tree.right = Bst(e)
|         else
|             place_bst(tree.right.value,e)
|         end
|     end
| end
|
| function print_bst(tree::Bst)
|     if !isnull(tree.left) print_bst(tree.left.value) end
|     println(tree.val)
|     if !isnull(tree.right) print_bst(tree.right.value) end
| end
|
| end
`----

,----
| julia> include("bst.jl")
|
| julia> b.print_bst( b.build_bst([4,5,10,3,20,-1,10]))
| Dropping 10. No repeated values allowed
| -1
| 3
| 4
| 5
| 10
| 20
|
| julia>
`----


--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Ralph Smith
Conversion is done by methods listed in base/nullable.jl

I would like to know if there is any drawback to an alternative like

abstract Bst

immutable NullNode <: Bst end

type BstNode <: Bst
    val::Int
    left::Bst
    right::Bst
end

isnull(t::Bst) = isa(t,NullNode)

BstNode(key::Int) = BstNode(key, NullNode(), NullNode())

which appears to be good for type-safety, and is (sometimes) slightly faster and less cumbersome than Nullables.

On Sunday, October 30, 2016 at 6:24:42 PM UTC-4, Ángel de Vicente wrote:
Hi,

by searching in the web I found
(<a href="http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia" target="_blank" rel="nofollow" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F36383517%2Fhow-to-implement-bst-in-julia\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFm2eJUI_akVDpHPpLmwDE-U6D9LA&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F36383517%2Fhow-to-implement-bst-in-julia\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFm2eJUI_akVDpHPpLmwDE-U6D9LA&#39;;return true;">http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia)
a way to make my BST code much cleaner (as posted below). Nevertheless,
I don't find this very ellegant, since the head node is of type Bst,
while the children are of type Nullable{Bst} (is this the 'canonical' way
of building recursive data structures with Julia?).

But when I first read the code in SO, I thought that it was probably
wrong, since it does:

node.left = BST(key)
where node.left is of type Nullable{BST}.

Then I realized that automatic conversion from BST to Nullable{BST} is
done when assigning to node.left, so all is good. Coming from Fortran,
this is a bit odd for me... what are the rules for automatic conversion?  


Thanks a lot,
Ángel de Vicente





,----
| module b
|
| type Bst
|     val::Int
|     left::Nullable{Bst}
|     right::Nullable{Bst}
| end
| Bst(key::Int) = Bst(key, Nullable{Bst}(), Nullable{Bst}())  
|
| "Given an array of Ints, it will create a BST tree, type: Bst"
| function build_bst(list::Array{Int,1})
|     head = list[1]
|     tree = Bst(head)
|     for e in list[2:end]
|         place_bst(tree,e)
|     end
|     return tree
| end
|
| function place_bst(tree::Bst,e::Int)
|     if e == tree.val
|         println("Dropping $(e). No repeated values allowed")
|     elseif e < tree.val
|         if (isnull(tree.left))
|             tree.left = Bst(e)
|         else
|             place_bst(tree.left.value,e)
|         end
|     else
|         if (isnull(tree.right))
|             tree.right = Bst(e)
|         else
|             place_bst(tree.right.value,e)
|         end
|     end
| end
|
| function print_bst(tree::Bst)
|     if !isnull(tree.left) print_bst(tree.left.value) end
|     println(tree.val)
|     if !isnull(tree.right) print_bst(tree.right.value) end
| end
|
| end
`----

,----
| julia> include("bst.jl")
|
| julia> b.print_bst( b.build_bst([4,5,10,3,20,-1,10]))
| Dropping 10. No repeated values allowed
| -1
| 3
| 4
| 5
| 10
| 20
|
| julia>
`----


--
Ángel de Vicente
<a href="http://www.iac.es/galeria/angelv/" target="_blank" rel="nofollow" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;">http://www.iac.es/galeria/angelv/          
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

John Myles White
Working with non-concrete types is often a problem for performance, so this approach may not be very efficient compared with alternatives that are more careful about the use of concrete types.

 --John

On Sunday, October 30, 2016 at 6:27:47 PM UTC-7, Ralph Smith wrote:
Conversion is done by methods listed in base/nullable.jl

I would like to know if there is any drawback to an alternative like

abstract Bst

immutable NullNode <: Bst end

type BstNode <: Bst
    val::Int
    left::Bst
    right::Bst
end

isnull(t::Bst) = isa(t,NullNode)

BstNode(key::Int) = BstNode(key, NullNode(), NullNode())

which appears to be good for type-safety, and is (sometimes) slightly faster and less cumbersome than Nullables.

On Sunday, October 30, 2016 at 6:24:42 PM UTC-4, Ángel de Vicente wrote:
Hi,

by searching in the web I found
(<a href="http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia" rel="nofollow" target="_blank" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F36383517%2Fhow-to-implement-bst-in-julia\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFm2eJUI_akVDpHPpLmwDE-U6D9LA&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F36383517%2Fhow-to-implement-bst-in-julia\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFm2eJUI_akVDpHPpLmwDE-U6D9LA&#39;;return true;">http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia)
a way to make my BST code much cleaner (as posted below). Nevertheless,
I don't find this very ellegant, since the head node is of type Bst,
while the children are of type Nullable{Bst} (is this the 'canonical' way
of building recursive data structures with Julia?).

But when I first read the code in SO, I thought that it was probably
wrong, since it does:

node.left = BST(key)
where node.left is of type Nullable{BST}.

Then I realized that automatic conversion from BST to Nullable{BST} is
done when assigning to node.left, so all is good. Coming from Fortran,
this is a bit odd for me... what are the rules for automatic conversion?  


Thanks a lot,
Ángel de Vicente





,----
| module b
|
| type Bst
|     val::Int
|     left::Nullable{Bst}
|     right::Nullable{Bst}
| end
| Bst(key::Int) = Bst(key, Nullable{Bst}(), Nullable{Bst}())  
|
| "Given an array of Ints, it will create a BST tree, type: Bst"
| function build_bst(list::Array{Int,1})
|     head = list[1]
|     tree = Bst(head)
|     for e in list[2:end]
|         place_bst(tree,e)
|     end
|     return tree
| end
|
| function place_bst(tree::Bst,e::Int)
|     if e == tree.val
|         println("Dropping $(e). No repeated values allowed")
|     elseif e < tree.val
|         if (isnull(tree.left))
|             tree.left = Bst(e)
|         else
|             place_bst(tree.left.value,e)
|         end
|     else
|         if (isnull(tree.right))
|             tree.right = Bst(e)
|         else
|             place_bst(tree.right.value,e)
|         end
|     end
| end
|
| function print_bst(tree::Bst)
|     if !isnull(tree.left) print_bst(tree.left.value) end
|     println(tree.val)
|     if !isnull(tree.right) print_bst(tree.right.value) end
| end
|
| end
`----

,----
| julia> include("bst.jl")
|
| julia> b.print_bst( b.build_bst([4,5,10,3,20,-1,10]))
| Dropping 10. No repeated values allowed
| -1
| 3
| 4
| 5
| 10
| 20
|
| julia>
`----


--
Ángel de Vicente
<a href="http://www.iac.es/galeria/angelv/" rel="nofollow" target="_blank" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;">http://www.iac.es/galeria/angelv/          
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Angel de Vicente
In reply to this post by Ralph Smith
Hi Ralph,

Ralph Smith <[hidden email]> writes:
> Conversion is done by methods listed in base/nullable.jl

OK, but more than the conversion rules I was wondering about when
conversion will be invoked. Conversion does not happen when calling a
function (so, in this example a function expecting a Nullable{BST} but
given a BST will not work), but it does happen when used in an
expression (as the one I mentioned node.left = BST(key) which gets
converted to Nullable{BST}). Not sure if there are any other subtleties
that I should be aware of.

Thanks,
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Barnes-Hut N-body simulations (was recursive data structures with Julia)

Angel de Vicente
In reply to this post by Angel de Vicente
Hi,

Angel de Vicente <[hidden email]> writes:
> Being used to nullify a pointer for this, I'm not sure how to best
> proceed in Julia. Is there a better way to build recursive data
> structures?

OK, so this was just a test example to go for something bigger, and by
using the cleaner version with Nullable fields I implemented a basic
code to perform a Barnes-Hut N-body simulation
(https://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation)

The good think is that it works OK, and development while being able to
use the REPL accelerates coding so much (in comparison to compiled
languages), but the bad news is that it is ~25x slower than my own
Fortran version :-( (I have tried to make all functions type stable and
I have followed the same algorithm as in the Fortran version).

I haven't done any code profiling yet, so I don't know which parts of
the code are so expensive, but I will try to investigate these days...

Any pointers/help on how to best proceed to identify bottlenecks and how
to get rid of them in Julia are most welcome.

Thanks,
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Jeffrey Sarnoff
In reply to this post by John Myles White
John,

Currently (v0.5) :
Which uses of non-concrete types are performance friendly?
What ways of using abstract types are a drag on performance?

Regards, Jeffrey


On Sunday, October 30, 2016 at 9:38:15 PM UTC-4, John Myles White wrote:
Working with non-concrete types is often a problem for performance, so this approach may not be very efficient compared with alternatives that are more careful about the use of concrete types.

 --John

On Sunday, October 30, 2016 at 6:27:47 PM UTC-7, Ralph Smith wrote:
Conversion is done by methods listed in base/nullable.jl

I would like to know if there is any drawback to an alternative like

abstract Bst

immutable NullNode <: Bst end

type BstNode <: Bst
    val::Int
    left::Bst
    right::Bst
end

isnull(t::Bst) = isa(t,NullNode)

BstNode(key::Int) = BstNode(key, NullNode(), NullNode())

which appears to be good for type-safety, and is (sometimes) slightly faster and less cumbersome than Nullables.

On Sunday, October 30, 2016 at 6:24:42 PM UTC-4, Ángel de Vicente wrote:
Hi,

by searching in the web I found
(<a href="http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia" rel="nofollow" target="_blank" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F36383517%2Fhow-to-implement-bst-in-julia\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFm2eJUI_akVDpHPpLmwDE-U6D9LA&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fquestions%2F36383517%2Fhow-to-implement-bst-in-julia\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFm2eJUI_akVDpHPpLmwDE-U6D9LA&#39;;return true;">http://stackoverflow.com/questions/36383517/how-to-implement-bst-in-julia)
a way to make my BST code much cleaner (as posted below). Nevertheless,
I don't find this very ellegant, since the head node is of type Bst,
while the children are of type Nullable{Bst} (is this the 'canonical' way
of building recursive data structures with Julia?).

But when I first read the code in SO, I thought that it was probably
wrong, since it does:

node.left = BST(key)
where node.left is of type Nullable{BST}.

Then I realized that automatic conversion from BST to Nullable{BST} is
done when assigning to node.left, so all is good. Coming from Fortran,
this is a bit odd for me... what are the rules for automatic conversion?  


Thanks a lot,
Ángel de Vicente





,----
| module b
|
| type Bst
|     val::Int
|     left::Nullable{Bst}
|     right::Nullable{Bst}
| end
| Bst(key::Int) = Bst(key, Nullable{Bst}(), Nullable{Bst}())  
|
| "Given an array of Ints, it will create a BST tree, type: Bst"
| function build_bst(list::Array{Int,1})
|     head = list[1]
|     tree = Bst(head)
|     for e in list[2:end]
|         place_bst(tree,e)
|     end
|     return tree
| end
|
| function place_bst(tree::Bst,e::Int)
|     if e == tree.val
|         println("Dropping $(e). No repeated values allowed")
|     elseif e < tree.val
|         if (isnull(tree.left))
|             tree.left = Bst(e)
|         else
|             place_bst(tree.left.value,e)
|         end
|     else
|         if (isnull(tree.right))
|             tree.right = Bst(e)
|         else
|             place_bst(tree.right.value,e)
|         end
|     end
| end
|
| function print_bst(tree::Bst)
|     if !isnull(tree.left) print_bst(tree.left.value) end
|     println(tree.val)
|     if !isnull(tree.right) print_bst(tree.right.value) end
| end
|
| end
`----

,----
| julia> include("bst.jl")
|
| julia> b.print_bst( b.build_bst([4,5,10,3,20,-1,10]))
| Dropping 10. No repeated values allowed
| -1
| 3
| 4
| 5
| 10
| 20
|
| julia>
`----


--
Ángel de Vicente
<a href="http://www.iac.es/galeria/angelv/" rel="nofollow" target="_blank" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;">http://www.iac.es/galeria/angelv/          
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Barnes-Hut N-body simulations (was recursive data structures with Julia)

Angel de Vicente
In reply to this post by Angel de Vicente
Hi,

Angel de Vicente <[hidden email]> writes:

> OK, so this was just a test example to go for something bigger, and by
> using the cleaner version with Nullable fields I implemented a basic
> code to perform a Barnes-Hut N-body simulation
> (https://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation)
>
> The good think is that it works OK, and development while being able to
> use the REPL accelerates coding so much (in comparison to compiled
> languages), but the bad news is that it is ~25x slower than my own
> Fortran version :-( (I have tried to make all functions type stable and
> I have followed the same algorithm as in the Fortran version).

after playing a little bit with the profiler, following some of the
advice in
http://docs.julialang.org/en/release-0.5/manual/performance-tips/ and
doing some very minor changes to the code, these
are the times (the best of three runs in all cases) for a test run of
the code (100 time steps, 1000 bodies):

Fortran: compiled with gfortran -O0  2.72s
                       gfortran -O3  1.29s

         compiled with ifort -O0     4.73s
                       ifort -O3     1.17s

Julia:   v.0.5                       3.85s
         (first run ignored to avoid first compilation time)


So my Julia version now takes ~3x the time of the Fortran one. Probably
I could improve it even further, but given that I'm still very new to
Julia this is not bad at all, I think.

Good stuff!
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

hubert_tieying
In reply to this post by Angel de Vicente


Am Donnerstag, 27. Oktober 2016 16:03:27 UTC+2 schrieb Ángel de Vicente:
Hi,

I've been trying to implement some code to build Binary Search
Trees. The code below works, I'm able to build a tree and then print it
in ascending order, but it is quite ugly, with those Nullable types and
having to access subtrees with code like tree.value.left instead of
directly tree.left      
 Here is a variant for a binary search tree which uses union types and also has an empty tree. The definition is straightforward and - at least for me - easy to understand.


type Empty
end

et
= Empty()  # a possible variant for an empty tree

typealias BT
{T}  Union{T, Empty}

type
BTree
    key
::Int
    left
:: BT{BTree}
    right
::BT{BTree}
end

BST
= BT{BTree} # type of binary search trees

BTree(key::Int) = BTree(key, et, et):: BST


function insert(t::BST, val)
   
if t == et
       
return BTree(val)
    elseif val
< t.key
       
return BTree(t.key, insert(t.left,val), t.right)
   
else  
       
return BTree(t.key, t.left, insert(t.right,val))
   
end
end

# Testing:
# arr = [9,15,-4,3,11,6,-2,-16]
# tr = et
# for a in arr
#      tr = insert(tr,a)
# end
# tr


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Angel de Vicente
Hi,

[hidden email] writes:

>     Hi,
>        
>         I've been trying to implement some code to build Binary Search
>         Trees. The code below works, I'm able to build a tree and then print it
>         in ascending order, but it is quite ugly, with those Nullable types and
>         having to access subtrees with code like tree.value.left instead of
>         directly tree.left
>
> Here is a variant for a binary search tree which uses union types and also has
> an empty tree. The definition is straightforward and - at least for me - easy to
> understand.

OK, thanks for the suggestion. So, I ended up having three different
ways of constructing BSTs, and decided to test how they perform. The
three different methods are:

1.- my suggestion with Nullables (as per mail of Oct 30)
2.- the method with non-concrete types suggested by Ralph Smith (as per
      mail of Oct 31)
3.- your suggestion with union types
   a- your way of building the tree
   b- modified way of building the tree


3b uses your idea of union types but build the tree as follows:

,----
| function build_bst3(list::Array{Int,1})
|     head = list[1]
|     tree = Bst3(head)
|     for e in list[2:end]
|         place_bst3(tree,e)
|     end
|     return tree
| end
|
| function place_bst3(tree::BST,e::Int)
|     if e == tree.val
| #       println("Dropping $(e). No repeated values allowed")
|     elseif e < tree.val
|         if tree.left == et
|             tree.left = Bst3(e)
|         else
|             place_bst3(tree.left,e)
|         end
|     else
|         if tree.right == et
|             tree.right = Bst3(e)
|         else
|             place_bst3(tree.right,e)
|         end
|     end
| end
`----


I created an array with 1e5 unique values
test=unique(rand(1:Int(1e11),100000))

And this is the time it takes for each method:

Times to build the tree (best of 10 runs):
-----
Method 1:  0.125s
Method 2:  0.154s
Method 3a: 0.393s
Method 3b: 0.191s    


Times to traverse the tree (count number of nodes):
----
Method 1: 0.017s
Method 2: 0.008s
Method 3: 0.017s


Given this, for the N-body code that I wrote I would actually go for
Method 2, since for each iteration I build the tree once but then I use
it many times (once per particle), so it should probably be the fastest.


Cheers,
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Páll Haraldsson
In reply to this post by Angel de Vicente
On Thursday, October 27, 2016 at 2:03:27 PM UTC, Ángel de Vicente wrote:
Hi,

I've been trying to implement some code to build Binary Search Trees.

Is this a genuine need or an exercise? I quickly looked at Datastructures.jl:

"The containers internally use a 2-3 tree, which is a kind of balanced tree and is described in many elementary data structure textbooks."

Maybe you use their code or learn from it (assuming they best solve your Nullable problem; that I didn't look into), or maybe you can help them if your data structure is really needed.


--
Ángel de Vicente
<a href="http://www.iac.es/galeria/angelv/" target="_blank" rel="nofollow" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.iac.es%2Fgaleria%2Fangelv%2F\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHWgWJwB7xZkScAhM-XaTehlCOVww&#39;;return true;">http://www.iac.es/galeria/angelv/          
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Recursive data structures with Julia

Angel de Vicente
Hi,

Páll Haraldsson <[hidden email]> writes:
>     I've been trying to implement some code to build Binary Search Trees.
>
> Is this a genuine need or an exercise? I quickly looked at Datastructures.jl:

a genuine need (well, not really the BSTs, but recursive data structures
in general. In this thread I have another post where I explain that the
goal for this was to implement a Barnes-Hut N-body simulation code, for
which I need octtrees).

> "The containers internally use a 2-3 tree, which is a kind of balanced tree and
> is described in many elementary data structure textbooks."
>
> Maybe you use their code or learn from it (assuming they best solve your
> Nullable problem; that I didn't look into), or maybe you can help them if your
> data structure is really needed.

thanks, I will look into Datastructures.jl (though by now I already have
three alternative ways of implementing BSTs, as I posted this morning).

Thanks,
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/         
Loading...