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
