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
