Performance Evaluation of A Novel Most Recently Used Frequency Count (MRUFC) List Accessing Algorithm

摘要

List Accessing Problem (LAP) is a problem of significant theoretical and practical interest in the context of linear search. Move-To-Front (MTF) Transpose(TRANS) and Frequency Count(FC) are the three most primitive list accessing algorithms developed in the literature. FC is the static optimal offline algorithm, but it has not been studied extensively in the literature till date. In this paper, a comprehensive study of FC algorithm has been done. After our analysis we have explored the limitation of FC algorithm which is a scope to improve its performance. Based on an idea of combining the concepts of Most Recently Used (MRU) of paging algorithm and FC List Accessing algorithm, we have proposed a novel hybrid list accessing algorithm which we call as Most Recently Used Frequency Count(MRUFC) algorithm. We have evaluated the performance of FC list accessing algorithm and our proposed MRUFC algorithm by using Calgary Corpus as the input dataset. Our experimental results show that MRUFC performs better than FC for all the request sequences generated from the input dataset.