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

A. = 1

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

Typický příklad testovacího programu, pro zjištění doby běhu programu a shody ve výsledku, představuje PROGRAM1 v Technika: Univerzální programová jednotka.


Obálka Obsah Index Hlavní stránka

změněno 8. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.