Move-to-front heuristic in Python
Moves each accessed element to the front of the list; 2-competitive against optimal static order.
- File
move_to_front_heuristic.py, 64 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/move-to-front-heuristic/. The authors are listed in prov/ADRSG4.jsonl.
from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar
K = TypeVar("K", bound=Hashable)
class _Node(Generic[K]):
__slots__ = ("key", "next")
def __init__(self, key: K, nxt: "_Node[K] | None") -> None:
self.key = key
self.next = nxt
class MoveToFrontList(Generic[K]):
"""A singly linked list of distinct keys that moves each accessed key to the front.
access(x) costs Theta(i) time, where i is the 1-based position of x, and
uses O(1) extra space. Its return value is i, the cost of the request in
the list update model of Sleator and Tarjan.
"""
def __init__(self, keys: Iterable[K] = ()) -> None:
items = list(keys)
if len(set(items)) != len(items):
raise ValueError("the keys must be distinct")
self.head: _Node[K] | None = None
for key in reversed(items):
self.head = _Node(key, self.head)
def access(self, x: K) -> int:
"""Return the 1-based position of x and move x to the front.
Precondition: x is in the list (else KeyError, and the list is unchanged).
"""
prev: _Node[K] | None = None
cur, i = self.head, 1 # @line L1
while cur is not None and cur.key != x: # @line L2
prev, cur, i = cur, cur.next, i + 1 # @line L3
if cur is None:
raise KeyError(x)
if prev is not None: # @line L4
prev.next = cur.next # @line L5
cur.next = self.head # @line L6
self.head = cur # @line L7
return i # @line L8
def to_list(self) -> list[K]:
"""Return the keys from front to back. Cost Theta(n)."""
out: list[K] = []
cur = self.head
while cur is not None:
out.append(cur.key)
cur = cur.next
return out
def mtf_total_cost(start: Iterable[K], requests: Iterable[K]) -> int:
"""Return the total cost of MTF on the requests from the start list. Cost O(n m)."""
lst = MoveToFrontList(start)
return sum(lst.access(x) for x in requests)
test_move_to_front_heuristic.py 90 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/move-to-front-heuristic/. The authors are listed in prov/ADRSG4.jsonl.
import itertools
import random
import pytest
from move_to_front_heuristic import MoveToFrontList, mtf_total_cost
def test_example() -> None:
lst = MoveToFrontList("abcde")
costs = [lst.access(x) for x in "dbdeadb"]
assert costs == [4, 3, 2, 5, 4, 3, 4]
assert lst.to_list() == list("bdaec")
assert sum(costs) == 25
assert mtf_total_cost("abcde", "e" * 10) == 14
def test_edges() -> None:
one = MoveToFrontList([7])
assert one.access(7) == 1 and one.to_list() == [7]
lst = MoveToFrontList([1, 2, 3])
assert lst.access(1) == 1 and lst.to_list() == [1, 2, 3]
assert lst.access(3) == 3 and lst.to_list() == [3, 1, 2]
with pytest.raises(KeyError):
lst.access(9)
assert lst.to_list() == [3, 1, 2]
with pytest.raises(ValueError):
MoveToFrontList([1, 1])
assert mtf_total_cost([], []) == 0
def test_random_against_python_list() -> None:
rng = random.Random(1985)
for _ in range(600):
n = rng.randint(1, 9)
keys = rng.sample(range(100), n)
lst = MoveToFrontList(keys)
model = list(keys)
for _ in range(rng.randint(0, 30)):
x = rng.choice(keys)
want = model.index(x) + 1
model.insert(0, model.pop(want - 1))
assert lst.access(x) == want
assert lst.to_list() == model
def _serve_random_algorithm(start: list[int], requests: list[int], rng: random.Random) -> tuple[int, int, int]:
"""An arbitrary algorithm A: random paid and free exchanges. Returns (C_A, X_A, F_A)."""
a = list(start)
c = x_paid = f_free = 0
for x in requests:
for _ in range(rng.randint(0, 2)):
if len(a) > 1:
j = rng.randrange(len(a) - 1)
a[j], a[j + 1] = a[j + 1], a[j]
x_paid += 1
i = a.index(x)
c += i + 1
moves = rng.randint(0, i)
for _ in range(moves):
a[i - 1], a[i] = a[i], a[i - 1]
i -= 1
f_free += moves
return c, x_paid, f_free
def test_sleator_tarjan_bound() -> None:
rng = random.Random(28)
for _ in range(600):
n = rng.randint(1, 7)
start = list(range(n))
reqs = [rng.randrange(n) for _ in range(rng.randint(1, 25))]
c, x_paid, f_free = _serve_random_algorithm(start, reqs, rng)
assert mtf_total_cost(start, reqs) <= 2 * c + x_paid - f_free - len(reqs)
def test_against_every_static_order() -> None:
rng = random.Random(202)
for _ in range(100):
n = rng.randint(1, 5)
start = list(range(n))
reqs = [rng.randrange(n) for _ in range(rng.randint(1, 15))]
mtf = mtf_total_cost(start, reqs)
for perm in itertools.permutations(start):
inv = sum(1 for a, b in itertools.combinations(perm, 2) if a > b)
static = sum(perm.index(x) + 1 for x in reqs)
assert mtf <= 2 * static + inv - len(reqs)
What the next level needs
- the tests did not run in this build