On 11/30/15 4:58 PM, Steven Schveighoffer wrote:
On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:
On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
What about when element i is matched, swap it with the (i/2)'th element?
Randomization is essential - without it you have thrashing if you search
for 2 elements in alternation. -- Andrei
What about selecting a random element in 0..k/2 instead of 0..k-1?
I think complexity would stay the same. Choosing a tighter range puts a
greater weight on the last search than on recent searches.
One thing I like is that I choose 0..k, not 0..k-1, which means it's
possible that the element stays put (no change in position). That
reduces thrashing for the top (most frequently searched) few elements.
andrei
