Re: Binary Search
- From: Lawrence D'Oliveiro <ldo@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Sun, 27 Mar 2011 16:17:17 +1300
In message <imikdg120s@xxxxxxxxxxxxxxxxx>, Michael Wojcik wrote:
Patricia Shanahan wrote:
I would recommend comparing its performance to a linear search with the
data in descending order of historical access frequency.
You could implement the latter constraint (data in descending order of
access) dynamically using a move-to-front list, though you'd want a
data structure that offers cheap insertion at the front.
Or you could simply maintain an access counter attached to each element, and
re-sort after every, say, 10**n lookups (for n ≥ 3 or something).