Re: [Caml-list] Choosing a random element in a Map or a Set

[Ivan Gotovchits <ivg@ieee.org>]

[-- Attachment #1: Type: text/plain, Size: 1014 bytes --]

On Thu, Mar 18, 2021 at 5:41 AM <jean-marc.alliot@irit.fr> wrote:

> 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
>

As a side note, in case if you decide to pursue this idea. You don't really
need to take the code as you can implement your solution using the public
interface.
For that, you need only these two public functions: `find_first` and
`split`. The `find_first` function will help us to extract the top element
(`let top t = fst@@find_first (fun _ -> true) t`),
and `let destruct t = split (top t) t` will return you the left and the
right subtrees, and the top element.  The `destruct` function will not
allocate or rebalance any trees and conceptually
will just return pointers to the corresponding subtrees. So it is O(1) both
in space and time.

[-- Attachment #2: Type: text/html, Size: 1420 bytes --]