And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

Now that we got talking about searching in arrays, allow me to also 
share an idea I've had a short while ago.

(Again, we're in the "I'd prefer to use an array if at all possible" 
mindset. So let's see how we can help searching an array with as little 
work as possible.)

One well-known search strategy is "Bring to front" (described by Knuth 
in TAoCP). A BtF-organized linear data structure is searched with the 
classic linear algorithm. The difference is what happens after the 
search: whenever the search is successful, the found element is brought 
to the front of the structure. If we're looking most often for a handful 
of elements, in time these will be near the front of the searched structure.

For a linked list, bringing an element to the front is O(1) (just rewire 
the pointers). For an array, things are not so pleasant - rotating the 
found element to the front of the array is O(n).

So let's see how we can implement a successful BtF for arrays.

The first idea is to just swap the found element with the first element 
of the array. That's O(1) but has many disadvantages - if you search 
e.g. for two elements, they'll compete for the front of the array and 
they'll go back and forth without making progress.

Another idea is to just swap the found element with the one just before 
it. The logic is, each successful find will shift the element closer to 
the front, in a bubble sort manner. In time, the frequently searched 
elements will slowly creep toward the front. The resulting performance 
is not appealing - you need O(n) searches to bring a given element to 
the front, for a total of O(n * n) steps spent in the n searches. Meh.

So let's improve on that: whenever an element is found in position k, 
pick a random number i in the range 0, 1, 2, ..., k inclusive. Then swap 
the array elements at indexes i and k. This is the Randomized Slide to 
Front strategy.

With RStF, worst case search time remains O(n), as is the unsuccessful 
search. However, frequently searched elements migrate quickly to the 
front - it only takes O(log n) searches to bring a given value at the 
front of the array.

Insertion and removal are both a sweet O(1), owing to the light 
structuring: to insert just append the element (and perhaps swap it in a 
random position of the array to prime searching for it). Removal by 
position simply swaps the last element into the position to be removed 
and then reduces the size of the array.

So the RStF is suitable in all cases where BtF would be recommended, but 
allows an array layout without considerable penalty.

Related work: Theodoulos Garefalakis' Master's thesis "A Family of 
Randomized Algorithms for List Accessing" describes Markov Move to 
Front, which brings the searched element to front according to a Markov 
chain schedule; and also Randomized Move to Front, which decides whether 
a found element is brought to front depending on a random choice. These 
approaches are similar in that they both use randomization, but 
different because neither has good complexity on array storage.


Andrei