AlgoVerse

Move-to-front

A self-organizing list: each requested item moves to the front, so popular items stay near it; its cost is at most 4 times the best offline method's.

In a linked list, finding the k-th item takes k steps. If some items are requested more often, they should sit near the front. But we do not know which ones in advance; the algorithm has to decide online.

Read the full explanation ↓
Input:
L 1×5 · R 1×8PDF export

The list starts as 1 2 3 4 5 and the requests keep coming back to 4 and 5; after the first time they sit at the front and are cheap.

  1. def move_to_front(L, R):
  2. lst = list(L[0])
  3. cells = [lst] # for the picture: the list as one table row
  4. cost = 0
  5. for x in R[0]:
  6. i = 0
  7. while i < len(lst) and lst[i] != x:
  8. i = i + 1
  9. if i == len(lst):
  10. lst.append(x)
  11. cost = cost + i + 1
  12. lst.pop(i)
  13. lst.insert(0, x)
  14. return cost

Invariant: The list's items are in order of their last request (the most recent first), apart from those never requested yet.

Start

x—
i—
cost—

The table is still empty.

Local variables

Orange = changed in this step

L list

[1, 2, 3, 4, 5]

R list

[4, 5, 4, 5, 4, 1, 4, 5]

Call stack

  1. move_to_front()line 1
Step 1 of 92
Black = found · Orange = key stepscan: 0/15 · found: 0/8 · to_front: 0/8
    Explanation

    The idea

    In a linked list, finding the k-th item takes k steps. If some items are requested more often, they should sit near the front. But we do not know which ones in advance; the algorithm has to decide online.

    Move-to-front is the simplest rule: each requested item moves to the front of the list. Other rules:

    • transpose: the requested item swaps only with the item in front of it;
    • frequency count: the list stays sorted by how often each item was requested.

    Competitive analysis

    Sleator and Tarjan showed that on any request sequence, move-to-front costs at most 4 times what the best offline method costs, one that knows all requests in advance (counting swaps). Transpose has no such guarantee.

    The input

    L is the starting list and R the requests. A request that is not in the list is added at its end.