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 -- Любишь кататься - люби и саночки возить.
