Tree random element

Learning Questions & Discussions Coding Challenges
, ,
1

Trees (specially gb_trees) are a very efficient/fast tool to store Key-Value. However, depending on the program it’s usage cat get a bit more complicated.

Here goes my challenge.
What would be the most efficient way to get a random element and it’s path from a gb_tree?

2

:gb_trees.iterator/1 plus a reservoir sampling algorithm?

3

The idea is good if we don’t want to cover the whole tree (just the k first), however to cover the whole tree, wouldn’t we have to execute rand:random() in each iteration (rand operations are quite expensive)?

4

So after thinking about it, my solution would be something like this:

iex(1)> tree = :gb_tree.example() #Any f that returns a tree
{3, {:a, 1, nil, {:b, 2, nil, {:c, 3, nil, nil}}}}
iex(2)> n = :rand.uniform(:gb_trees.size(tree))
2
iex(11)> iter = :gb_trees.iterator(tree) 
[{:a, 1, nil, {:b, 2, nil, {:c, 3, nil, nil}}}]
iex(14)> {k,v,_}=Enum.reduce(1..n, {:nil,:nil,:gb_trees.iterator(tree)}, fn _, {_,_,i} -> :gb_trees.next(i) end)
{:b, 2, [{:c, 3, nil, nil}]}

However I am thinking, now gb_trees are not used any longer as we do have maps.