Exegesis of Self-Organizing Linear Search

We consider techniques for self-organizing linear search, examining the behavior of methods under arbitrary and specific probability distributions. The notion of moving an element forward after it has been accessed k times in a row is introduced. One implementation performs the transformation after any k identical requests. A second essentially groups requests into batches of k, and performs the action only if all requests of a batch are the same. Adopting as the transformation, the move to front heuristic, the second approach is shown in general to be superior. We show that the batched approach, with k = 2, leads to an average search time no greater than 1. 21. . . times that of the optimal ordering. For the more direct approach, a ratio of 1. 36. . . is shown under the same constraints. The simple move to front heuristic (i. e. , k = 1) is also examined. It is shown that for a particular distribution this scheme can lead to an average number of probes /2 times that of the optimal order. Within an interesting class of distributions, this is shown to be the worst average behavior.