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

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 04:33:27PM -0500, Andrei Alexandrescu via Digitalmars-d wrote:
[...]
> 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.
[...]
> 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.

What about when element i is matched, swap it with the (i/2)'th element?

Then it will take just log(n) searches to bring it to the front of the
array, but it won't (immediately) compete with whatever's currently the
most popular item in the array. Furthermore, when it does compete with
it, it will already have been moved closer to the front of the array, so
the previous most-popular element won't be pushed far back into the deep
recesses of the array, but remain close to the front where it will be
quickly found.

More generally, you could pick the (i/k)'th element for swapping when
you've matched an element, with k being a constant, chosen parameter.
You may be able to optimize for certain use cases (e.g., if you knew
beforehand the average number of "popular" elements) by choosing an
appropriate value of k.


T

-- 
Nobody is perfect.  I am Nobody. -- pepoluan, GKC forum