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
Tobias Herp - řešení PROGRAM3_1

 


obálka obsah index hlavní

změněno 12. dubna 2018
Copyright © 2000-2018 Vladimír Zábrodský, RNDr.

mail