The Transpose Heuristic

We would like ArraySet to organize itself the way LinkedSet does, but move-to-front does not fit an array. Moving the element at index i to the front means shifting every element before it one slot to the right. That is $O(n)$, so the move would cost as much as the search it is meant to shorten.

In an array we make a smaller change. When a search finds an element, we swap it with the element just before it. This is the transpose heuristic. Swapping two neighbors is $O(1)$, with no shifting. An element that is looked up often moves forward one slot per lookup, and over many lookups it reaches the front.

Trace

Let’s use the same site with 1,000 accounts, this time stored in an ArraySet. add appends at the end, so the oldest accounts are at the front. The three regulars, carol, bob, and alice, are already at indices 0, 1, and 2. A search for the element at index i takes i + 1 comparisons.

Suppose dana has just signed up, so she is at the back, at index 999. She logs in every day from now on.

  ┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
  │ carol │  bob  │ alice │  ···  │  ravi │  omar │  yuki │  dana │
  └───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
      0       1       2              996     997     998     999

Her first login takes 1,000 comparisons, and dana swaps with yuki to index 998. Her second login takes 999 comparisons, and she swaps with omar to index 997. Her third login takes 998 comparisons, and she swaps with ravi to index 996:

  ┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
  │ carol │  bob  │ alice │  ···  │  dana │  ravi │  omar │  yuki │
  └───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
      0       1       2              996     997     998     999

This is the cost of transpose. With move-to-front, dana’s second login would take one comparison. With transpose, she has to log in 999 times before she reaches the front.

The slow climb also has an upside. zed, the dormant account, is at index 500 and logs in once. Transpose moves him to index 499, and the regulars at the front are not affected. With move-to-front, his one login put him ahead of all three regulars.

Implementation

With indexOf already in place, contains does the search, then the swap:

@Override
public boolean contains(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  int i = indexOf(item);
  if (i == -1) {
    return false;
  }
  if (i > 0) {
    T temp = arr[i];
    arr[i] = arr[i - 1];
    arr[i - 1] = temp;  // swap the found item one step toward the front
  }
  return true;
}

The if (i > 0) guard skips the swap when the item is already first.

Analysis

As with move-to-front, the worst case is still $O(n)$, and the average case improves only when lookups are skewed. contains now changes the array, and this is safe for the same reason as before: a set has no defined order.

Neither heuristic is always better. Move-to-front adapts right away, but one rare lookup can push a rarely used element ahead of the common ones. Transpose is not thrown off by one rare lookup, but it takes many lookups to adapt. The right choice depends on how the lookups a program makes are spread out over time.