TAOCP 6.1 Exercise 15
Let the subroutines be arranged in some order \(a_1, a_2, \dots, a_N\).
Section 6.1: Sequential Searching
Exercise 15. ▶ [M22] The text shows how to arrange programs optimally on a system library tape, when only one program is being sought. But another set of assumptions is more appropriate for a subroutine library tape, from which we may wish to load various subroutines called for in a user’s program.
For this case let us suppose that subroutine $j$ is desired with probability $P_j$, independently of whether or not other subroutines are desired. Then, for example, the probability that no subroutines at all are needed is $(1-P_1)(1-P_2)\cdots(1-P_N)$; and the probability that the search will end just after loading the $j$th subroutine is $P_j(1-P_{j+1})\cdots(1-P_N)$. If $L_j$ is the length of subroutine $j$, the average search time will therefore be essentially proportional to
$$ L_1P_1(1-P_2)\cdots(1-P_N)+(L_1+L_2)P_2(1-P_3)\cdots(1-P_N)+\cdots+(L_1+\cdots+L_N)P_N. $$
What is the optimum arrangement of subroutines on the tape, under these assumptions?
Verified: no
Solve time: 1m39s
Solution
Let the subroutines be arranged in some order (a_1, a_2, \dots, a_N). The average search time is proportional to
[ T = \sum_{j=1}^{N} \biggl(\sum_{i=1}^{j} L_{a_i}\biggr) P_{a_j} \prod_{k=j+1}^{N} (1-P_{a_k}). ]
We can rewrite (T) by exchanging the order of summation:
[ T = \sum_{i=1}^{N} L_{a_i} \biggl( \sum_{j=i}^{N} P_{a_j} \prod_{k=j+1}^{N} (1-P_{a_k}) \biggr) = \sum_{i=1}^{N} L_{a_i} \biggl(1 - \prod_{k=i}^{N} (1-P_{a_k})\biggr). ]
The coefficient of (L_{a_i}) is the probability that the search reaches position (i), i.e. that at least one of the subroutines from (i) to (N) is desired.
To find the optimal arrangement, consider two adjacent subroutines (a) and (b) at positions (i) and (i+1). Let (X) be the set of subroutines before them and (Y) the set after them. Define
[ R = \prod_{y \in Y} (1-P_y) \qquad (\text{with } R=1 \text{ if } Y=\varnothing). ]
In the order ((a,b)) the contribution of these two subroutines to (T) is
[ C_{ab} = L_a\bigl[1 - (1-P_a)(1-P_b)R\bigr] + L_b\bigl[1 - (1-P_b)R\bigr]. ]
In the swapped order ((b,a)) it is
[ C_{ba} = L_b\bigl[1 - (1-P_a)(1-P_b)R\bigr] + L_a\bigl[1 - (1-P_a)R\bigr]. ]
The difference is
[ C_{ab} - C_{ba} = L_a P_b(1-P_a)R - L_b P_a(1-P_b)R. ]
Since (R \ge 0), the sign of this difference is determined by
[ L_a P_b(1-P_a) - L_b P_a(1-P_b). ]
If this quantity is positive, swapping (a) and (b) reduces (T); if negative, the original order is better. Therefore, to minimize (T) we should place (a) before (b) whenever
[ L_a P_b(1-P_a) \le L_b P_a(1-P_b). ]
Assuming (P_a, P_b \in (0,1)), this inequality is equivalent to
[ \frac{L_a(1-P_a)}{P_a} \le \frac{L_b(1-P_b)}{P_b}. ]
If (P_a = 1) the left side is (0) and the inequality holds (such a subroutine should be placed as early as possible); if (P_a = 0) the left side is infinite and the inequality fails unless (P_b = 0) as well (subroutines never desired should be placed at the end).
Crucially, the condition involves only the two subroutines (a) and (b); it does not depend on (X) or (Y). Hence any arrangement that violates this pairwise condition for some adjacent pair can be improved by swapping that pair. By repeatedly swapping adjacent pairs that are out of order, we eventually reach an arrangement where the subroutines are sorted in non‑decreasing order of the key
[ K_j = \frac{L_j(1-P_j)}{P_j}, ]
with the conventions (K_j = 0) when (P_j = 1) and (K_j = \infty) when (P_j = 0). No further swap can reduce (T), so this sorted arrangement is globally optimal.
Answer: The subroutines should be ordered so that the values (\displaystyle \frac{L_j(1-P_j)}{P_j}) are non‑decreasing.
∎
Notes
This result is the analogue of Smith's rule for minimizing weighted completion time, adapted to the “last success” search model. The key (\frac{L_j(1-P_j)}{P_j}) can be interpreted as the length of subroutine (j) divided by the odds (P_j/(1-P_j)) that it is desired.