Dear list,
I am trying to take a random element from a Map or a Set.
Currently, I generate one random int between 1 et Card(map), and I iter
until I reach this element. The solution is in O(n) which is not great...
I was about to code the following solution: take the current Map code
and add a function which follows the balanced binary tree from the root
and takes randomly a left or right turn at each node until we reach a
leaf (we only need to generate one random int and use its binary
representation to choose the left or right direction at each node). This
should be in O(log(n))
Before I start coding like an idiot:
1) Is there another, more intelligent, solution?
I would create an array of keys and then randomly choose a key from that array. If you want to be on the functional side, you can shuffle the array and turn it into a list.
This solution involves some duplication but is easy to implement and is especially useful if you do not what repetitions in your selection.
An alternative solution that doesn't suffer from an extra memory overhead would be writing a function that generates a random key (instead of a random integer). It is not always possible,
especially when the domain of keys is infinite. However, if your set/map is total (i.e., maps all keys in the domain to values) then it is the perfect solution.
Finally, as an amalgamation of the above approaches, you can hash-cons your keys (essentially turning keys into integers). It usually involves an extra data structure to maintain your index,
but gives you the additional benefits of hash-consing, e.g., faster and tighter maps and sets.
2) Is my solution biased? I think it is not, as long as the tree is
properly balanced but...
OCaml trees are relaxed AVL trees with the maximum difference between trees height equal to 2 (not 1 as in classical AVL). For small trees, it is quite a substantial difference, e.g., imagine a tree of 9 elements with the left tree having a height of 3 and the right of height 1.
The right tree will have only one element and the left will have 7 elements. Therefore, the probability of selecting the right element will be 1/2 vs 1/9. Even for larger trees, it remains the problem as a large tree is made of small subtrees :) Therefore your probability distribution
will be far from uniform.
Thanks
Jean-Marc