NÁHODNÝ VÝBĚR K PRVKŮ

Algoritmus vybere náhodně K prvků z pole A.1,...,A.N. Pro porovnání uvedu dva algoritmy, SAMPLING_K Donalda Knutha a SAMPLING_B Jona Bentleye.

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Globální proměnné: vstupní pole A., výstupní pole B.
 
Parametry: N - počet prvků A., přirozené číslo K - počet prvků B
 
Výsledek: Vybrané prvky jsou uloženy do pole B.
 

SAMPLING_K: procedure expose A. B.
parse arg N, K
T = 0; M = 0
do while M < K
  if RANDOM(0, N - T - 1) < K - M
    then do
      M = M + 1; T = T + 1; B.M = A.T
    end
    else T = T + 1
end
return

 

 

SAMPLING_B: procedure expose A. B.
parse arg N, K
NotMember. = 1
S = 0
do while S < K
  T = RANDOM(1, N)
  if NotMember.T
    then do
      S = S + 1; B.S = A.T; NotMember.T = 0
    end
end
return

 

POROVNÁNÍ
Pro N=10000; K=5000 a 1000 testů byla průměrná doba výpočtu SAMPLING_K okolo 0.5 sekundy a průměrná doba výpočtu SAMPLING_B byla okolo 0.3 sekundy.

 

SOUVISLOSTI

Literatura
Bentley J. Programming Pearls - A Sample of Brilliance
CACM September 1987 No. 9, p. 754-757
Knuth D. E. Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973


Obálka Obsah Index Hlavní stránka

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