3.1. Generating Arrays¶
- File:
ArrayUtil.ml
(look forWeek 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 forWeek 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.