Linear search

When some keys are asked for far more often than others, why keep searching for them at the far end? Watch the popular keys move to the front.

⋯18int find_front(int *a, int n, int key)19{20    for (int i = 0; i < n; i++) {21        comparisons++;22        if (a[i] == key) {23            for (int k = i; k > 0; k--)24                a[k] = a[k - 1];25            a[0] = key;26            return 0;27        }28    }29    return -1;30}31 32int main(void)33{34    int a[N] = { 12, 7, 31, 4, 25, 18, 9, 40 };35    const int stream[LOOKUPS] = { 40, 9, 40, 18, 40, 9, 40, 9, 12, 40,36                                  9, 40, 40, 9, 31, 40, 9, 40, 9, 40 };37    for (int t = 0; t < LOOKUPS; t++)38        find(a, N, stream[t]);39    printf("plain: %d comparisons\n", comparisons);40    comparisons = 0;41    for (int t = 0; t < LOOKUPS; t++)42        find_front(a, N, stream[t]);43    printf("move to front: %d comparisons\n", comparisons);44    return 0;45}

Cell by cell

If an array is in no particular order, a key could be anywhere, so a search must look at the cells one at a time from the front until it finds it. That is linear search. Its cost is the number of comparisons: one per cell looked at.

The order of the cells is ours to choose, though. If a few keys are asked for again and again, moving them towards the front makes their next search short.

The code and its cost

Three cases

int find(const int *a, int n, int key)
{
    for (int i = 0; i < n; i++) {
        comparisons++;
        if (a[i] == key)
            return i;
    }
    return -1;
}

At best the key is in cell 0: 1 comparison. At worst it is in the last cell, n comparisons, and a key that is not there costs n as well: a search that finds nothing is the worst case, not a cheap one. If the key is present and equally likely to be in any cell, the average is (n + 1)/2 comparisons (Counting steps).

A sentinel

Each pass of the loop above makes two tests: i < n and a[i] == key. If the array has a spare cell, put the key in it first. The search is then sure to stop, and the bound test can go:

int find_sentinel(int *a, int n, int key)
{
    a[n] = key;
    int i = 0;
    while (a[i] != key)
        i++;
    return i < n ? i : -1;
}

If the loop stopped at cell n, it found only the sentinel, and the key is absent. The array must have room for n + 1 cells.

Moving found keys forward

int find_front(int *a, int n, int key)
{
    for (int i = 0; i < n; i++) {
        comparisons++;
        if (a[i] == key) {
            for (int k = i; k > 0; k--)
                a[k] = a[k - 1];
            a[0] = key;
            return 0;
        }
    }
    return -1;
}

Move-to-front moves each key it finds to cell 0, shifting the cells before it one place right, i moves, exactly as Inserting and deleting in an array made room. A gentler rule, transposition, swaps a found key with the one just before it, so a key creeps forward one place per lookup.

The program mtf.c runs a stream of 20 lookups, ten for 40, seven for 9 and one each for 18, 12 and 31, first with find and then with find_front on the same array. The plain scan costs 139 comparisons: 40 is always in the last cell and 9 in the one before. Move-to-front costs 68. Its first ten lookups cost 42 and its last ten only 26, as 40 and 9 settle into the first two cells. The array ends as 40 9 31 12 18 7 4 25.

Move-to-front does not help every stream. If every key is asked for equally often, in turn, the key just moved to the front is the one least likely to be wanted next, and on average nothing is gained.

Worked example

An absent key, with and without a sentinel. Search 12 7 31 4 25 18 9 40 for 99, which is not there. The plain loop makes 8 key tests and 9 bound tests: the ninth bound test, 8 < 8, is the one that stops it. With a sentinel in a ninth cell, the loop makes 9 key tests, the last one meeting the sentinel, and no bound tests. The traced program sentinel.c counts both and prints exactly those numbers.

The average for a present key. With n = 8 and every cell equally likely, the average is (1 + 2 + … + 8)/8 = 36/8 = 4.5 comparisons.

The stream’s average. The plain scan averages 139/20 = 6.95 comparisons a lookup. Move-to-front averages 68/20 = 3.4.

A stream that gains nothing. Ask for 12, 7, 31, 4, 25, 18, 9, 40 in turn, over and over. With move-to-front, each lookup moves its key to the front, which pushes the next key wanted one place further back: after the first round, every key asked for is in the last cell, and every lookup costs 8. Whatever is at the front is about to be passed over. The traced program mtf-round.c prints the costs of two rounds: 1 2 3 4 5 6 7 8, then 8 eight times.

Two checks. How many comparisons does it take to find 25 in the original order? (5.) After the stream? (8: 25 has drifted to the last cell.)

Where it’s used

Small and unsorted tables. For a handful of items, or a table searched rarely, sorting it would cost more than it saves; a linear scan is the simplest search that works.

Caches. Keeping recently used items at the front is the idea behind the least-recently-used cache, Chapter 20.

Compression. Some compressors code each symbol by its position in a move-to-front list: symbols that repeat get small numbers, which code in fewer bits.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.