How can I randomly select an element in Ocaml?

Question

In my program in OCaml, I need to randomly select a string from a huge set of strings. I've tried two different ways of doing this so far, each with little success. I first stored all of the strings into a list and then would randomly select an element from the list:

let randomelement l =
    List.nth l (Random.int (List.length l))

But this takes a long time if it selects the 1000th string in the list. So I put it all into a set, thinking that Set.choose would return a random element from the set. But that doesn't seem to be working. I guess I have two questions...how does Set.choose work, and is there a better way to randomly select an element in Ocaml?

Answer 1

If you care about selection speed you should use a different container. Why use List with access in O(n) or Set with O(log n) when you can use Array with O(1) i.e. constant time.

To adjust your example:

let randomelement arr =
    let n = Random.int (Array.length arr) in
    Array.get arr n;;