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

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:58 PM, Steven Schveighoffer wrote:
> On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:
>> On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
>>> What about when element i is matched, swap it with the (i/2)'th element?
>>
>> Randomization is essential - without it you have thrashing if you search
>> for 2 elements in alternation. -- Andrei
>>
>
> 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.

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.


andrei