MTF

1985年

同一の探索値で次回探索した時に最短時間で探索できるようにするには、キャッシュのデータをどのように配置換えすればよいか？

もし要求されるデータの確率が知られているなら、確率の高さの順に、先頭から並べていけばよいのは明らかです。しかし、実際には、要求確率はわかりません。

自己組織化リスト（Self-organizing list)の問題

探索は端から順に一つづつ調べる

この問題について、1970年代から80年代に、コンピュータ科学者が一連の研究を行ないました。

『アルゴリズム思考術』によると、85年にダニエル・スリ―ターとロバート・タージャンが発表した論文が、この問題を解決しました。それによれば、使用したデータをリストの先頭に戻せばよいのです。これは、Move-to-Front (MTF)法 と呼ばれます。そうすれば、探索時間は、要求確率が分かっている場合の2倍以上にはならないことを、彼らは証明しました。