Technique: Test Data Sets

The tests all have the same structure: an input is constructed, the routine is called, and the answer is checked for correctness. Target of a test can be debugging of code or empirical study of complexity of the algorithm or comparing one algorithm against others. For example: The suited test data sets to testing the MODIFIND function follow

CONSTANT ARRAY

 A. = 1

SORTED ARRAY

 do J = 1 to N; A.J = J; end

ARRAY OF DISTINCT ELEMENTS

For creating of such an array, we use the SHUFFLE subroutine:

 do J = 1 to N; A.J = J; end call SHUFFLE N

ELEMENTS UNIFORMLY RANDOM IN INTERVAL

For creating any input array of elements with values ranging from 0 (minimum) to 100000 (maximum), we use the RANDOM built-in function:

 do J = 1 to N; A.J = RANDOM(0, 100000); end

For generation of elements with values ranging form 1 to 2147483646, there is the LCG function:

 X = 171956486 /* "random" number */ do J = 1 to N; X = LCG(X); A.J = X; end

SORTED RANDOM ARRAY I

 do J = 1 to N   A.J = RANDOM(1,1000) end call QUICKSORT N

SORTED RANDOM ARRAY II

 A.0 = 0 do J = 1 to N   Jm1 = J - 1   A.J = A.Jm1 + RANDOM(1, 1000) end

ALL PERMUTATIONS

The thorough test examines FACT(N) permutations for N in [1,smallint], where smallint is equal to 5, for example. See Generation of permutation sequences.

 N=5; Median = 3 C. = 1; Pr. = 1 do J = 1 to N; P.J = J; end C.N = 0 do I = 1 to N; A.I = P.I; end call MODIFIND N, Median J = 1 do while J < N   X = 0  do J = 1 while C.J = N - J + 1   Pr.J = \Pr.J; C.J = 1   if Pr.J then X = X + 1   end   if J < N     then do       if Pr.J then K = C.J + X         else K = N - J + 1 - C.J + X       Kp1 = K + 1; W = P.K       P.K = P.Kp1; P.Kp1 = W       do I = 1 to N; A.I = P.I; end       call MODIFIND N, Median       C.J = C.J + 1     end end return

SHUFFLING ARRAY ACCORDING TO CERTAIN PERMUTATION

Shuffling the array A. according to certain permutation P. of set {1,...,N}. Shuffling in place

 do K = 1 to N   L = P.K   do while L < K; L = P.L; end   W = A.K; A.K = A.L; A.L = W end

The fastest code with a temporary array follows

 do K = 1 to N   L = P.K; B.K = A.L end do K = 1 to N   A.K = B.K end

For a typical example of test see PROGRAM1 in Technique: Universal Unit

 cover contents index main page