Self Adjusting Data Structures

Self Adjusting Data Structures

Application programs are often developed using standard data structure techniques such as stacks, queues, and balanced trees with the goal of limiting worst case performance. Such programs, however, normally carry out many operations on a given data structure. This means that you may be able to trade off the individual worst case cost of each operation for that of the worst case cost over a sequence of operations. In other words, any one particular operation may be slow, but the average time over a sufficiently large number of operations is fast. This is an intuitive definition of amortized time, a way of measuring the complexity of an algorithm. In this case, the algorithms to be concerned with are those that carry out operations on data structures.

The heuristic I'll discuss in this article is called the "structural self-adjusting heuristic." To illustrate what I mean by self-adjusting, consider the following example: Suppose you're running an information warehouse and your task is to distribute information to people who request it. The information in this warehouse could be stored in a fixed order, such as the order of information in a library. You quickly notice, however, that certain pieces of information are requested more often than others. You could make the job easier by moving the most often requested information close to the service counter. This means that instead of having to search through the depths of the warehouse at any given time, you have a good portion of the most requested information nearby.

As this example suggests, self-adjusting heuristic algorithms are ideally suited to lists, binary search trees, and priority queues (heaps). In lists, the heuristic attempts to keep the most frequently accessed items as close to the front as possible. In binary search trees, the heuristic attempts to keep the most frequently accessed items as close to the root as possible, while preserving the symmetric ordering. Finally, in heaps, the heuristic attempts to minimize the cost of modifying the structure, and partially orders the heap in a simple, uniform way. To illustrate how these algorithms can be implemented (Pardee 2010).

Self-Adjusting Lists

A singly linked list is a group of records where each record contains one field that holds an individual piece of user data, and another field that holds a pointer to the next record in the list. An initial pointer that indicates which record starts the list is (or should be) kept. This pointer enables you to search, insert, and delete operations.

Move-to-Front Singly Linked Lists

To understand how the move-to-front (MTF) approach works, consider a situation in which a particular application uses an open hash table with a linked list that is associated with each array location. Suppose that the hashing routine for this application is as good as it can possibly be. If you wish to improve the search performance without unduly complicating the supporting code, however, you might examine the performance of the search performed on the lists. Chances are that certain elements are accessed more often ...