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

[Steven Schveighoffer via Digitalmars-d]

On 11/30/15 5:07 PM, Andrei Alexandrescu wrote:
> On 11/30/15 4:58 PM, Steven Schveighoffer wrote:
>>
>> What about selecting a random element in 0..k/2 instead of 0..k-1?
>
> I think complexity would stay the same. Choosing a tighter range puts a
> greater weight on the last search than on recent searches.

In the case where you search for a very small number of elements, it 
puts an upper bound on how soon they make it to the front (log(n) 
instead of n)

> One thing I like is that I choose 0..k, not 0..k-1, which means it's
> possible that the element stays put (no change in position). That
> reduces thrashing for the top (most frequently searched) few elements.

I think insignificantly, depending on the number of "frequently 
searched" elements. But you could tune it, let's say to 8 elements:

const upperBound = max(k/2, min(8, k));

There are a lot of options for tuning that can be played with, probably 
the best way to "prove" what is best is to just try some experiments :)

-Steve