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

[Nicolas Barnier <barnier@recherche.enac.fr>]

Hi Jean-Marc,

Le 18/03/2021 à 10:44, jean-marc.alliot@irit.fr a écrit :
> 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?

If using a Map or a Set is not compulsory, you can design a data structure
supporting insert, delete, search and random element in constant amortized
time with an extensible array and a hash-table as explained here:

https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/

I don't know if there are any good implementation of (Python-like)
extensible arrays in a widespread OCaml library, but François Pottier
published one as part of another superb data structure (union-find):

https://gitlab.inria.fr/fpottier/unionfind/-/blob/master/src/StoreVector.ml

You may want to adjust the ratio (2 here) by which the array is resized when
necessary.

Hope this helps,

-- Nicolas