R Data Structures and Algorithms

Self-organizing lists

So far, we have learned that the performance of search can be enhanced by sorting the vectors based on their key values prior to the search operations. However, there seems to be an another approach for sorting vectors, which is not based on key values but on the expected frequency of accessing the key values for comparison purposes. This kind of sorting based on expected frequency of access can sometimes be cheaper compared to sorting based on key values, thereby increasing the performance of search operations.

Consider a vector V sorted based on the frequency of access of key values, but not on the value of its elements. In other words, the elements with a higher probability (p_i) of getting compared with the search element ...