Technique: Universal Unit
Assume the following task, we wish to find the median of the B. array of size N=10001. We can't use the straightforward solution, for example the code of the MODIFIND function because it works only with the A. array.
FIRST SOLUTION
We rewrite the code of the MODIFIND function for work with B. array. The program PROGRAM1 displays on the screen the result 0.698 seconds and values of medians. In practice we could write a program for automatic changes of identifiers.
/* 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 "seconds"; 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
|
SECOND SOLUTION First of all we will copy the B. array into the A. array and then call the original MODIFIND function. The PROGRAM2 displays 0.912 seconds. In this case we have to reserve the A. array for passing parameters.
/* 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 "seconds"; say S
exit
MODIFIND: procedure expose A.
...
|
THIRD SOLUTION The name of the array is stored in the Stemv variable. In this case we have to reserve only one variable for passing parameters - the Stemv variable. The PROGRAM3.1 using interpret statement displays 0.793 seconds. It is really effective but hard to code solution. PROGRAM3.2 using the VALUE function displays 0.962 seconds. In this cases is the program code almost unreadable.
/* 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)
|
FOURTH SOLUTION This is the first really general solution. MODIFIND4 can be an internal or external function. For special parameter passing, we use the external data queue. The PROGRAM4 displays 3.449 seconds.
/* 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 "seconds"; 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
|
The modification of the PROGRAM4 with the external function MODIFIND4 displays 3.328 seconds.
FIFTH SOLUTION Suppose the elements of B. array are words. Then for passing parameters, we can use a string as shown in the following program. It is second general solution. Also, the MODIFIND5 function can be coded as an external routine.
/* 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 "seconds"; 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
|
This program displays 12.825 seconds; with the external version of MODIFIND5 displays 12.885 seconds.
CONCLUSION
| Comparison of Method |
| Method |
External? |
Tool for transferring |
Time |
Disadvantage |
| 1 |
no |
none |
0.698 |
one routine for every array |
| 2 |
no |
array A. |
0.912 |
copy into A. |
| 3.1 |
no |
variable + INTERPRET |
0.793 |
unreadable code |
| 3.2 |
no |
variable + VALUE |
0.962 |
unreadable code |
| 4 |
yes |
external data queue |
3.328 |
slower |
| 5 |
yes |
string |
12.825 |
slower, lexical analyse |
COAUTHOR
|
