TECHNIKA: TESTOVACÍ DATA
Všechny testy mají podobnou strukturu: nejprve se vytvoří vstupní data, pak se vyvolá testovaná programová jednotka a nakonec se vyhodnotí výsledky. Cílem může být ladění, ověření složitosti algoritmu nebo vzájemné porovnání časové složitosti algoritmů. Uveďme si jako příklad testovací data pro funkci MODIFIND - nalezení K-tého nejmenšího prvku.
KONSTANTNÍ POLE
UTŘÍDĚNÉ POLE
do J = 1 to N; A.J = J; end
|
POLE NAVZÁJEM RŮZNÝCH PRVKŮ
Využijeme podprogram SHUFFLE:
do J = 1 to N; A.J = J; end
call SHUFFLE N
|
PRVKY Z INTERVALU Máme-li vytvořit pole s prvky z intervalu
[0,100000], použijeme vestavěnou funkci RANDOM:
do J = 1 to N; A.J = RANDOM(0, 100000); end
|
Pro generaci prvků s hodnotami od 1 až do 2147483646 je tu funkce LCG:
X = 171956486 /* "random" number */
do J = 1 to N; X = LCG(X); A.J = X; end
|
UTŘÍDĚNÉ NÁHODNÉ POLE I
do J = 1 to N
A.J = RANDOM(1,1000)
end
call QUICKSORT N
|
UTŘÍDĚNÉ NÁHODNÉ POLE II
A.0 = 0
do J = 1 to N
Jm1 = J - 1
A.J = A.Jm1 + RANDOM(1, 1000)
end
|
VŠECHNY PERMUTACE Důkladný test prozkoumá všech FACT(N) permutací vstupních dat pro N z intervalu [1, smallint], kde
smallint je rovno, řekněme, pěti. Viz Generování všech permutací.
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
|
ZAMÍCHÁNÍ POLE URČUJE DANÁ PERMUTACE
Zamíchání pole A. v místě je určeno permutací P. množiny { 1,...,N}:
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
|
Rychlejší kód potřebuje pomocné pole
do K = 1 to N
L = P.K; B.K = A.L
end
do K = 1 to N
A.K = B.K
end
|
|
