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
Tobias Herp - the solution PROGRAM3_1

 


Cover Contents Index Main page

last modified 30th July 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic