TECHNIKA: UNIVERZÁLNÍ PROGRAMOVÁ JEDNOTKA
Předpokládejme, že máme řešit úlohu najít medián pole B. rozměru N=10001. Nemůžeme využít přímo funkci MODIFIND z tohoto alba, protože ta pracuje s polem A..
PRVNÍ ŘEŠENÍ
Přepíšeme kód funkce MODIFIND tak, aby pracovala s polem B.; program PROGRAM1 zobrazí jako výsledek 0.698 sec a hodnoty mediánů. Pro praktické využití tohoto obratu, bychom si mohli napsat program, který by automaticky měnil jméno pole v programovém kódu.
/* PROGRAM1 */
N = 10001; K = 5001
Seed = RANDOM(1, 1, 481989)
Total = 0; S = ""
do 10
do J = 1 to N
B.J = RANDOM(1, 100000)
end
call TIME "R"
S = S MODIFIND1(N, K)
Total = Total + TIME("R")
end
say Total / 10 "sec"; say S
exit
MODIFIND1: procedure expose B.
parse arg N, K
L = 1; R = N
do while L < R
X = B.K; I = L; J = R
do until J < K | K < I
do while B.I < X; I = I + 1; end
do while X < B.J; J = J - 1; end
W = B.I; B.I = B.J; B.J = W
I = I + 1; J = J - 1
end
if J < K then L = I
if K < I then R = J
end
return B.K
|
DRUHÉ ŘEŠENÍ Nejprve vždy zkopírujeme pole B. do A. a pak vyvoláme původní funkci MODIFIND.
/* PROGRAM2 */
N = 10001; K = 5001
Seed = RANDOM(1, 1, 481989)
Total = 0; S = ""
do 10
do J = 1 to N
B.J = RANDOM(1, 100000)
end
call TIME "R"
do J = 1 to N; A.J = B.J; end
S = S MODIFIND(N, K)
Total = Total + TIME("R")
end
say Total / 10 "sec"; say S
exit
MODIFIND: procedure expose A.
...
|
PROGRAM2 zobrazí 0.912 sec. Musíme však pole A. rezervovat pro předání parametrů.
TŘETÍ ŘEŠENÍ V proměnné Stemv se předá funkci jméno pole. V tomto případě rezervujeme jen jméno jediné proměné Stemv.
PROGRAM3_1 zobrazí 0.793 sec. PROGRAM3_2 zobrazí 0.962 sec.
Výsledný programový kód není snadno pochopitelný ani v jednom případě.
/* PROGRAM3_1 */
N = 10001; K = 5001
Seed = RANDOM(1, 1, 481989)
Total = 0; S = ""
StemV = 'B.'
do 10
do J = 1 to N
B.J = RANDOM(1, 100000)
end
call TIME "R"
S = S MODIFIND3_1(N, K)
Total = Total + TIME("R")
end
say Total / 10 "seconds"; say S
exit
MODIFIND3_1: procedure expose (StemV)
parse arg N, K
L = 1; R = N
interpret,
'do while L < R ;',
'X = 'StemV'K; I = L; J = R ;',
'do until J < K | K < I ;',
'do while 'StemV'I < X; I = I + 1; end ;',
'do while X < 'StemV'J; J = J - 1; end;',
'W = 'StemV'I; 'StemV'I = 'StemV'J;',
StemV'J = W;',
'I = I + 1; J = J - 1;',
'end;',
'if J < K then L = I;',
'if K < I then R = J;',
'end;',
'return 'StemV'K'
|
/* PROGRAM3_2 */
N = 10001; K = 5001; Stemv = "B."
Seed = RANDOM(1, 1, 481989)
Total = 0; S = ""
do 10
do J = 1 to N
B.J = RANDOM(1, 100000)
end
call TIME "R"
S = S MODIFIND3_2(N, K)
Total = Total + TIME("R")
end
say Total / 10 "seconds"; say S
exit
MODIFIND3_2: procedure expose Stemv (Stemv)
parse arg N, K
L = 1; R = N
do while L < R
X = VALUE(Stemv || K); I = L; J = R
do until J < K | K < I
do while VALUE(Stemv || I) < X
I = I + 1
end
do while X < VALUE(Stemv || J)
J = J - 1
end
W = VALUE(Stemv || I, VALUE(Stemv || J))
T = VALUE(Stemv || J, W)
I = I + 1; J = J - 1
end
if J < K then L = I
if K < I then R = J
end
return VALUE(Stemv || K)
|
ČTVRTÉ ŘEŠENÍ To je první skutečně obecné řešení, které může být použito i pro vnější funkce a podprogramy. Pro předání parametrů využijeme externí datovou frontu. PROGRAM4 zobrazí 3.449 sec.
/* PROGRAM4 */
N = 10001; K = 5001
Seed = RANDOM(1, 1, 481989)
Total = 0; S = ""
do 10
do J = 1 to N
B.J = RANDOM(1, 100000)
end
call TIME "R"
do J = 1 to N; queue B.J; end
S = S MODIFIND4(N, K)
Total = Total + TIME("R")
end
say Total / 10 "sec"; say S
exit
MODIFIND4: procedure
parse arg N, K
do J = 1 to N; pull A.J; end
L = 1; R = N
do while L < R
X = A.K; I = L; J = R
do until J < K | K < I
do while A.I < X; I = I + 1; end
do while X < A.J; J = J - 1; end
W = A.I; A.I = A.J; A.J = W
I = I + 1; J = J - 1
end
if J < K then L = I
if K < I then R = J
end
return A.K
|
Upravený PROGRAM4, volající vnější funkci MODIFIND4 (jediná úprava - vynechání příkazu procedure) zobrazí 3.328 sec.
PÁTÉ ŘEŠENÍ Předpokládejme, že prvky pole B. jsou slova. Pak pole B. může být předáno jako řetězec znaků, ve kterém jednotlivé prvky oddělují mezery. Tento postup je použitelný i pro předání parametrů vnější funkci. V obecném případě může být lexikální alnalýza, potřebná pro převzetí hodnot jednotlivých prvků, mnohem složitější.
/* PROGRAM5 */
N = 10001; K = 5001
Seed = RANDOM(1, 1, 481989)
Total = 0; S = ""
do 10
do J = 1 to N
B.J = RANDOM(1, 100000)
end
call TIME "R"
String = ""
do J = 1 to N
String = String B.J
end
S = S MODIFIND5(N, K, String)
Total = Total + TIME("R")
end
say Total / 10 "sec"; say S
exit
MODIFIND5: procedure
parse arg N, K, String
do J = 1 to N
parse var String A.J String
end
L = 1; R = N
do while L < R
X = A.K; I = L; J = R
do until J < K | K < I
do while A.I < X; I = I + 1; end
do while X < A.J; J = J - 1; end
W = A.I; A.I = A.J; A.J = W
I = I + 1; J = J - 1
end
if J < K then L = I
if K < I then R = J
end
return A.K
|
Tento program vypíše 12.825 sec; v případě verze s vnější funkcí 12.885 sec.
SHRNUTÍ
| Porovnání metod |
| Metoda |
Externí? |
Prostředek předání |
Čas výpočtu |
Nevýhoda |
| 1 |
ne |
žádný |
0.698 |
pro každé pole jiná rutina |
| 2 |
ne |
pole A. |
0.912 |
kopírování do A. |
| 3.1 |
ne |
proměnná+INTERPRET |
0.793 |
nečitelný programový kód |
| 3.2 |
ne |
proměnná+VALUE |
0.962 |
nečitelný programový kód |
| 4 |
ano |
externí datová fronta |
3.328 |
pomalejší |
| 5 |
ano |
řetězec |
12.825 |
pomalejší, lex. analýza |
SPOLUAUTOR
|
