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 (pi
) of getting compared with the search element S is placed first, followed by the element with the second highest probability, and so on. The search for element S is performed sequentially on all the sorted elements in the vector. Upon multiple search iterations, the expected number of comparisons...
