On Mon, Nov 30, 2015 at 04:33:27PM -0500, Andrei Alexandrescu via Digitalmars-d wrote: [...] > One well-known search strategy is "Bring to front" (described by Knuth > in TAoCP). A BtF-organized linear data structure is searched with the > classic linear algorithm. The difference is what happens after the > search: whenever the search is successful, the found element is > brought to the front of the structure. If we're looking most often for > a handful of elements, in time these will be near the front of the > searched structure. [...] > So let's see how we can implement a successful BtF for arrays. > > The first idea is to just swap the found element with the first > element of the array. That's O(1) but has many disadvantages - if you > search e.g. for two elements, they'll compete for the front of the > array and they'll go back and forth without making progress. > > Another idea is to just swap the found element with the one just > before it. The logic is, each successful find will shift the element > closer to the front, in a bubble sort manner. In time, the frequently > searched elements will slowly creep toward the front. The resulting > performance is not appealing - you need O(n) searches to bring a given > element to the front, for a total of O(n * n) steps spent in the n > searches. Meh. > > So let's improve on that: whenever an element is found in position k, > pick a random number i in the range 0, 1, 2, ..., k inclusive. Then > swap the array elements at indexes i and k. This is the Randomized > Slide to Front strategy.
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. More generally, you could pick the (i/k)'th element for swapping when you've matched an element, with k being a constant, chosen parameter. You may be able to optimize for certain use cases (e.g., if you knew beforehand the average number of "popular" elements) by choosing an appropriate value of k. T -- Nobody is perfect. I am Nobody. -- pepoluan, GKC forum
