# 3.1. Generating Arrays¶

- File:
`ArrayUtil.ml`

(look for`Week 03 functions`

)

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

## 3.1.2. Measuring execution time¶

- File:
`Util.ml`

(look for`Week 03 functions`

)

For our future experiments with algorithms and data structures, it is useful to be able to measure execution time of computations we run. To do so, we implement the following helper function:

```
let time f x =
let t = Sys.time () in
let fx = f x in
Printf.printf "Execution elapsed time: %f sec\n" (Sys.time () -. t);
fx
```

It can be used with any arbitrary computation that takes at least one argument (thanks to currying).

## 3.1.3. Randomised array generation and testing¶

Let us make use of the random generators for testing `insert_sort`

and its performance:

```
open InsertSortArray;;
# let a = generate_key_value_array 5000;;
val a : (int * string) array =
[|(894, "goavt"); (2768, "hvjjb"); (3535, "pbkoy"); (1615, "ybzua");
(2820, "ssriq"); (2060, "sfxsu"); (2328, "kjgff"); (112, "xuoht");
(1188, "xxfcs"); (2384, "xbwgb");
(1134, "oi"... (* string length 5; truncated *)); (3102, ...); ...|]
# time insert_sort a;;
Execution elapsed time: 0.395832 sec
- : unit = ()
```

Notice that the comparison operator `<`

in OCaml is overloaded and
works not only on integers but on arbitrary values, implementing an
ad-hoc comparison. Thanks to this, even though we initially designed
`insert_sort`

to work on arrays of integers, it works on arrays of
pairs equally well.