3.1. Generating Arrays — YSC2229 2021 - Ilya Sergey

3.1.1. Simple random generators¶

To test not only the correctness, but also the performance of our search and sorting algorithms, let us invest some time into creating the procedures for generating random arrays. In this chapter and further in this module we will consider slightly more interesting arrays than just arrays of integers of type int array.

In such “more interesting” arrays, each of an array will be a pair of a key (an integer), identifying an element, and a value, which carries some interesting payload. In a general case, some elements might have duplicating keys, and different keys can correspond to the same element. Do not confuse the array indices (which are used for efficient access to specific array entries) with element keys (which are domain-specific and can be anything, serving to identify the corresponding payload).

Let us start from implementing a random generator for lists of random numbers in a range from 0 to a given bound, of a specified length len:

let generate_keys bound len = let acc = ref [] in for i = 0 to len - 1 do acc := (Random.int bound) :: ! acc done; !acc

Notice, that for the sake of efficiency (and diversity) the program is implemented via a loop rather than as a recursion.

Our next procedure is more interesting and will generate strings of a fixed length containing lowercase characters of the standard latin alphabet:

let generate_words length num = let random_ascii_char _ = let rnd = (Random.int 26) + 97 in Char.chr rnd in let random_string _ = let buf = Buffer.create length in for i = 0 to length - 1 do Buffer.add_char buf (random_ascii_char ()) done; Buffer.contents buf in let acc = ref [] in for i = 0 to num - 1 do acc := (random_string ()) :: ! acc done; !acc

The first function, random_ascii_char generates a random lowercase ASCII character (of which there are 26), and 97 corresponds to 'a'. random_string will create a string up to the fixed length. Finally, the main body function will add this string to the result list.

To generate arrays, let us first implement a function list_to_array that creates an array from a list of elements:

let list_to_array ls = match ls with | [] -> [||] | h :: t -> let arr = Array.make (List.length ls) h in List.iteri (fun i v -> arr.(i) <- v) ls; arr

We also define an auxiliary function list_zip, which is similar in its functionality to the standard function List.combine, but, unlike the latter does not exhaust call stack, as it is implemented in Continuation-Passing Style and is, hence, in a tail-call form:

let list_zip ls1 ls2 = let rec walk xs1 xs2 k = match xs1, xs2 with | h1 :: t1, h2 :: t2 -> walk t1 t2 (fun acc -> k ((h1, h2) :: acc)) | _ -> k [] in walk ls1 ls2 (fun x -> x)

We can finally implement an generator for key-value arrays:

let generate_key_value_array len = let kvs = list_zip (generate_keys len len) (generate_words 5 len) in list_to_array kvs

It can be used as follows:

# generate_key_value_array 10;; - : (int * string) array = [|(1, "emwbq"); (3, "yyrby"); (7, "qpzdd"); (7, "eoplb"); (6, "wrpgn"); (7, "jbkbq"); (7, "nncgq"); (1, "rruxr"); (8, "ootiw"); (7, "halys")|]

Additionally, we can implement simpler generators for arrays of integers and strings:

let generate_int_array len = generate_keys len len |> list_to_array let generate_string_array len = generate_words 5 len |> list_to_array

The “pipeline” operator |> is ised in OCaml to provide its left operand as an input to its right operand, which must be a function.