The Move-to-Front Heuristic

A linear search is fast when the target is near the front and slow when it is near the back. Programs do not look up every element equally often. On a site with thousands of accounts, a few hundred active users log in every day, and the rest almost never do. If those active users sat near the front of the list, most searches would end after a few steps.

We do not know in advance which elements will be looked up often, but the searches themselves tell us. The move-to-front heuristic uses this. Each time a search finds an element, it moves that element to the front of the list. Elements that are looked up often stay near the front. Elements that are rarely looked up drift toward the back.

It is called a heuristic because it is a rule that usually helps but does not guarantee the best outcome. Whether it helps depends on the lookups a program actually makes.

Trace

Let’s go back to usernames. Suppose a site has 1,000 accounts, stored in a LinkedSet. add inserts at the head, so the newest accounts are at the front and the oldest are at the back. Three of the oldest accounts, alice, bob, and carol, belong to regulars who log in every day. Most of the other accounts are rarely used. One of them, zed, is at position 500.

          ┌──────┐     ┌──────┐               ┌───────┐     ┌─────┐     ┌───────┐
head ───▶ │ yuki │ ──▶ │ omar │ ──▶  ···  ──▶ │ alice │ ──▶ │ bob │ ──▶ │ carol │ ──▶ null
          └──────┘     └──────┘               └───────┘     └─────┘     └───────┘
             1            2        995 more      998          999          1000

Each login calls contains with the username. When alice logs in, contains("alice") compares against 998 nodes before it finds her. The search found alice, so she moves to the front:

          ┌───────┐     ┌──────┐     ┌──────┐               ┌─────┐     ┌───────┐
head ───▶ │ alice │ ──▶ │ yuki │ ──▶ │ omar │ ──▶  ···  ──▶ │ bob │ ──▶ │ carol │ ──▶ null
          └───────┘     └──────┘     └──────┘               └─────┘     └───────┘
              1            2            3        995 more     999          1000

Every node that was ahead of alice moved back one position. The nodes behind her, bob and carol, did not move. If alice logs in again before anyone else does, the search finds her after one comparison.

Here is a sequence of logins, with the number of comparisons each one takes in a plain list and with move-to-front:

In the plain list, nothing moves, so alice pays 998 comparisons every time she logs in. With move-to-front, each regular pays the full cost once, on their first login. After that, the three regulars stay in the first few positions, and each of their logins takes at most three comparisons. The longer the sequence runs, the bigger the gap gets.

The zed row shows the downside. zed was at position 500, but the three regulars moved ahead of him, so the search reaches him after 503 comparisons. Then he moves to the front, ahead of the regulars, and pushes each of them back one position. That is why alice’s last login takes two comparisons instead of one. zed will probably not log in again for a long time, but he stays near the front until other logins push him back.

Implementation

Here is contains with the heuristic applied. It tracks prev the same way remove does, and passes the found node and its predecessor to a moveToFront helper:

@Override
public boolean contains(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> prev = null;
  Node<T> curr = head;
  while (curr != null) {
    if (item.equals(curr.value)) {
      moveToFront(curr, prev);
      return true;
    }
    prev = curr;
    curr = curr.next;
  }
  return false;
}

private void moveToFront(Node<T> node, Node<T> previous) {
  if (previous == null) {
    return;                   // already at the front; nothing to do
  }
  previous.next = node.next;  // unlink the node from its current spot
  node.next = head;           // splice it in at the head
  head = node;
}

The duplicate check inside add searches the same way, so it could move the element it finds to the front as well. remove should not, because the element it finds is about to be removed.

Analysis

The move is three assignments, so it is $O(1)$. The search before it has not changed, so contains is still $O(n)$ in the worst case. A lookup for an element at the back, or for a username that has no account, still compares against every node.

The heuristic improves the average case, and only when lookups are skewed, as they were in the trace. When every element is looked up equally often, it does not help. Each lookup moves its element to the front, but the next lookup is just as likely to be for an element at the back.

contains now changes the list, even though we think of it as a read. This is safe. The elements in the set stay the same, and only their order changes. A set has no defined order, so a client cannot see the change through the Set interface.