Self-Organizing Heuristics

LinkedSet and ArraySet both implement the Set ADT. In both, contains is a linear search from the front, and it throws an IllegalArgumentException if the item is null.

LinkedSet<T> stores the items in a singly linked list:

public class LinkedSet<T> implements Set<T> {

  private Node<T> head;  // the first node, or null when empty
  private int size;      // how many items the set holds

  private static class Node<T> {
    T value;
    Node<T> next;
  }

  // the operations go here
}

ArraySet<T> stores the items in an unsorted array, at indices 0 through size - 1:

public class ArraySet<T> implements Set<T> {

  private T[] arr;   // the backing array
  private int size;  // how many items the set holds

  // Returns the index of item in arr, or -1 if it is not there.
  private int indexOf(T item) { /* already implemented */ }

  // the operations go here
}
Solution
@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)) {
      if (prev != null) {
        prev.next = curr.next;
        curr.next = head;
        head = curr;
      }
      return true;
    }
    prev = curr;
    curr = curr.next;
  }
  return false;
}
Solution
@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;
  }
  return true;
}
Solution

Moving the item at index i to index 0 of an array means shifting every item before it one slot to the right, which is . Swapping two neighbors is . In a linked list, moving a node to the head is a few pointer assignments, so move-to-front is there.

Solution

Move-to-front adapts right away: one lookup puts an item at the front. But a single lookup of a rarely used item also puts it ahead of all the frequently used ones. Transpose moves an item forward only one slot per lookup, so a single rare lookup barely changes the order. But a frequently used item at the back needs many lookups to reach the front.

Solution

The worst case is still for both: an item at the back, or an item that is not in the set, takes a full scan. The average cost improves when access is skewed, that is, when a few items are searched for often and most are searched for rarely. When every item is equally likely to be searched for, there is no improvement.

Solution

The heuristic changes only the order of the items inside the structure. The set still holds the same items. A set has no order and no positional operations, so a client cannot see the change through the interface.

Solution

contains(58)

          ┌────┐     ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 58 │ ──▶ │ 72 │ ──▶ │ 46 │ ──▶ │ 31 │ ──▶ null
          └────┘     └────┘     └────┘     └────┘

contains(31)

          ┌────┐     ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 31 │ ──▶ │ 58 │ ──▶ │ 72 │ ──▶ │ 46 │ ──▶ null
          └────┘     └────┘     └────┘     └────┘

contains(58)

          ┌────┐     ┌────┐     ┌────┐     ┌────┐
head ───▶ │ 58 │ ──▶ │ 31 │ ──▶ │ 72 │ ──▶ │ 46 │ ──▶ null
          └────┘     └────┘     └────┘     └────┘

contains(64) is a miss, so the list does not change.

Solution

contains(72)

┌────┬────┬────┬────┐
│ 31 │ 58 │ 72 │ 46 │
└────┴────┴────┴────┘
   0    1    2    3

contains(72)

┌────┬────┬────┬────┐
│ 31 │ 72 │ 58 │ 46 │
└────┴────┴────┴────┘
   0    1    2    3

contains(31) finds 31 at index 0, so there is nothing to swap and the array does not change.

contains(64) is a miss, so the array does not change.