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

[H. S. Teoh via Digitalmars-d]

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.


T

-- 
Любишь кататься - люби и саночки возить.