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

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:53 PM, H. S. Teoh via Digitalmars-d wrote:
> On Mon, Nov 30, 2015 at 01:41:12PM -0800, H. S. Teoh via Digitalmars-d wrote:
> [...]
>> 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.
>
> In fact, it's probably provable that if there are 2 most popular items
> in the array, they will eventually migrate to the 1st two positions of
> the array. Not so sure about the case of n most popular items for n>2,
> as position 3 is a kind of odd case where it gets displaced only by
> elements from indices that aren't a power of 2, but it would seem at a
> cursory glance that the 3 most popular items would tend to settle around
> the first 4 elements of the array.
>
> Hmm... it seems that in the worst case (the most popular n items all lie
> precisely at indices of the form 2^j) the most popular items will end up
> within the first 2^n positions of the array. Not sure how to compute the
> average case; intuitively at least it seems that it should lie somewhere
> between the first n positions and the first 2^n positions.

With RStF it's easy to prove (e.g. by reductio ad absurdum) that if you 
search only for k items out of n, they will end up in the top k 
positions of the array. Then they'll churn there :o). The key to the 
proof is that in the stationary state no element migrates in our out of 
the top k slots. I think it would be difficult to achieve this property 
with a deterministic approach.

The more interesting question would be what the element distribution is 
if both elements and searches are Gaussian-distributed (probably a 
frequent case in practice).


Andrei